Programma

PARTE 1: Generalità e strumenti.
Definizione di problema computazionale, algoritmo, struttura di dati.
Random Access Machine e pseudocodice.
Studio asintotico delle funzioni (notazioni O-grande, Omega e Theta).
Complessità asintotica degli algoritmi e dei problemi.
Complessità ammortizzata.
Analisi del caso migliore, medio, peggiore.
Ricorsione ed equazioni di ricorrenza.
Teoremi per l'analisi di funzioni ricorsive.

PARTE 2: Tipi astratti di dato.
Tipi astratti di dato e loro rappresentazioni.
Esempi già noti: insiemi, pile, code, liste, ecc.
Gestione telescopica di strutture di dati dinamiche.
Alberi: Alberi binari; Alberi di grado arbitrario; Visite di alberi; Alberi binari di ricerca; Alberi rosso-neri.
Tabelle hash.
Grafi: Rappresentazione con matrici e liste di adiacenza. Visite in ampiezza e profondità. Grafi e connettività. Componenti connesse. Cammini minimi su grafi.

PARTE 3: Paradigmi algoritmici.
Algoritmi greedy (esempio: Ordinamento tramite selection sort).
Algoritmi iterativi (esempio: Ordinamento tramite insertion sort).
Algoritmi divide et impera (esempi: Ordinamento tramite merge-sort, ordinamento tramite quick-sort).

PARTE 4: Il corso contiene richiami delle seguenti nozioni di Linguaggio C
Programmazione imperativa.
Tipi di dato elementari.
Funzioni.
Puntatori e Array.
Stringhe.
Gestione della memoria: Heap e Stack.
Gestione di progetti in C: prototipi e implementazioni.
Ricorsione e Memoria.
Puntatori e Record.
Gestione dinamica della memoria.

Testi Adottati

Trasparenze fornite dal docente e scaricabili via via dal sito del corso: https://moodle1.ing.uniroma3.it/
Per scaricare le slides sono neccessarie le credenziali di ateneo.

Bibliografia Di Riferimento

I seguenti testi sono consigliati esclusivamente agli studenti che non possono seguire le lezioni: T.H.CORMEN, C.E.LEISERSON, R.L.RIVEST, C.STEIN INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI (TERZA EDIZIONE) MCGRAW-HILL, 2010 B.W.KERNIGHAM, D.M.RITCHIE IL LINGUAGGIO C, PRINCIPI DI PROGRAMMAZIONE E MANUALE DI RIFERIMENTO (SECONDA EDIZIONE) PEARSON EDUCATION ITALIA, 2004 Qualsiasi altro testo introduttivo al linguaggio C potrebbe essere equivalente a questo qui sopra.

Modalità Erogazione

Lezioni con proiezione di slides. Esercitazioni in classe con scrittura da parte del docente (con suggerimenti degli studenti) di codice in lingaggio C, compilazione, linking ed esecuzione di programmi.

Modalità Frequenza

Le trasparenze del corso sono abbondantemente commentate allo scopo di rendere possibile la preparazione all'esame anche agli studenti non frequentanti.

Modalità Valutazione

Valutazione in itinere: durante l'erogazione del corso gli studenti verranno invitati a risolvere degli "homework" su Moodle consistenti nella scrittura di funzioni in linguaggio C. Moodle compila la risposta e ne verifica automaticamente la correttezza con opportuni dati di test. Durante il corso verranno svolti diverse prove intermedie in laboratorio con esercizi analoghi a quelli svolti online. Prova scritta: ha una durata di 2 ore e consiste in un programma in pseudocodice di cui lo studente deve eseguire un'analisi della complessità asintotica in termini di O-grande, Omega e Theta e di un problema da risolvere tramite una funzione in linguaggio C (ed eventuali funzioni di appoggio). La prova scritta è preceduta da una prova preliminare in laboratorio allo scopo di verificare che gli studenti abbiano raggiunto una dimestichezza minima con il linguaggio C e con i concetti base del corso. Gli studenti che hanno svolto le prove intermedie hanno guadagnato una porzione del voto finale. Il voto finale viene completato con una prova scritta.