Corso di Modellazione geometrica A.A. 1999-2000

Elenco studenti e gruppi di laboratorio

Dispense

Laboratorio

Esercitazione

ULTIME NOVITA' E PRECISAZIONI:

• DATA CONSEGNA: viene spostata al 25 gennaio per chi intende dare l'esame l'1 febbraio (ex appello del 31 gennaio posticipato di un giorno).
• L'algoritmo deve funzionare correttamente nei casi di input NON DEGENERE (punti NON tutti allineati). Gli input degeneri possono essere semplicemente riconosciuti e rifiutati.
• (Solo per chi ha scelto Graham) Se nell'implementazione dell'algoritmo avete usato la funzione di qsort, la stima di complessita' temporale risente della complessita' di qsort che e' diversa nel caso medio e nel caso pessimo. Potete fare una stima solo della parte realizzata da voi (cioe' qsort esclusa) e dire che a questo va aggiunto il costo di qsort; poi concludere sulla complessita' totale distinguendo i due casi di qsort.
• (Solo per chi ha scelto Graham) SEGNALAZIONE D'ERRORE NEL TESTO:
  Vi ho detto di tenere un contatore, aumentarlo ogni volta che si esamina una terna "che va bene", e fermarsi quando il contatore raggiunge il numero totale di punti + 1.
  In realta' questo non e' sufficiente. Bisogna anche tenere conto delle terne "che non vanno bene", in quanto per ognuna di queste terne si torna indietro di un vertice sulla lista, e per controbilanciare questo poi bisogna avanzare una volta in piu'.
  Un modo per correggere l'errore e' il seguente:
  • tenere un contatore come si e' detto
  • fermarsi quando vale numero punti + 1 come si e' detto
  • incrementarlo ad ogni terna "buona" come si e' detto
  • in piu' (cosa che non era stata detta) decrementarlo ad ogni terna "non buona"
  Un altro modo e' non decrementarlo mai, e invece contare a parte il numero di terne "non buone" incontrate; ci si ferma quando il contatore ha raggiunto numero punti + 1 + numero di terne non buone.

Spiegazioni