Introduzione agli Algoritmi (Corso di Laurea in Informatica)

A.A. 2014-2015, secondo semestre, secondo canale

Docente: Irene Finocchi

Ricevimento: giovedì 14:00-15:30 durante il corso (speditemi mail prima di venire), per appuntamento al termine del corso. Ufficio: sede di Via Salaria, stanza 345/A. Tel: 06-49918426. E-mail: finocchi AT di.uniroma1.it

Esercitatore: Lorenzo Carlucci

Ricevimento: su appuntamento via e-mail. Ufficio: sede di Viale Regina Elena, Palazzina G II piano st. G26. Tel: 06-49255163. E-mail: carlucci AT di.uniroma1.it

Avvisi

  • APPELLO STRAORDINARIO APRILE 2016: l'appello si svolgerà giovedì 14 aprile alle ore 9:00 in Aula 13 (Via Scarpa), in concomitanza con la prova intermedia del canale MZ A.A. 2015-2016. E' obbligatoria la prenotazione su Infostud.

  • Risultati appello del 1 febbraio: per le verbalizzazioni, giovedì 25 febbraio ore 11:00 nel mio ufficio. Nel caso in cui non possiate venire in tale data contattatemi per email. Se non avete necessità di vedere il compito, posso verbalizzare direttamente io su Infostud: anche in questo caso contattatemi per email prima del 25 febbraio.

  • Appello del 1 febbraio: come indicato sulla pagina degli appelli nel sito del corso di studio in Informatica, l'appello del 1 febbraio gennaio si svolgerà in aula Gini (edificio di statistica) alle ore 9:00. Chi deve sostenere solo la seconda parte può presentarsi alle 10:30.

  • Risultati esame 13 gennaio 2016: gli studenti che devono verbalizzare, avendo superato entrambe le parti, possono presentarsi venerdì alle 14:30 per avere la firma sul certificato d'esame. Se invece non avete bisogno del certificato e non volete vedere il compito, posso verbalizzare direttamente io su Infostud: in tal caso fatemi sapere per email se posso procedere.

  • Appello del 13 gennaio: come indicato sulla pagina degli appelli nel sito del corso di studio in Informatica, l'appello del 13 gennaio si svolgerà in aula 13 alle ore 9:00. Chi deve sostenere solo la seconda parte può presentarsi alle 10:30.

  • RISULTATI APPELLO STRAORDINARIO: gli unici due studenti che hanno avuto una sufficienza all'appello straordinario sono Ornati (20 alla parte 1, parte 2 da rifare nella sessione invernale) e Samele (18 alla parte 1, parte 2 da rifare nella sessione invernale). Contattatemi per email per prendere un appuntamento nel caso in cui vogliate vedere gli errori commessi.

  • APPELLO STRAORDINARIO: l'esame si svolgerà il 5 novembre alle ore 9:00 in aula seminari (via Salaria 113, terzo piano). Gli studenti esonerati dalla prima parte devono presentarsi direttamente alle 10:30. E' obbligatoria la prenotazione su Infostud.

  • RISULTATI APPELLO DEL 3 SETTEMBRE 2015: risultati.
    • Poiché sarò all'estero per motivi di lavoro, gli studenti che hanno superato entrambe le parti (o coloro che vogliono vedere i propri errori) possono presentarsi giovedì 1 ottobre, alle ore 9:30, presso il mio ufficio. Manterrò l'appello aperto fino a tale data.
    • Chi ha superato solo una delle due parti può completare l'esame nell'appello di gennaio o febbraio (ultima data disponibile: dopo tale data il voto acquisito a una singola parte andrà perso).
    • Le studentesse Marcozzi e Scangella sono pregate di presentarsi all'orale alle 9:30.

  • APPELLO DEL 3 SETTEMBRE 2015: la prima parte dell'esame avrà inizio alle ore 9:30. Gli studenti esonerati dalla prima parte devono presentarsi direttamente alle 11:00. La prova per entrambi i canali si svolgerà in aula 1 di ingegneria. L'aula 13 non è disponibile contrariamente a quanto disposto in un primo momento e solo l'aula 1 di ingegneria è disponibile, esclusivamente di mattina.

  • RISULTATI APPELLO DEL 2 LUGLIO 2015: parte1, parte2. Gli studenti che hanno superato entrambe le parti (o coloro che vogliono vedere i propri errori) possono presentarsi venerdì 24 luglio, ore 9:30, presso il mio ufficio. Chi ha superato solo una delle due parti può completare l'esame nell'appello del 3 settembre.

  • VERBALIZZAZIONI APPELLO DEL 2 LUGLIO 2015: le verbalizzazioni avranno luogo nella settimana 20 - 24 luglio. Controllate il sito Web dopo il 15 luglio per ulteriori avvisi in merito.

  • APPELLO DEL 2 LUGLIO 2015: la prima parte dell'esame avrà inizio alle ore 9:30. Gli studenti esonerati dalla prima parte devono presentarsi direttamente alle 11:00. La prova per il canale 2 (MZ) si svolgerà in aula 13 di ingegneria, dove solitamente si tengono le lezioni del primo canale (l'aula 13 si trova in Via Antonio Scarpa 12, una traversa di Via del Castro Laurenziano).

Sorted descending Magnanini 6 2 7 6 insuff Samele 7 1 1 4 insuff Schifalacqua 13 0 8 - insuff Rampello 15 7 6 14 21 Manduca 11 7 3 1 18 parte 1. Rifare parte 2 il 27 gennaio

* RISULTATI APPELLO STRAORDINARIO NOVEMBRE 2014. Gli studenti che hanno ottenuto la sufficienza sono: Mohammad (voto finale 18), Paladini (voto finale 23), Provenzano (voto finale 19). Per la verbalizzazione contattare il docente.

  • Risultati appello Settembre 2014: gli studenti che hanno ottenuto la sufficienza sia sulla prima che sulla seconda parte del compito possono verbalizzare il giorno venerdì 3 ottobre alle ore 10:00 presso il mio studio. Nella stessa data sarà anche possibile visionare il compito per tutti gli studenti. Gli studenti che hanno ottenuto la sufficienza solo in una delle due parti possono completare l'esame, rifacendo lo scritto sulla parte insufficiente, nella sessione invernale.

  • Risultati appello Luglio 2014: gli studenti che hanno ottenuto la sufficienza sia sulla prima che sulla seconda parte del compito possono verbalizzare il giorno 24 luglio alle ore 15:00 presso il mio studio. Nella stessa data sarà anche possibile visionare il compito per tutti gli studenti. Gli studenti che hanno ottenuto la sufficienza solo in una delle due parti possono completare l'esame, rifacendo lo scritto sulla parte insufficiente, nell'appello di settembre.

  • PROVA INTERMEDIA E APPELLO STRAORDINARIO: risultati

ALTRI AVVISI

E' obbligatorio prenotarsi alla prova intermedia entro venerdì 11 aprile, seguendo questo link.

DATE D'ESAME:

  • scritto martedì 4 giugno aula V Mat, ore 9:00 (verbalizzazione ed eventuali orali: venerdì 7 giugno in Sala Riunioni, Via Salaria, ore 9:00);
  • scritto martedì 25 giugno aula V Mat, ore 9:00 (verbalizzazione ed eventuali orali: martedì 9 luglio in Sala Riunioni, Via Salaria, ore 9:00);
  • scritto martedì 10 settembre aula 1 NEC, ore 9:30 (verbalizzazione ed eventuali orali: data da definire, Via Salaria, stanza 345/A);

  • Auguri! tree.png

  • Preparazione all'esame: vi segnalo una corposa lista di esercizi utili per prepararsi all'esame. Gli esercizi (disponibili su questo sito Web o sul libro di testo) si riferiscono principalmente agli argomenti trattati nella seconda parte del corso. Per gli esercizi relativi alla prima parte, guardate il corrispondente avviso "Preparazione all'esonero". Buon lavoro!
    • Le esercitazioni 5 e 6 di Algoritmi I dell'A.A. 2008-2009 (a cura del Dott. Accattoli)
    • La dispensa 5 del Dott. Carlucci
    • Esercizio 3 degli appelli del 5 febbraio 2009, 22 gennaio 2009, 9 settembre 2008, 17 giugno 2008, 11 febbraio 2008, 28 gennaio 2008
    • Esercizio 4 dell'appello del 17 giugno 2008
    • Dal libro di testo: esercizi 3.4, 3.5, 6.1, 6.2, 6.3, 6.4, 6.5, 6.6, 6.10 (solo per alberi AVL), 7.1, 7.2, 7.3, 7.5.
    • Dal libro di testo: problemi 3.3, 3.4, 3.5, 3.6, 3.7, 3.8, 4.8, 4.9, 4.10, 4.11, 6.1, 6.2, 6.3, 6.4, 6.5, 6.6, 7.1, 7.2, 7.3, 7.4, 7.5.

  • Preparazione all'esonero: vi segnalo una corposa lista di esercizi utili per prepararsi all'esonero. Gli esercizi sono disponibili su questo sito Web (in alcuni casi ci sono anche le soluzioni) o sul libro di testo. Vi segnalo anche le dispense messe in rete dal Dott. Carlucci. Buon lavoro!
    • Le esercitazioni 1, 2, 3 e 4 di Algoritmi I dell'A.A. 2008-2009 (a cura del Dott. De Agostino)
    • Le esercitazioni 2, 3 e 4 di Algoritmi I dell'A.A. 2008-2009 (a cura del Dott. Accattoli)
    • Paragrafo 2 (solo punti 2 e 3) dell'esercitazione 5 di Algoritmi I dell'A.A. 2008-2009 (a cura del Dott. Accattoli)
    • Prove intermedie del 14 novembre 2007 e del 27 novembre 2008
    • Esercizio 2 dell'appello del 28 gennaio 2008
    • Esercizi 1 e 2 degli appelli dell'11 febbraio 2008, 17 giugno 2008, 9 settembre 2008, 22 gennaio 2009, 5 febbraio 2009
    • Dal libro di testo: esercizi 1.1, 1.2, 1.3, 2.1, 2.2, 2.3, 2.6, 2.7, 2.8, 2.9, 2.11, 3.1, 4.2, 4.3, 4.4, 4.5, 4.7, 4.9, 4.12, 4.13, 4.14
    • Dal libro di testo: problemi 1.3, 1.4, 2.2, 2.3, 2.4, 2.6, 2.8, 2.9, 2.10, 3.3, 4.1, 4.3, 4.4, 4.5, 4.7, 4.12, 4.13, 5.1, 5.2
-->

Orario lezioni

Giorno Ore Aula
Lunedì 8:45-10:15 Aula 1 - Aule L di Ingegneria
Giovedì 8:45-11:15 Aula 1 - Aule L di Ingegneria

Mailing list del corso

Iscrivetevi alla mailing list su Google Groups. La mailing list sarà usata per discutere gli esercizi assegnati durante il corso, per porre domande di interesse generale al docente ed all'esercitatore, per avvisare tempestivamente gli studenti di qualsiasi problematica inerente al corso.

Google Groups
Subscribe to Introduzione agli Algoritmi (Sapienza, Irene Finocchi)
Email:
Visit this group

Obiettivi e programma

In questo corso, attraverso lo studio di algoritmi e strutture dati classiche, acquisirete la capacità di analizzare problemi e progettare soluzioni algoritmiche corrette ed efficienti. Apprenderete inoltre varie tecniche utili per analizzare le prestazioni di un algoritmo tramite strumenti matematici rigorosi.

Formalmente non ci sono insegnamenti propedeutici. Sono comunque fondamentali le conoscenze impartite nel corso di Fondamenti di Programmazione ed una conoscenza di base di analisi matematica (soprattutto studio di funzioni e serie numeriche).

Per un buon esito dell'esame è fondamentale seguire le lezioni, svolgere gli esercizi assegnati settimanalmente e preparare l'esame di pari passo con lo svolgimento del corso.

Programma del corso

  • Introduzione all'algoritmica
    • Metodi per l'analisi delle risorse di calcolo utilizzate da algoritmi iterativi e ricorsivi [cap. 1 fino al par. 1.6]
    • Notazione asintotica [par. 2.2]
    • Caso peggiore e caso migliore. Cenni all'analisi nel caso medio [par. 2.3 e 2.4]
    • Soluzione di equazioni di ricorrenza: metodo di iterazione, metodo di sostituzione, teorema master (senza dimostrazione) [par. 2.5]
  • Strutture dati fondamentali
    • Pile [par. 3.1 e 3.2]
    • Code [par. 3.1 e 3.2]
    • Code con priorità: heap binari [par. 4.3.1]
  • Principali algoritmi di ricerca ed ordinamento
    • Ricerca sequenziale e binaria [par. 2.4]
    • Ordinamenti quadratici: bubbleSort, selectionSort, insertionSort [par. 4.2]
    • Ordinamenti ottimi: mergeSort, heapSort [par. 4.3 e 4.4]
    • QuickSort (solo analisi nel caso peggiore ed intuizione del caso medio) [par. 4.5]
    • Lower bound per il problema dell'ordinamento tramite confronti [par. 4.1]
    • Ordinamenti lineari: integerSort [par. 4.6]
  • Alberi
    • Rappresentazioni in memoria indicizzate e collegate [par. 3.3]
    • Visita per livelli [par. 3.3]
    • Visite in profondità [par. 3.3]
  • Dizionari
    • Alberi binari di ricerca: definizione ed operazioni fondamentali [par. 6.1]
    • Alberi AVL: fattore di bilanciamento, rotazioni, operazioni fondamentali [par. 6.2]

Per tutti gli algoritmi presentati nel corso si richiede la conoscenza delle dimostrazioni di correttezza e complessità.

Per maggiori informazioni guardate anche il diario delle lezioni.

Modalità e date d'esame

L'esame consiste in una prova scritta che conterrà:

  • esercizi di ragionamento non svolti precedentemente a lezione (e.g., analisi del tempo di esecuzione di un frammento di codice o progettazione di nuovi algoritmi);
  • domande tipiche da esame orale, tese a verificare la conoscenza e la comprensione di base della materia (e.g., definizioni, dimostrazioni, strutture dati e algoritmi presentati durante il corso).

Nella prova scritta non sarà possibile utilizzare libri, appunti o dispense in formato cartaceo né elettronico.

In generale, il superamento della prova scritta permette di verbalizzare il voto conseguito. Il docente ha però facoltà di richiedere un colloquio orale suppletivo in casi specifici tra cui: sufficienza non piena allo scritto, sospetto di copiatura, votazione alta (con possibilità di lode), dubbi nell'interpretazione del compito.

Prova intermedia. E' prevista una prova intermedia nella settimana di interruzione della didattica. La prova riguarderà tutti gli argomenti svolti fino alla data della prova stessa. La sufficienza ottenuta alla prova intermedia è valida fino all'ultimo appello dell'anno accademico di riferimento. La prova intermedia è anch'essa strutturata in esercizi di ragionamento e domande di comprensione.

Data prova intermedia: martedì 14 aprile 2015, data soggetta a conferma (da parte della segreteria didattica).

Appelli. Ci saranno cinque appelli, rispettivamente due nella sessione estiva (giugno-luglio), uno in settembre, due nella sessione invernale (gennaio- febbraio). Tutti gli appelli saranno divisi in due parti. Lo studente potrà sostenere tutto l'esame oppure affrontare una prova sugli stessi argomenti di quella intermedia in un appello e completare la prova scritta in un appello successivo.

Date appelli: da definire da parte della segreteria didattica. Per informazioni ufficiali su date, orari e luoghi degli appelli fate sempre riferimento al calendario pubblicato dalla segreteria didattica nelle pagine Web del corso di laurea.

Voto. Il voto finale verrà incrementato di un punto per chi termina nella sessione estiva avendo superato la prova intermedia, e di mezzo punto per chi conclude l'esame nella sessione estiva (senza prova intermedia).

Prenotazioni. Per partecipare alle prove scritte (inclusa quella intermedia) è obbligatoria la prenotazione. Sarà possibile prenotarsi agli appelli d'esame tramite infostud, e alla prova intermedia tramite twiki.

Libro di testo

DFI08.jpg C. Demetrescu, I. Finocchi, G.F. Italiano, "Algoritmi e Strutture Dati", 2/ed. McGraw-Hill, 2008.

Raccomando l'uso della seconda edizione del libro. Nell'area studenti relativa al libro, troverete animazioni di alcuni degli algoritmi e delle strutture dati presentati in classe.

Un utile libro di consultazione è il seguente: T.H. Cormen, C.E. Leiserson, R.L. Rivest e C. Stein, "Introduction to Algorithms", 2/ed. Mit Press e McGraw-Hill, 2001.

Diario delle lezioni

Diario delle lezioni A.A. 2014-2015 ed esercizi di riepilogo assegnati periodicamente.

Esercizi (svolti)

Risolvere esercizi è indispensabile per l'apprendimento e per il superamento di questo esame. Per ogni esercizio, cercate sempre di elaborare una soluzione personale. Leggete le soluzioni (eventualmente) fornite di seguito solo in un secondo momento, al fine di verificare la correttezza del vostro approccio.

Soluzioni di alcuni degli esercizi del libro di testo

Appunti di approfondimento ed esercizi svolti a cura del Dott. Carlucci

  • Appunti 1: Notazione Asintotica, metodo algebrico e metodo analitico.
  • Appunti 2: Notazione Asintotica, Logaritmi, Polinomi, Esponenziali, Fattoriali.
  • Appunti 3: Logaritmi, polinomi, esponenziali. Numeri di Fibonacci.
  • Appunti 4: Correzione degli Esercizi di Riepilogo (A).
  • Appunti 5: Ricerca Binaria, Bubble Sort.
  • Appunti 6: Ricerca binaria ricorsiva, esercizi di riepilogo.
  • Appunti 7: Quick Sort.
  • Appunti 8: Correzione esercizi 2 e 3 dell'esonero A.A. 2009-2010.
  • Appunti 9: Counting Sort. Esercizi.
  • Appunti 10: Esercizi di riepilogo.
  • Appunti 11: Alberi.
  • Appunti 12: AVL e ABR.

Compiti d'esame

Esami di Introduzione agli Algoritmi, A.A. 2013-2014

Esami di Introduzione agli Algoritmi, A.A. 2012-2013

Esami di Introduzione agli Algoritmi, A.A. 2011-2012

Esami di Introduzione agli Algoritmi, A.A. 2010-2011

Esami di Introduzione agli Algoritmi, A.A. 2009-2010

Esami di Introduzione agli Algoritmi, A.A. 2008-2009

Esami di Algoritmi I, A.A. 2008-2009

Esami di Algoritmi I, A.A. 2007-2008



This topic: Intro_algo/EO > WebHome
Topic revision: r229 - 2016-03-17 - IreneFinocchi
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback