Il corso di TAMC introduce e sviluppa alcune tematiche fondamentali dell'Informatica con particolare enfasi sull'aspetto algoritmico e di programmazione. Il corso di TAMC è destinato agli studenti che frequentano il terzo o il quarto anno del corso di laurea in Matematica e che desiderano dare un taglio ``pratico'' ai loro studi.
Il corso di TAMC ha un duplice obiettivo: da un lato intende fornire le
tecniche basilari della programmazione, dall'altro si propone di
trasmettere e fare apprezzare i principi scientifici del calcolatore e della
teoria della computazione. Linguaggi Pascal e C verranno usati come strumenti
concreti di insegnamento, nonostante le tecniche di programmazione fornite
abbiano valenza generale. Chi fosse interessato all'apprendimento in modo
specifico delle basi per il calcolo scientifico può utilmente prendere
in considerazione il corso di Calcolo Numerico e Programmazione.
Il corso di TAMC è annuale con il seguente contenuto:
Algoritmi e programmi. Ricorsione e induzione. Tempo di esecuzione dei programmi e relazioni di ricorrenza. Soluzione delle relazioni di ricorrenza. Analisi O-grande. Modelli dei dati: liste, pile, code, alberi, insiemi, relazioni, grafi, dizionari. Tecniche di progettazione: divide et impera, backtracking, greedy, programmazione dinamica. Algoritmi fondamentali. Algoritmi di ordinamento: bubble sort, selection sort, insertion sort, quick sort, tree sort, merge sort, counting sort, radix sort, bucket sort. Algoritmi di ricerca: binary search, tabelle hash. Algoritmi su grafi: ricerca depth-first, ricerca breadth-first, albero minimo di copertura, cammini minimi, chiusura transitiva. Strutture dati avanzate: code a priorità, Fibonacci heap, alberi 2-3, alberi rosso-nero, find-merge-set. Generazione dei numeri pseudo casuali. Applicazione alla simulazione e hashing. Teoria della complessità e decidibilità. Macchine di Turing. Non determinismo ed enumerazione. Classi P e NP. NP-completezza e riducibilità. Teorema di Cook-Levin.
Il corso è accompagnato da una sessione di Esercitazioni tenute dal Dott. Michele D'Amico nelle quali verranno ripresi e rielaborati i contenuti presentati durante le lezioni e verranno assegnati gli esercizi di programmazione. In laboratorio è possibile lavorare da soli od in gruppi di al massimo due persone. I lavori verranno svolti in C ed in JavaScript.
I dettagli dell'ambiente e dei linguaggi di programmazione saranno forniti durante le ore di esercitazione e non durante le ore di lezione.
Il laboratorio per il corso di TAMC è costituito da 12 iMac allocati al primo piano del dipartimento di Matematica. Il laboratorio è aperto dalle 8.30 alle 18.00, dal Lunedi al Venerdi. Durante la prima esercitazione avrete la possibilità di indicare la vostra preferenza riguardante l'orario in cui la macchina del vostro gruppo di lavoro sará a voi dedicata.
Ogni esercitazione di laboratorio verrà giudicata in base a criteri di correttezza e di stile. Correttezza e stile rivestiranno la stessa importanza in sede di giudizio. Informazioni più dettagliate a riguardo verranno fornite durante le ore di esercitazione.
Al termine dell'anno ci sarà una prova di esame scritta. Il voto finale sarà determinato in base alla votazione ottenuta nella prova scritta ed ai risultati ottenuti nelle esercitazioni di laboratorio. Alla prova scritta verrà attribuito un punteggio pari a 50% ed agli esercizi di laboratorio verrà attribuito un punteggio pari a 50% del totale.
Le lezioni saranno basate sui seguenti testi:
Per il laboratorio è necessaro un testo di riferimento per il linguaggio C. Tra gli altri, suggeriamo: