Algoritmica e Laboratorio

Anna Bernasconi      Tel. 0502213121

Conoscenza dei basilari Principi di Programmazione e del Linguaggio C. In particolare, per un più proficuo utilizzo delle ore di laboratorio, si consiglia fortemente di studiare approfonditamente i primi 5 capitoli del libro di testo consigliato per le attività di laboratorio (Il Linguaggio C).
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à.

Conoscenze. 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.

Capacità. 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.

Comportamenti. 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.

L'obiettivo del corso è quello di introdurre strutture dati e tecniche algoritmiche (di base) che consentano allo studente la risoluzione di problemi su sequenze, liste, alberi e grafi, in modo efficiente in tempo e/o spazio. Introdurremo inoltre alcune tecniche per valutare le prestazioni degli algoritmi, o le limitazioni inerenti del calcolo. Infine svolgeremo una intensa attività di laboratorio che porterà gli studenti a sperimentare in linguaggio C le nozioni e le tecniche algoritmiche apprese in classe.