corso |
Codice: | 008AA | Crediti: | 12 | Semestre: | 2 | Sigla: | AlL | |
Settore disciplinare: | INF/01 - Informatica |
Conoscenza di un linguaggio di programmazione imperativo, preferibilmente il linguaggio C (che utilizzeremo per le nostre esercitazioni di laboratorio).
Dimestichezza con l'uso dei puntatori e della ricorsione.
Nozioni matematiche: proprietà e limiti di funzioni, sommatorie, numeri di Fibonacci, permutazioni, coefficienti binomiali, aritmetica modulare, numeri primi, metodi di dimostrazione (per induzione, per assurdo, per casi).
Definire formalmente la nozione di algoritmo e di modello di calcolo. Caratterizzare i dati da elaborare, organizzandoli e strutturandoli nel modo più opportuno al fine di agevolarne l'uso da parte di un algoritmo. Progettare e realizzare in C algoritmi corretti (che risolvono cioé sempre e solo il problema a cui si è interessati) ed efficienti (cioé che lo risolvono il più velocemente possibile o usano il minor spazio di memoria possibile), attraverso l'esame di diversi paradigmi. Studiare le limitazioni inerenti dei problemi da risolvere, in particolare di quelli la cui soluzione richiede l'esame di tutte le possibilità.
Cosa è un algoritmo e cosa è un modello di calcolo. Saper caratterizzare i dati da elaborare strutturandoli nel modo più opportuno al fine di agevolarne l'uso da parte degli algoritmi. Conoscere le strutture dati e le tecniche fondamentali per il progetto di algoritmi (di base). Conoscere le tecniche di valutazione della complessità e le limitazioni inerenti dei problemi da risolvere. Caratterizzare i problemi indecidibili ed esponenziali. Conoscere il linguaggio C e saper realizzare con esso gli algoritmi e le strutture dati viste in classe.
Saper progettare e realizzare in un linguaggio imperativo (es. C) algoritmi corretti ed efficienti attraverso l'uso di strutture dati e tecniche algoritmiche di base. Saper valutare la complessità di un algoritmo in tempo e spazio, al caso pessimo e al caso medio, e secondo la complessità ammortizzata. Saper valutare le limitazioni inerenti del calcolo.
Lo studente saprà realizzare in un linguaggio imperativo (es. linguaggio C) gli algoritmi e le strutture dati viste in classe. Lo studente saprà inoltre stimare la bontà (leggi, efficienza in tempo e spazio) di un sofwtare sulla base delle caratteristiche progettuali salienti, prescindendo dunque dalla macchina, dal linguaggio di sviluppo o dal sistema operativo sul quale il software viene eseguito. Allo stesso modo, saprà stimare le prestazioni degli algoritmi prima di arrivare alla fase di programmazione, debugging e profiling, mediante l'uso di modelli matematici opportuni.
Segue una descrizione di massima del programma, per i dettagli si rimanda alla pagina del corso.
A scelta uno dei seguenti libri di testo:
Anche dispense e appunti forniti in classe dal docente
Prova in laboratorio per verificare la capacità di realizzazione in C di algoritmi di base visti in classe, o per la risoluzione di semplici problemi su array, liste, alberi e grafi.
Prova scritta con esercizi atti a valutare l'apprendimento delle nozioni teoriche e la capacità di "problem solving" acquisite dallo studente.
Prova orale.