Orario del Corso

Giorno	Orario	Aula
Lunedì	9 - 11	C
Giovedì	14 - 16	E
Venerdì	9 - 11	E
Ricevimento Venerdì	11 - 13	Studio docente

Modalità di Esame

L’esame di Algoritmica consiste di una prova scritta e di una prova orale. Durante la prova scritta gli studenti NON possono consultare i propri libri e appunti. L'esame scritto dunque consiste di esercizi e domande teoriche.

Durante il corso vengono svolte due verifiche intermedie (compitini). Gli studenti che superano entrambe le verifiche, con una votazione superiore al 18, possono sostenere la prova orale in uno dei due appelli della sessione invernale (Gennaio o Febbraio). Chi avesse riportato la sufficienza in un compitino soltanto potrà recuperare la parte insufficiente in uno degli appelli della sessione invernale. In questi appelli la prova scritta sarà composta da due parti così da consentire il recupero suddetto. Il recupero può essere anche tentato da chi desidera migliorare il voto riportato in un compitino. In questo caso, il voto del compitino viene perso al momento della consegna del nuovo elaborato scritto.

Coloro che superano la prova scritta possono sostenere la prova orale nello stesso appello, oppure in un appello della stessa sessione. Ogni studente può entare l’esame al più quattro volte durante tutto il corso dell’Anno Accademico: la consegna dell’elaborato viene considerata come “tentativo”.

Libri di Testo

· [CLR] T. Cormen, C. Leiserson, R. Rivest, "Introduzione agli algoritmi e strutture dati", McGraw-Hill Italia, 2005.

· [L] F. Luccio, La Struttura degli Algoritmi, Boringhieri 1984.

Appunti, Programmi, Esercizi e altro...

· Prerequisiti del corso: alcune nozioni sullo studio di funzioni (test) e conoscenza del concetto di lista e albero (LSD)

· Programma java per trovare la sottosequenza di somma massima (qui trovi la classe Text.java).

· Una collezione di esercizi: parte 1, parte 2, parte 3.

· Compiti di esame: 04/04/02, 16/05/02, 27/05/02, 21/06/02, 12/07/02, 20/12/04, 11/01/05, 02/02/05,06/06/05,27/06/05,18/07/05,12/09/05,04/11/05,21/12/05,13/01/06.

Programma del corso (Riferito alla nuova versione del CLR)

1. Analisi di Algoritmi e Complessità

a. Introduzione alla complessità di calcolo [CLR I.1 e I.2]

b. Ordini di grandezza delle funzioni [CLR I.3]

c. Algoritmi ricorsivi e Tecnica divide&conquer [L cap. 5]

i. Numeri di Fibonacci;

ii. Calcolo del massimo e minimo;

iii. Ricerca Binaria;

iv. Mergesort;

v. Moltiplicazione rapida di interi.

d. Relazioni di ricorrenza [CLR I.4]

e. Limiti inferiori alla complessità [L sez. 4.2 e CLR I.8.1]

2. Progetto di Algoritmi e Strutture Dati

a. Code, Pile, Liste e alberi [CLR III.10 e Rivedere appunti corso Laboratorio]

b. Heap e Heapsort [CLR II.6]

c. Quicksort [CLR II.7]

d. Ordinamento in tempo lineare [CLR II.8]

e. Tabelle hash: Liste di concatenazione, Indirizzamento aperto, Hashing Perfetto [CLR III.11]

g. Alberi binari di ricerca [L cap. 5 e CLR III.12]

h. Grafi: rappresentazione, visite, topological sort [CLR VI.22]

l. Alberi delta-bilanciati e AVL: definizione e operazioni di rotazione [L pagine 80-84 e 90-97]

3. Classi di Complessità [appunti]

a. Enumerazione e non determinismo: combinazioni e permutazioni

b. Classi P, NP, NPC, NP-hard

4. Modelli di Calcolo e Calcolabilità [appunti]

a. Indecidibilità e universalitàà

b. Macchina di Turing

Il registro elettronico delle lezioni è disponibile sul sito virmap dell’ateneo