Questa è una vecchia versione del documento!
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.
su http://mediateca.unipi.it sono a disposizione disposizione le video-lezioni dell'anno 2015/2016. Bisogna registrarsi con le credenziali di ateneo.
Venerdì 7 ottobre cominceranno le lezioni di Laboratorio.
Orario delle Lezioni | |||
---|---|---|---|
Giovedì | 14-18 | N1 | |
Venerdì | 14-18 | M |
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.
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.
Per il laboratorio, un testo fra:
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 consigliamo di installare una macchina virtuale, come VirtualBox, con una qualunque distribuzione Linux. 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 il corso), per concentrarsi soltanto sugli aspetti di coding degli algoritmi.qsort
-based.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/2015 | 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/2015 | 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. |