CODICE 114618 ANNO ACCADEMICO 2025/2026 CFU 6 cfu anno 2 INGEGNERIA INFORMATICA 8719 (L-8) - IMPERIA SETTORE SCIENTIFICO DISCIPLINARE ING-INF/05 LINGUA Inglese SEDE IMPERIA PERIODO 1° Semestre MODULI Questo insegnamento è un modulo di: ALGORITHMS MATERIALE DIDATTICO AULAWEB 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 MATTEO CARDELLINI 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.