Strumenti Utente

Strumenti Sito


informatica:all-b:algob_10:start

Questa è una vecchia versione del documento!


Algoritmica e Laboratorio - Corso B


News

Risultati dello scritto del 9.9.2011:

   441800   suff
   463763   ins
   464879   20
   466905   venire a vedere la correzione
   467101   20
   467641   ins
   468087   suff
   470199   25
   473029   22

Risultati dello scritto del 7.7.2011:

   422257   ins
   441761   ins
   464587   ins
   465077   22
   466759   27
   466905   ins
   467101   ins
   470199   ins

Hanno superato il laboratorio dell'8.7.2011:

 
   464879
   466759
   

Risultati dello scritto del 21.6.2011:

   422257   ins
   441389   20
   441800   ins
   451351   20
   453089   suff
   457989   20
   463763   ins
   464587   ins
   465169   ins
   466089   24
   466905   ins
   471565   25
   473029   ins

Hanno superato il laboratorio del 22.6.2011:

 
   439043
   451051
   451351
   452068
   452093
   452853
   453845
   454089
   454964
   460073
   464229
   464247
   464561
   466089
   468405
   468827
   471565
   472131

Risultati dello scritto del 6.6.2011:

   437435   21
   441800   ins
   444043   suff
   444151   suff
   451051   21
   451449   27
   452068   24
   452826   24
   452853   21
   453089   ins
   453845   21
   454089   suff
   457989   ins
   463763   ins
   464091   24
   464229   30-
   464247   27
   464433   suff
   464561   24
   464587   ins     
   464879   suff
   464885   suff
   466759   suff
   466905   ins
   468405   suff
   468827   suff
   469299   27
   472131   27

Hanno superato il laboratorio del 15.6.2011:

   437666
   442988
   443136
   451842
   456464
   456796
   459248
   464091
   466632
   466766
   469528
   421500
   437435
   444151
   451742
   464262
   467680
   469299
   471062
   471122

Informazioni Generali

Docente: Roberto Grossi

Impegno: 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio.


Ricevimento studenti
Grossi ore giorno Stanza 361, Dipartimento di Informatica


Il corso consiste ogni settimana di 3 lezioni di didattica frontale in aula e di 1 esercitazione in laboratorio nella quale le nozioni apprese in classe verranno sperimentate realizzando in C gli algoritmi corrispondenti.

Orario delle Lezioni
Giorno Orario Aula (Corso B) Tipologia
Lunedì 9-11 A Teoria
Martedì 9-11 A Teoria
Mercoledì 9-11 A Teoria
Giovedì 9-11 H Laboratorio


Obiettivi del Corso

Al Kowarizmi L'obiettivo del corso è quello di introdurre strutture dati e tecniche algoritmiche (di base) che consentano allo studente la risoluzione di problemi su sequenze, liste, alberi e grafi, in modo efficiente in tempo e/o spazio. Si discuteranno inoltre alcune tecniche analitiche per la valutazione delle prestazioni degli algoritmi, o delle limitazioni inerenti del calcolo.

Il corso prevede una intensa attività di laboratorio che porterà gli studenti a sperimentare in linguaggio C le nozioni e le tecniche algoritmiche apprese in classe.


Modalità di esame

L'esame consiste di tre prove:

  • Una prova in laboratorio che verifica la capacità dello studente di realizzare in C gli algoritmi di base visti in classe, risolvendo semplici problemi su array, liste, alberi e grafi. Tale prova è da intendersi come un test di idoneità il cui superamento permette allo studente di essere ammesso a sostenere la prova scritta.
  • Una prova scritta con esercizi atti a valutare l'apprendimento delle nozioni teoriche e la capacità di “problem solving” dello studente. Tale prova viene valutata in trentesimi, e si intende superata se la valutazione è maggiore o uguale a 18, nel qual caso lo studente è ammesso a sostenere la prova orale.
  • Una prova orale sul programma del corso, la cui valutazione è in trentesimi e tiene in considerazione il risultato riportato dallo studente nella prova scritta.

IMPORTANTE per gli studenti della Classe 26: possono sostenere la sola prova scritta di AlL come scritto dell'esame di Algoritmica (vecchio corso) e devono contattare la prof. Pagli per la verbalizzazione; la prova di laboratorio LLS dovrà essere svolta con il dott. Gervasi.

Esercizi e testi di esame

Un centinaio di esercizi sono reperibili presso le vecchie pagine del corso

http://www.di.unipi.it/~grossi/ALG/

http://www.di.unipi.it/didadoc/asd1/page6.html


Appelli di esame Note
09.09.2011 ore 15:30 (scritto) 12.09.2011 ore 14:30 (prova di laboratorio)

Libro di testo

  • P. Crescenzi, G. Gambosi, R. Grossi. Strutture di dati e algoritmi: progettazione, analisi e visualizzazione. Addison-Wesley, 2006.
    • CAPITOLI DA STUDIARE PER L'ESAME: Capitolo 1 (tutto), Capitolo 2 (tranne i paragrafi 2.5.2, 2.6), Capitolo 3 (tranne i paragrafi 3.2, 3.4.2, 3.4.3), Capitolo 4 (tranne i paragrafi 4.2, 4.3.2, 4.3.3, 4.3.4, 4.4), Capitolo 5 (tranne i paragrafi 5.5 e 5.6.2), Capitolo 6 (solo il paragrafo 6.1), Capitolo 7 (tranne i paragrafi 7.2 e 7.5.2), Capitolo 8 (tutto), Capitolo 9 (solo il paragrafo 9.1).
    • Per approfondimenti ed errata: http://www.algoritmica.org/sda/pmwiki.php
  • Per il laboratorio: B.W. Kernighan, D.M. Ritchie. Il Linguaggio C, Pearson-Prentice Hall, seconda edizione, 2008.

Materiale per il Laboratorio

  • Prerequisito: Conoscenza approfondita della programmazione C per ciò che concerne gli operatori (aritmetici e relazionali), il flusso del controllo (If-then-else, while, for), le funzioni, gli array e i puntatori. Quindi i capitoli 1-5 del libro “Il Linguaggio C”, B.W. Kernighan e D.M. Ritchie, Pearson-Prentice Hall, seconda edizione, 2008.
  • Strumenti per la programmazione: Un editore testuale (tipo Emacs), e il compilatore gcc, sono sufficienti per apprendere e testare le varie nozioni algoritmiche e di coding che verranno discusse in Laboratorio. I programmatori più esperti potranno eventualmente utilizzare un framework di sviluppo come Eclipse esteso con il suo plug-in Eclipse C/C++ Development Tooling. Per chi si trova a operare sotto Windows suggeriamo il compilatore e il debugger disponibili con MinGW, e consigliamo di istallare i 3 componenti suddetti secondo la sequenza: Eclipse-MinGW-CDevTool. Il consiglio è però quello di adoperare la combinazione minimale editor+gcc al fine di non perdersi nei meandri e nelle opzioni dei vari tools (non necessari per AIL), per concentrarsi soltanto sugli aspetti di coding degli algoritmi.

FAQ

(ancora non attivo)

Programma del corso

  1. Breve introduzione a problemi computazionali, indecidibilità, e trattabilità (P, NP, NPC, EXP-TIME).
  2. Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, caso pessimo e caso medio.
  3. Limiti del calcolo: albero di decisione, limiti superiori e inferiori.
  4. Divide-et-impera, Relazioni di ricorrenza, Teorema fondamentale.
  5. Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento.
  6. Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort.
  7. Ordinamento di interi: Counting sort, Radix Sort.
  8. Ordinamento di stringhe.
  9. Problema dei matrimoni stabili e sottosequenza di somma massima.
  10. Programmazione dinamica: LCS, Partizione e Zaino
  11. Generazione di combinazioni e permutazioni
  12. Greedy: Huffman e Zaino
  13. Strutture dati auto-aggiustanti: MTF. Analisi ammortizzata e competitiva.
  14. Alberi: rappresentazione e visite.
  15. Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto), trie.
  16. Strutture dati randomizzate: Skip List.
  17. Algoritmi randomizzati: Quicksort, Karp-Rabin.
  18. Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
  19. Grafi II: albero di copertura minimo, cammini minimi, componenti (fortemente) connesse.

Registro Elettronico delle Lezioni

Registro del Laboratorio

Data Argomento Rif. Biblio
07/3/11 Laboratorio: Basi del C e di compilazione sotto Unix. Struttura base del programma, blocchi condizionali e cicli, input/output, array. Cap. 2-3, 7.1-7.4 di [KR]. Lucidi}
08/3/11 Laboratorio: Ripasso e esercizi su funzioni e puntatori. Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi
10/3/11 Laboratorio: Ripasso e esercizi su passaggio dei parametri. Lucidi
10/3/11 Laboratorio: Ripasso e esercizi su allocazione dinamica della memoria e gestione di stringhe. Lucidi
24/3/11 Laboratorio: Redirezione dell'input e timing di un programma. Problema del sottoarray di somma massima. Test Soluzioni
31/3/11 Laboratorio: Insertion Sort su Interi e Stringhe. Per casa: Implementare Merge Sort e Ricerca Binaria. Esercizi Soluzioni
07/4/11 Laboratorio: QuickSort su Interi e Stringhe. Esercizi Soluzioni
14/4/11 Laboratorio: Qsort su Interi e Stringhe. Esercizi Soluzioni
28/4/11 Laboratorio: Le struct in C e esercizi con le liste. Lucidi Esercizi
12/5/11 Laboratorio: Alberi Binari di Ricerca. Esercizi Soluzioni
19/5/11 Laboratorio: Funzioni Hash. Esercizi Esercizi Aggiuntivi Liste Soluzione
26/5/11 Laboratorio: Simulazione della prova di esame. Testo
informatica/all-b/algob_10/start.1315735931.txt.gz · Ultima modifica: 11/09/2011 alle 10:12 (8 anni fa) da Roberto Grossi