Algoritmi I (Corso di Laurea in Informatica)

A.A. 2008-2009, primo semestre

Docente: Irene Finocchi

Esercitatore: Sergio De Agostino



Avvisi

  • Scritto del 10 settembre: risultati. Orali e verbalizzazioni mercoledì 16 settembre, ore 9:00, in Sala Riunioni (via Salaria). Raccomando di essere presenti e puntuali: non sarà possibile verbalizzare l'esame in altre date.

  • Scritto del 6 luglio: risultati! Orali e verbalizzazioni venerdì 17 luglio, ore 9:00, in Aula Seminari (via Salaria). Raccomando di essere presenti e puntuali: sarò in viaggio a partire da domenica e non sarà possibile verbalizzare l'esame in altre date. Nel caso vi sia stato proposto di sostenere l'orale ma vogliate rinunciare, vi prego di comunicarmelo via e-mail.

  • Prenotazioni: come già sapete, a partire dalla prossima sessione d'esame le prenotazioni andranno effettuate su InfoStud. Gli studenti che hanno formalmente richiesto ai docenti di Introduzione agli Algoritmi (Fachini, Finocchi, Silvestri) di poter sostenere l'esame di Introduzione agli Algoritmi al posto di Algoritmi I non potranno prenotarsi agli esami del 6 luglio e 10 settembre: dovranno invece usufruire degli appelli previsti per Introduzione agli Algoritmi (23 giugno, 14 luglio e 15 settembre). Se avete già sostenuto l'esame di Algoritmi I e dovete solo verbalizzare il voto, prenotatevi ad uno dei due appelli di Algoritmi I rimanenti e presentatevi nella data prevista per l'orale. Le prenotazioni sono obbligatorie. La ricevuta di prenotazione va stampata e portata all'esame (sia il giorno dello scritto che quello dell'orale). I periodi di prenotazione sono i seguenti:
    • Appello del 6 luglio: dal 29 maggio fino al 2 luglio
    • Appello del 10 settembre: dal 30 luglio fino all'8 settembre

  • Risultati scritto del 5 febbraio: esonerati, esame completo. Orali e verbalizzazioni domani 12 febbraio, come indicato sul calendario degli esami.

  • Soluzioni: è in rete uno sketch della soluzione degli esercizi 1 e 2 dello scritto del 22 gennaio.

  • Risultati scritto del 22 gennaio: esonerati, esame completo. Orali e verbalizzazioni il 12 febbraio, come indicato sul calendario degli esami.

  • Esami della prossima sessione: sono in rete su twiki i fogli di prenotazione per gli appelli del 22 gennaio e del 5 febbraio. Sarà possibile prenotarsi fino alle ore 24:00 rispettivamente del 20 gennaio e del 3 febbraio. Possono partecipare agli scritti (che valgono anche come secondo esonero per chi abbia superato la prova intermedia) solo gli studenti del corso di laurea in Informatica. Vi invito a prenotarvi all'appello di febbraio solo nel caso in cui non abbiate consegnato o non vogliate presentarvi all'appello di gennaio (i due scritti sono mutuamente esclusivi).

  • First Annual SIGMOD Programming Contest: se avete buone competenze implementative e vi interessano gli algoritmi, fatemi sapere! Si tratta di una iniziativa molto seria e interessante, organizzata da SIGMOD (ACM Special Interest Group on Management of Data) e MIT (Massachusetts Institute of Technology), e sponsorizzata da Microsoft e Vertica Systems. C'è eventualmente la possibilità di creare un team in collaborazione con studenti di Ingegneria Informatica.

  • Prova intermedia: la prova sarà alle 14:00 in Aula 1 NEC (anziché in Aula 3 di Fisica).

  • Orario lezioni: a partire da lunedì 17 novembre le lezioni inizieranno alle 14:00, anziché alle 14:30.

  • Giovedì 13 novembre: eccezionalmente, la lezione (esercitazione) si terrà dalle 16:00 alle 18:00, per via di uno scambio effettuato con il docente di Laboratorio di Sistemi Operativi (Prof. Verola).

  • Prova intermedia e riorganizzazione lezioni: le prove intermedie sono state spostate nella settimana dal 24 al 28 novembre. Ho aggiornato il diario delle lezioni e delle esercitazioni di conseguenza. La prova di Algoritmi I si terrà giovedì 27 novembre dalle 14:00 alle 16:00. Rimane valido il foglio di prenotazione che avevo già creato: non c'è quindi bisogno di riprenotarsi se l'avete già fatto.

  • Mobilitazione e prossime lezioni: il Consiglio di Facoltà del 27/10/08 ha approvato una mozione-delibera che sospende l'attività didattica dal 28 ottobre al 3 novembre (inclusi). Salvo ulteriori avvisi, la prossima lezione di Algoritmi I si svolgerà quindi giovedì 6 novembre. E' probabile che prossimamente sarà delineato un riassetto del calendario didattico che ci permetterà di recuperare parte delle lezioni perse. Metterò l'avviso non appena le informazioni saranno disponibili.

  • Lezione del giorno lunedì 27 ottobre 2008: a causa delle manifestazioni in corso, e poiché l'edificio di Fisica risulta essere ancora occupato, la lezione di lunedì 27 ottobre è annullata.

  • Esercitazione del giorno giovedì 23 ottobre 2008: l'esercitazione è annullata, come deliberato dal Consiglio di Area Didattica in Informatica al fine di permettere agli studenti di partecipare all'assemblea indetta dalle 14.00 alle 18.00 in Aula I NEC. Ulteriori informazioni a questo link.

  • Prova intermedia: giovedì 27 novembre. La prova si svolgerà nell'aula in cui si tengono le lezioni, inizierà alle ore 14:00 (anziché alle 14:30 come le lezioni) e durerà due ore. Possono partecipare solo gli studenti del corso di laurea in Informatica. Il foglio di prenotazione è in rete su twiki a questo link. Sarà possibile prenotarsi fino alle ore 24:00 di lunedì 24 novembre 2008.

  • Data inizio corso: lunedì 22 settembre 2008, come da calendario didattico.

Orari & luoghi

Lezioni: ogni lunedì e giovedì, dalle 14:00 alle 16:00, in Aula III di Fisica (Nuovo Edificio). Potete trovare la suddivisione tra lezioni ed esercitazioni al link Diario delle lezioni.

Anche se la frequenza del corso non è obbligatoria, consiglio fortemente di seguire sia le lezioni che le esercitazioni: il corso richiede infatti di apprendere come applicare idee e tecniche che, seppur semplici, non si prestano ad una riduzione in metodi o ricette meccaniche.

Ricevimento

  • Irene Finocchi: martedì 11:00-13:00 durante il corso (speditemi mail prima di venire), per appuntamento al termine del corso. Ufficio: Dip. di Informatica (sede di Via Salaria, 113), stanza 311. Telefono: 06 4991 8428. E-mail: finocchi AT di.uniroma1.it
  • Sergio De Agostino: martedì 15:00-17:00. Ufficio: Dip. di Informatica (sede di Via Salaria, 113). Telefono: 06 4991 8529 . E-mail: deagostino AT di.uniroma1.it

Obiettivi del corso & propedeuticità

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.

Non ci sono insegnamenti propedeutici. Si richiedono comunque le conoscenze impartite nei corsi di Programmazione 1 e 2 ed una conoscenza di base di analisi matematica (soprattutto studio di funzioni ed equazioni numeriche).

Informazioni ufficiali sul corso di Algoritmi I nelle pagine Web dei corsi di studio in Informatica.

Modalità & date d'esame

L'esame consiste in una prova scritta obbligatoria ed una eventuale prova orale: l'orale può essere richiesto dal docente nel caso di voti incerti o dallo studente per tentare di migliorare il voto ottenuto allo scritto. Non è in nessun caso possibile svolgere l'orale nel caso in cui non sia stato superato lo scritto.

Poiché l'orale non è obbligatorio, la prova scritta includerà anche domande relative agli algoritmi e alle dimostrazioni spiegate in classe. Questo implica che durante le prove scritte non è possibile consultare libri, appunti, dispense (né tantomeno foglietti o vicini).

Prove intermedie: è prevista una prova scritta intermedia il giorno giovedì 27 novembre 2008, 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 solo per i primi due appelli, mutuamente esclusivi, che si svolgeranno al termine del corso (sessione di gennaio/febbraio): in tali appelli, chi abbia superato la prova intermedia potrà scegliere di sostenere solo la prova relativa alla seconda parte o di risostenere la prova interamente (nel caso non sia soddisfatto del voto ottenuto). In tutti gli appelli successivi lo scritto dovrà essere svolto per intero. Il voto finale verrà incrementato del 5% per coloro che avranno superato la prova intermedia e la prova finale relativa alla seconda parte del corso.

Per partecipare alle prove scritte (inclusa quella intermedia) è obbligatoria la prenotazione.

Appelli: ci saranno quattro appelli, di cui due mutuamente esclusivi al termine del corso (gennaio e febbraio), uno in giugno o luglio, ed uno in settembre. Per informazioni ufficiali su date, orari e luoghi degli appelli (scritti, orali & verbalizzazioni), fate riferimento al calendario pubblicato dalla segreteria didattica nelle pagine Web del corso di laurea.

Visione dei compiti: nelle date previste per gli orali è possibile visionare il compito scritto, anche nel caso in cui non sia stata ottenuta la sufficienza.

Libri di testo

Il libro di testo è il seguente:

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

Raccomando l'uso della seconda edizione del libro: contiene numerosi aggiornamenti rispetto alla prima, e molti più esercizi e problemi. Nell'area studenti relativa al libro, troverete animazioni di alcuni degli algoritmi e delle strutture dati presentati in classe e semplici quiz a risposta multipla.

Altri utili libri di consultazione sono:

  • [A99] M. H. Alsuwaiyel, "Algorithms - Design Techniques and Analysis", Word Scientific, 1999.
  • [CLRS01] T.H. Cormen, C.E. Leiserson, R.L. Rivest e C. Stein, "Introduction to Algorithms", 2/ed. Mit Press e McGraw-Hill, 2001.
  • [DFFI07] C. Demetrescu, U. Ferraro Petrillo, I. Finocchi, G.F. Italiano, "Progetto di Algoritmi e Strutture Dati in Java". McGraw-Hill, 2007.
  • [KT06] R. Kleinberg ed E. Tardos. Algorithm Design. Addison Wesley, 2006.

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.

Esercizi assegnati in classe

  1. Sia Fib un array di n interi, inizializzati tutti a 0. Progettare un algoritmo che memorizzi in Fib[i] l'i-esimo numero di Fibonacci Fi, per ogni i in [1,n]. L'algoritmo, a partire dal calcolo di Fn, deve operare ricorsivamente secondo la seguente strategia: a) se Fib[i-1]=0, calcola Fib[i-1] ricorsivamente; b) se Fib[i-2]=0, calcola Fib[i-2] ricorsivamente; c) memorizza in Fib[i] la somma Fib[i-1]+Fib[i-2].
    • Dare lo pseudocodice dell'algoritmo
    • Disegnare l'albero della ricorsione per il calcolo di F6
    • Analizzare il tempo di esecuzione dell'algoritmo
    • Ripetere i punti precedenti assumendo che i passi a) e b) siano invertiti
  2. Il Professor Bifolcacci sostiene di saper sfruttare la relazione di ricorrenza che definisce i numeri di Fibonacci per ottenere un algoritmo ricorsivo con tempo di esecuzione subesponenziale. In particolare, l'algoritmo del Professor Bifolcacci prima calcola ricorsivamente Fn-2 e Fn-3, e poi restituisce Fn=2Fn-2+Fn-3.
    • Dimostrare che l'algoritmo è corretto
    • Impostare una relazione di ricorrenza per il tempo di esecuzione
    • Dimostrare che il professore ha commesso un errore: il tempo di esecuzione è ancora esponenziale! E' sufficiente dare una minorazione al tempo di esecuzione, ovvero far vedere che il tempo di esecuzione è Omega(g(n)), dove g(n) è una opportuna funzione con crescita esponenziale.
  3. Fornire un'implementazione ricorsiva dell'algoritmo per la ricerca dei duplicati visto in classe (e discusso anche nel capitolo 1 del libro [DFFI07]) ed analizzarne il tempo di esecuzione. Risolvere l'equazione di ricorrenza sia tramite l'albero della ricorsione che per iterazione.
  4. Proporre ed analizzare un algoritmo per risolvere il seguente problema: date due matrici A e B, rispettivamente di dimensione (n x k) e (k x m), calcolare la matrice prodotto A x B.
  5. Verificare che i confronti tra elementi sono l'operazione dominante negli algoritmi InsertionSort, SelectionSort e MergeSort. A tale scopo, calcolate il numero di linee di codice mandate in esecuzione nelle implementazioni proposte e mostrate che tale numero è Theta(numero di confronti).
  6. Nella implementazione del MergeSort proposta sul libro di testo, rimpiazzate la scelta dell'indice m come segue: m=(2i+f-2)/3. Con tale scelta, l'array da ordinare viene partizionato in due sottoarray, il secondo dei quali è grande il doppio del primo. Disegnate l'albero della ricorsione ed analizzate il numero di confronti eseguiti dall'algoritmo risultante. Per semplificare i calcoli, nell'analisi potete assumere che n sia una potenza di 3.
  7. Nella implementazione del MergeSort proposta sul libro di testo, rimpiazzate la scelta dell'indice m come segue: m=min { (i+f)/2, i+3 }. Con tale scelta, se c'e' un numero di elementi sufficiente, l'array da ordinare viene partizionato in due sottoarray, il primo dei quali ha dimensione 4. Disegnate l'albero della ricorsione ed analizzate il numero di confronti eseguiti dall'algoritmo risultante.
  8. Fornire un'implementazione iterativa della procedura fixHeap.
  9. Analizzare, impostando e risolvendo un'equazione di ricorrenza, il numero di confronti eseguiti dall'implementazione ricorsiva della procedura fixHeap nel caso in cui l'heap sia completo fino all' ultimo livello. Come può essere generalizzata la ricorrenza per heap qualsiasi?
  10. Dare una procedura ricorsiva per l' ordinamento a bolle e analizzarne la complessità.
  11. Proporre un algoritmo ricorsivo per verificare se un albero binario T ai cui nodi sono associate chiavi prese da un universo totalmente ordinato è un albero binario di ricerca. Analizzare il tempo di esecuzione nel caso peggiore e nel caso migliore. Ripetere l'esercizio proponendo un algoritmo iterativo.
  12. Implementare le classiche operazioni su un albero binario di ricerca (search, insert, max, pred, delete) assumendo che l'albero sia rappresentato tramite vettore-padri. Discutere i tempi di esecuzione delle implementazioni proposte.
  13. Considerare le cinque rappresentazioni di alberi viste in classe: vettore padri, vettore posizionale, puntatori ai figli, lista di figli, primo figlio - fratello successivo. Proporre algoritmi di conversione da una rappresentazione all'altra. Discutere sotto quali ipotesi gli algoritmi proposti operano correttamente (alberi generici, alberi d-ari con d fissato) ed analizzare i tempi di esecuzione delle implementazioni proposte.

Soluzioni di alcuni degli esercizi del libro di testo

Esercitazioni A.A. 2008-2009 (a cura del Dott. De Agostino)

Esercitazioni A.A. 2007-2008 (a cura del Dott. Accattoli)

Appunti ed esercitazioni di Anni Accademici precedenti al 2007-2008

Compiti d'esame

Tracce d'esame A.A. 2008-2009

Tracce d'esame A.A. 2007-2008

Tracce d'esame di Anni Accademici precedenti al 2007-2008

Programma dettagliato del corso

Trovate a questo link il programma definitivo per l'A.A. 2008-2009, con riferimenti bibliografici.

Diario delle lezioni

Settembre 2008
Lunedì Martedì Mercoledì Giovedì Venerdì Sabato Domenica
01 02 03 04 05 06 07
08 09 10 11 12 13 14
15 16 17 18 19 20 21
22
Introduzione al corso. Un esempio "giocattolo": i numeri di Fibonacci. Algoritmo ricorsivo, albero della ricorsione.
23 24 25
Analisi algoritmo ricorsivo. Algoritmi iterativi. Occupazione di memoria. Notazione asintotica.
26 27 28
29
Algoritmo basato su potenze di matrice. Soluzione ricorrenze per iterazione. Un nuovo esempio: ricerca di duplicati.
30          

Ottobre 2008
Lunedì Martedì Mercoledì Giovedì Venerdì Sabato Domenica
    01 02
Esercitazione: Fibonacci e ricerca dei duplicati ricorsiva
03 04 05
06
Caso peggiore e migliore. Analisi ricerca di duplicati. Insertion e selection sort: pseudocodice e correttezza.
07 08 09
Tempo di esecuzione Insertionsort e Selectionsort. Mergesort (con analisi).
10 11 12
13
Heap: altezza, vettore posizionale, fixHeap, cancellazione max, costruzione. Esercizi notazione asintotica.
14 15 16
Esercitazione: Bubblesort iterativo e ricorsivo, variante mergesort
17 18 19
20
Heapsort. Analisi heapify. Teorema master: enunciato ed esempi d'uso.
21 22 23
Esercitazione annullata per assemblea di studenti e docenti (14 - 18 Aula I NEC)
24 25 26
27
Sospensione didattica per protesta Legge 133
28 29 30
Sospensione didattica per protesta Legge 133
31    

Novembre 2008
Lunedì Martedì Mercoledì Giovedì Venerdì Sabato Domenica
          01 02
03
Sospensione didattica per protesta Legge 133
04 05 06
Esercitazione: Relazioni di ricorrenza, ricerca binaria, analisi fixheap
07 08 09
10
Metodo di sostituzione. Quicksort: partition in loco, analisi caso peggiore e migliore, intuizione caso medio.
11 12 13
Esercitazione: esercizio 2.9, problemi 2.9 e 2.10, esercizio 4.12, esercizio 7 assegnato in classe
14 15 16
17
Lower bound ordinamento. Ordinamenti lineari: integerSort e bucketSort. Problema 4.12.
18 19 20
Esercizi di preparazione alla prova intermedia.
21 22 23
24
Ore cedute al corso di Laboratorio di Sistemi Operativi
25 26 27
Prova Intermedia
28 29 30

Dicembre 2008
Lunedì Martedì Mercoledì Giovedì Venerdì Sabato Domenica
01
ABR: alberi binari di ricerca. Rappresentazioni di alberi: indicizzate e collegate.
02 03 04
Esercitazione: soluzioni prova intermedia
05 06 07
08
Festività Immacolata Concezione
09 10 11
Alberi AVL: definizioni, delimitazione altezza, rotazioni, operazione insert.
12 13 14
15
AVL: operazione delete. Visite di alberi: visita generica, in profondità, per livelli. Esercizi.
16 17 18
Definizione di grafo. Grafi orientati. Cammini e cicli. Rappresentazioni in memoria.
19 20 21
22 23 24 25 26 27 28
29 30 31        

Gennaio 2009
Lunedì Martedì Mercoledì Giovedì Venerdì Sabato Domenica
      01 02 03 04
05 06 07 08
Visite di grafi non orientati: visita generica, analisi tempo di esecuzione, visita BFS, proprietà dell'albero BFS.
09 10 11
12
Visita DFS ricorsiva e iterativa, proprietà dell'albero DFS. Visite di grafi orientati. Calcolo componenti connesse.
13 14 15
Esercitazione: Esercizi su grafi e alberi AVL. Grafi bipartiti.
16 17 18
19
Esercizi di preparazione all'esame: grafi e alberi AVL.
20 21 22 23 24 25
26 27 28 29 30 31  

Diario delle lezioni in formato testo.


Edit | Attach | Watch | Print version | History: r170 < r169 < r168 < r167 < r166 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r170 - 2009-09-14 - IreneFinocchi






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback