Scopi

Il modulo completa l'avvio alla programmazione quale strumento per la soluzione di problemi. Si accentua il passaggio dalle capacità analitiche a quelle progettuali.
Il modulo presenta le soluzioni algoritmiche "classiche" dei problemi, e la teoria che sta alla loro base, con particolare riferimento a realizzazioni in C e affronta casi di studio di maggiori dimensioni risolti mediante strategie algoritmiche implementate in C.

Responsabili

Docente
Giovanni Squillero
giovanni.squillero@polito.it
Telefono: 011/5647092
Fax: 011/5647099

Tutore
Sergio Porcu
sergio.porcu@gmail.com
Telefono: 0785/329002
Fax: 0785/329135

Contenuti

Analisi di algoritmi:
    Analisi asintotica e complessità di caso peggiore.
    Notazione Ο, Θ, Ω.
Algoritmi elementari:
    Ordinamento quadratico (selection sort, insertion sort).
    Ordinamento lineare (counting sort).
    Ordinamento logaritmico (quicksort, heapsort, mergesort).
    Attraversamenti di alberi e grafi.
Strutture dati:
    Rappresentazione dei dati in memoria.
    Puntatori.
    Allocazione statica e dinamica della memoria.
    Strutture linkate.
    Gestione della memoria in runtime.
    Strategie per scegliere la struttura dati.
Ricorsione:
    Il concetto di ricorsione.
    Funzioni matematiche ricorsive.
    Procedure ricorsive semplici.
    Backtrack e implementazione della ricorsione.
Paradigmi algoritmici:
    Divide-and-conquer.
    Greedy.
Algoritmi classici:
    Tabelle di hash.
    Alberi binari di ricerca e varianti.
    B-alberi.
Algoritmi sui grafi:
    Cammini minimi.
    Alberi ricoperti minimi.

Materiale didattico

Spazio web del docente

Materiale del tutore in area studenti

Spazio web Ce.Te.M.