Indice

Algoritmica e Laboratorio - Corso di recupero

Informazioni Generali

Docenti: Linda Pagli,Giulio Pibiri

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

Semestre: primo.

Ricevimento studenti: dopo ogni lezione oppure su appuntamento.

AVVISO

su http://mediateca.unipi.it sono a disposizione disposizione le video-lezioni dell'anno 2015/2016. Bisogna registrarsi con le credenziali di ateneo.

NUOVO AVVISO

RISULTATI APPELLO STRAORDINARIO DEL 31/10/2016, Corsi A e B

Risultati

Visione scritti e orali su appuntamento.

NUOVO AVVISO

All'indirizzo http://dijkstra.di.unipi.it/#/lessons i compiti degli appelli passati (a.a. 2015-16) sono adesso disponibili.

Anni accademici precedenti

Orario Lezioni

Orario delle Lezioni
Giovedì 14-18 N1
Venerdì 14-18 M

Obiettivi del Corso

Il corso è rivolto a studenti, che per motivi di vario tipo, non sono riusciti a superare il corso regolare di algoritmi e laboratorio il primo anno di studi. Il corso è costituito da brevi lezioni riassuntive sugli argomenti di base e da esercitazioni pratiche in cui si discuteranno e risolveranno problemi di vario tipo, definendo limiti inferiori, confrontando soluzioni diverse, analizzando correttezza e complessità. Il corso ha una natura più pratica che teorica e verrà organizzato anche in funzione dei fruitori. Agli studenti che hanno intenzione di frequentarlo sarà richiesta un partecipazione attiva. Consiste di due gruppi di lezioni di due ore ciascuna il pomeriggio del giovedì dalle 14 alle 18 e del venerdì dalle 14 alle 18. Sono previsti vari compiti scritti.

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à e Appelli di Esame

L'esame di questo corso coincide con quello di Algotimica e Laboratorio di 12 crediti. Consiste di tre prove:

Le prove possono essere sostenute in appelli diversi. Se una prova non viene passata, occorre risostenere soltanto quella.

Per avere una idea della tipologia delle prove, si consultino i testi dell'anno scorso.

Libri di testo

Per il laboratorio, un testo fra:

Materiale per il Laboratorio

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: qsort-based.
  9. Sottosequenza di somma massima.
  10. Programmazione dinamica: LCS, Partizione e Zaino
  11. Algoritmi randomizzati: Quicksort.
  12. Generazione di combinazioni e permutazioni
  13. Analisi ammortizzata: doubling di array, contatore binario, k ricerche.
  14. Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto).
  15. Alberi: rappresentazione e visite.
  16. Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
  17. Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse.
  18. Grafi III: Minimum Spanning Tree e Shortest Path.

Registro delle Lezioni

Data Argomento Rif. Biblio
22/09/2016 introduzione al corso: problemi, algoritmi, limiti inferiore e superiore. Algoritmi facili e difficili
22/09/2016 Test scritto per stabilire la preparazione degli studenti allrec.docx
23/09/2016 Correzione degli esercizi del test
23/09/2016 Divide et Impera, MergeSort,Merge-SelectionSort, soluzione di equazioni di ricorrenza col metodo della sostituzione [CLRS]: cap 2
29/09/2016 Divide et Impera: esercizi, soluzione equazioni di ricorrenza con l'albero di ricorsione[CLRS]:cap 2
29/09/2016 Word model e bit model, alberi di decisione per il problema dell'ordinamento [CLRS]: cap 8.1
30/09/2016 Ricerca Binaria. Partition e QuickSort. Analisi caso ottimo, caso pessimo. Randomized QuickSort [CLRS]: cap 7, escluso 7.4.2 Numero di confronti di Randomized-Quicksort (Appunti del Prof. Luccio)
30/09/2016 Divide et Impera: esercizi, soluzione equazioni di ricorrenza con l'albero di ricorsione
06/10/2016 Problema della Selezione. QuickSelect; Teorema dell'esperto per risolvere le ricorrenze [CLRS]:9.2,4.5]
06/10/2016 Applicazione del teorema dell'esperto. Esercizi di Divide et Impera
07/10/2016 Laboratorio: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. Cap. 2-3, 7.1-7.4 di [KR]. Lucidi.
07/10/2016 Laboratorio: Richiami di linguaggio C: Costrutti, array, printf e scanf. Cap. 2-3, 7.1-7.4 di [KR]. Lucidi.
13/10/2016 Heap come coda con priorità, operazioni di inserzione e estrazione del massimo. Implementazione con array e costruzione dell'Heap. HeapSort [CLRS]:cap 6]
13/10/2016 Esercizi di simulazione, di dimostrazione di proprietà e di utilizzo della struttura Heap
14/10/2016 Laboratorio: Puntatori, Array, e stringhe. Uso di Valgrind. Allocazione dinamica della memoria. Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi
14/10/2016 Laboratorio: Esercizi.
20/10/2016 Stabilità di un algoritmo di ordinamento. Sorting in tempo lineare: CountingSort e RadixSort[CLRS]:cap 8.1, 8.2 e 8.3]
20/10/2016 Esercitazione scritta compito,sol-es1, sol-es2-3, sol-es4
21/10/2016 Laboratorio: Array di stringhe; Selection, Insertion e Quick Sort su interi e stringhe; struct, typedef e qsort. Lucidi Lucidi Lucidi
21/10/2016 Laboratorio: Esercizi.
27/10/2016 Dizionari: realizzazione con tabelle a indirizzamento diretto e con tabelle hash; funzioni hash (metodo della divisione e metodo iterativo); gestione delle collisioni mediante concatenamento (analisi al caso pessimo e medio).[CLRS] cap 11: 11.2, 11.2, 11.3, 11.3.1.
27/10/2016 Tabelle hash a indirizzamento aperto (analisi al caso pessimo e medio). Scansione lineare, scansione quadratica, doppio hashing. Esercizi. [CLRS] cap 11: 11.4. Dispense Prof. Luccio
28/10/2016 Laboratorio: Liste mono e bidirezionali. Alberi binari di ricerca. Esercizi. Lucidi Lucidi
10/11/2016 Alberi, alberi binari; trasformazione da albero a albero binario. Visite. Divide et impera su alberi. Calcolo di dimensione, altezza e profondità. Esercizi. [CGGR] cap. 3.8.
10/11/2016 Alberi binari di ricerca, definizione e complessità delle operazioni di ricerca, inserzione e cancellazione, minimo e massimo, predecessore e successore, ordinamento. Minimo antenato comune.[CLRS] cap 12.1, 12.2,12.3
11/11/2016 Laboratorio: Tavole hash con liste concatenate. Esercizi. Lucidi
17/11/2016 Alberi AVL: definizione, alberi di Fibonacci, dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi AVL (ricerca; inserimento: rotazioni.). [CGGR]: Alberi AVL, rotazioni.
17/11/2016 Il problema della Edit Distance: definizione, regola ricorsiva e ricostruzione della soluzione, algoritmi ED e ALLINEA. Edit Distance (dispense Prof. Luccio).
18/11/2016 Laboratorio: Esercizi.
24/11/2016 Altri problemi di Programmazione Dinamica: Apparizioni approssimate e esercizi Edit Distance (dispense Prof. Luccio).
24/11/2016 Il problema dello Zaino, algortimi greedy, algoritmo esponenziale con GeneraBinarie, algortimo di programmazione dinamica.
25/11/2016 Laboratorio: Esercizi.
01/12/2016 Grafi: Notazione, definizioni, memorizzazione. Visita BFS, Alberi BFS e cammini minimi. Visita DFS, foresta DFS e classificazione degli archi [CLRS] cap 22.1, 22.2,22.3
01/12/2016 Ordinamento topologico, Esercizi [CLRS] cap 22.4
02/12/2016 Esercizi riassuntivi sui grafi