Università Roma Tre

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.

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.