OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

This course introduces the main strategies for designing algorithms and the tools for evaluating their correctness and performance. The objective is to develop the ability to formalize and solve problems algorithmically, as well as the capacity for analysis and evaluation of solutions.

OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO

La frequenza e la partecipazione attiva alle attività formative proposte (lezioni frontali ed esercitazioni) e lo studio individuale consentiranno allo studente di:

- Comprendere le basi teoriche dell'informatica intesa come trattamento automatico di linguaggi formali tramite il modelli computazionale degli automi a stati finiti.

- Comprendere la relazione tra modelli computazionali e linguaggi formali e stabilire una corrispondenza tra tipologia di linguaggio e corrispondente potenza richiesta al modello computazionale.

- Comprendere le problematiche principali relative allo sviluppo di algoritmi, sia relative alla correttezza sia relative alle prestazioni; comoprendere i modelli semplificati per la stima delle risorse.

- Conoscere i principali algoritmi e strutture dati di utilizzo comune: le loro origini, la loro struttura e le loro prestazioni in termini di consumo di risorse computazionali.

MODALITA' DIDATTICHE

Il corso si articola prevalentemente in lezioni di natura frontale il cui materiale verrà messo in anticipo a disposizione degli studenti su Aulaweb. Per ogni argomento verranno forniti i riferimenti corrispondenti ai libri di testo riportati in bibliografia.

PROGRAMMA/CONTENUTO

• Prerequisiti: logica deduttiva e dimostrazioni
• Linguaggi regolari e automi a stati finiti
• Linguaggi liberi dal contesto e automi push-down
• Modelli per l'analisi di algoritmi: caso pessimo, caso medio, complessità ammortizzata
• Strutture dati fondamentali
• Strategia "Forza Bruta" e backtracking
• Strategia "Dividi e Conquista"
• Strategia "Diminisici e Conquista"
• Strategia "Trasforma e Conquista"
• Compromesso spazio-tempo
• Algoritmi "golosi"  (greedy)

TESTI/BIBLIOGRAFIA

La parte di informatica teorica è tratta dal testo:

• J.E. Hopcroft, R. Motwani, J.D. Ullman Automi Linguaggi e Calcolabilità - Pearson

La parte di progettazione e analisi di algoritmi è tratta dai testi:

• R. Sedgewick, K. Wayne - Algorithms (fourth edition) - Addison Wesley
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein - Introduzione agli algoritmi e strutture dati - 3a Edizione - McGraw-Hill

Altri libri di testo

La strutturazione delle lezioni frontali ricalca il seguente testo:

• A. Levitin - Introduction to The Design and Analysis of Algorithms - 2nd edition - Addison-Wesley

Dai seguenti testi sono stati tratti alcuni dei contenuti di progettazione e analisi degli algoritmi:

• C. Demetrescu, I. Finocchi, G. F. Italiano - Algoritmi e strutture dati - 2a edizione McGraw-Hill
• S. Skiena - The Algorithm Design Manual - 2nd edition - Springer
• D.E. Knuth - The Art of Computer Programming - Vol. 1,2,3 - Addison Wesley
• S. Dasgupta, C.H. Papadimitriou, U. Vazirani - Algorithms - McGraw-Hill
• G.J.E. Rawlins - Compared to What?: An Introduction to the Analysis of Algorithms - W. H. Freeman.
• U. Mamber - Introduction to Algorithms: A Creative Approach - Addison Wesley
• J. Bentley - Programming Pearls - 2nd edition - Addison Wesley
• J. Kleinberg, E. Tardos - Algorithm Design - Pearson International Edition

Nota bene: non è necessario acquistare i libri di testo per raggiungere una preparazione soddisfacente per superare l'esame. Qualora si desiderasse consultare i testi e non fossero disponibili in biblioteca, si prega di rivolgersi al docente.

DOCENTI E COMMISSIONI

LEZIONI

Orari delle lezioni

L'orario di questo insegnamento è consultabile all'indirizzo: Portale EasyAcademy

ESAMI

MODALITA' D'ESAME

L'esame prevede una prova scritta su teoria della computazione, algoritmi e strutture dati.