Progettazione di Algoritmi a.a. 2010-2011

(canale 1)


Programma in breve


I seguenti argomenti saranno trattati durante il corso:

Libri di testo e riferimenti


Il libro di testo "ufficiale" del corso è "Introduction to Algorithms" di Cormen, Leiserson, Rivest. Qualsiasi edizione del libro va bene ed esiste anche la traduzione in italiano. Gli studenti sono comunque liberi di studiare su qualsiasi altro libro (che fornisca una preparazione di livello universitario, ovviamente). Il modo con cui gli argomenti saranno presentati a lezione potrà differire dal testo ufficiale. Gli studenti potranno comunque dimostrare la loro conoscenza di un generico argomento nel modo che preferiscono: seguendo quanto visto a lezione, oppure adeguandosi al testo ufficiale o infine usando un testo alternativo (purchè l'argomento in questione sia trattato ad un livello formale uguale o superiore a quello visto a lezione o nel testo ufficiale).

Per la parte finale di Calcolabilità e Complessità si può fare riferimento ai primi tre capitoli di "Computational Complexity" di Papadimitriou (qualsiasi edizione) e al corrispondente capitolo del Cormen.

Ricevimento e contatti


Il metodo migliore per contattarmi per questioni riguardanti il corso è via email franceschini@di.uniroma1.it. Se non rispondo ad un'email entro una settimana allora è probabile che l'abbia persa quindi riprovate.
L'orario di ricevimento è "semi-dinamico": ogni settimana il primo studente che chiede e riceve un appuntamento fissa implicitamente anche il giorno e l'ora di ricevimento per quella settimana.

Modalità d'esame


È fortemente consigliato seguire le lezioni del corso. Il corso non ha propedeuticità "di diritto". L'aver sostenuto l'esame di Introduzione agli algoritmi è certamente d'aiuto ma non strettamente necessario. È comunque da notare che gli strumenti di base del corso di Introduzione agli algoritmi (e.g. l'analisi di equazioni di ricorrenza) saranno considerati acquisiti durante il corso di Progettazione di Algoritmi.
Gli studenti che devono sostenere l'esame di Progettazione di Algoritmi (9 crediti) dovranno superare una prova scritta e una prova orale. Gli studenti che devono sostenere l'esame di Algoritmi II (6 crediti) dovranno sostenere la sola prova orale.

La prova scritta è divisa in due parti. La prima parte consiste di domande per verificare la conoscenza e comprensione di base della materia. (e.g. definizioni, algoritmi, dimostrazioni ecc, presentati durante il corso). La seconda parte consiste di domande tese a quantificare in maniera più precisa il livello di comprensione profonda della materia da parte dello studente (e.g. risoluzione di problemi non visti a lezione).
Durante la prova scritta non sarà possibile usare libri, appunti, computer ecc. Di fronte allo studente dovranno esserci solo una penna e dei fogli protocollo (fogli forniti al momento dell'esame).

La prova orale avrà un peso maggiore della prova scritta nella determinazione del voto finale dello studente. Anche la prova orale sarà divisa in due parti con domande di difficoltà crescente. La prima parte consisterà di domande per verificare la conoscenza e comprensione di base dello studente, mentre la seconda servirà a sondare il livello di comprensione profonda della materia.

Le prime parti delle prove scritte e orali sono fondamentali per il superamento dell'esame. Per ogni studente X che sostenga l'esame di Progettazione di Algoritmi (9 crediti) valgono le seguenti regole:
  1. X accede all'orale se e solo se X supera la prima parte dello scritto
  2. X supera l'esame se e solo se X supera la prima parte dell'orale
  3. Se X ha superato l'esame allora X può ottenere un voto finale >25 solo se X ha superato la seconda parte dello scritto o dell'orale.
Mentre per ogni studente X che sostenga l'esame di Algoritmi II (6 crediti) valgono solo le regole II e III (non dovendo sostenere lo scritto).

Orario, aula e annunci


Le lezioni si svolgono tutti i lunedi, mercoledi e venerdi, ore 16-18, in Aula I, Edificio Fermi, Dipartimento di Fisica, Città Universitaria.

Annunci

Sintesi delle lezioni

Gli argomenti sottolineati sono di secondo livello.
  1. 14 Marzo

  2. 16 Marzo

  3. 18 Marzo

  4. 21 Marzo

  5. 23 Marzo

  6. 25 Marzo

  7. 28 Marzo

  8. 30 Marzo

  9. 1 Aprile

  10. 4 Aprile

  11. 6 Aprile

  12. 8 Aprile

  13. 11 Aprile

  14. 13 Aprile

  15. 15 Aprile

  16. 18 Aprile

  17. 20 Aprile

  18. 4 Maggio

  19. 6 Maggio

  20. 9 Maggio

  21. 11 Maggio

  22. 13 Maggio

  23. 18 Maggio

  24. 20 Maggio

  25. 23 Maggio

  26. 25 Maggio

  27. 27 Maggio

  28. 1 Giugno

  29. 3 Giugno

  30. 6 Giugno

  31. 8 Giugno

  32. 10 Giugno

  33. 15 Giugno

  34. 17 Giugno

Errata corrige

  1. DFS iterativa (lezione 30 Marzo)

    La DFS_visit iterativa data a lezione contiene degli errori. Sotto la nuova versione riveduta e corretta. Come sempre, è invocata all'interno di DFS(G) (nel libro).