CODICE 114590 ANNO ACCADEMICO 2025/2026 CFU 9 cfu anno 2 INGEGNERIA INFORMATICA 8719 (L-8) - GENOVA 6 cfu anno 1 METODOLOGIE FILOSOFICHE 11868 (LM-78 R) - GENOVA SETTORE SCIENTIFICO DISCIPLINARE ING-INF/05 LINGUA Italiano (Inglese a richiesta) SEDE GENOVA PERIODO 1° Semestre MODULI Questo insegnamento è un modulo di: ALGORITMI E COMPUTAZIONE OBIETTIVI E CONTENUTI OBIETTIVI FORMATIVI L'insegnamento introduce le principali strategie di progettazione di algoritmi e gli strumenti per valutarne la correttezza e le prestazioni. L'obiettivo è lo sviluppo della capacità di formalizzare e risolvere problemi per via algoritmica e della capacità di analisi e valutazione delle soluzioni. Sono inoltre sviluppati i concetti relativi alla logica proposizionale e induzione e i principali modelli di computazione per l'informatica: automi, grammatiche, macchine di Turing. 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 a partire dai modelli computazionali più semplici quali gli automi a stati finiti, fino a quelli più complessi come la macchina di Turing. - 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 La macchina di Turing Introduzione alla (Turing) computabilità Introduzione alla (Turing) complessità Dalla macchina di Turing alla macchina RAM 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 ARMANDO TACCHELLA Ricevimento: Su appuntamento a richiesta degli studenti tramite una email al docente. LEZIONI INIZIO LEZIONI Si veda il calendario accademico: INGEGNERIA INFORMATICA 8719 | Orario e calendario accademico | UniGe | Università di Genova | Corsi di Studio UniGe Orari delle lezioni L'orario di questo insegnamento è consultabile all'indirizzo: Portale EasyAcademy
