Politecnico di Torino
Politecnico di Torino
   
Login  
en
Politecnico di Torino
Anno Accademico 2009/10
10EIPFN
Algoritmi e programmazione avanzata
Corso di Laurea in Matematica Per Le Scienze Dell'Ingegneria - Torino
Docente Qualifica Settore Lez Es Lab Tut Anni incarico
Poncino Massimo ORARIO RICEVIMENTO PO ING-INF/05 54 12 18 0 7
SSD CFU Attivita' formative Ambiti disciplinari
ING-INF/05 7.5 A - Di base Formazione informatica
Obiettivi dell'insegnamento
L'insegnamento, obbligatorio per tutti gli studenti, si propone un duplice obiettivo: da un lato, completare l'uso della programmazione quale strumento per la soluzione di problemi; dall'altro, studiare i concetti di base per la formulazione di soluzioni algoritmiche a problemi concreti. In particolare, verranno studiate soluzioni a problemi formulati in termini di strutture matematiche astratte (liste, code, grafi) e metodologie per identificare i problemi astratti che più si addicono allo studio di un problema concreto, mantenendo uno stretto legame con la loro implementazione in un programma.
Competenze attese
Il corso ha tre obiettivi principali: rendere l'allievo in grado di risolvere problemi concreti usando un approccio algoritmico; valutare l'efficienza dell'algoritmo scelto in termini di tempo di esecuzione; capacità di implementare tale soluzione algoritmica come programma da eseguire su calcolatore. Queste capacità vengono applicate alla soluzione di problemi pratici, siano essi trattabili (quindi con soluzioni di costo polinomiale) o meno (quindi con soluzioni euristiche approssimate).
Prerequisiti
Sono richieste principalmente conoscenze del linguaggio di programmazione C (al livello del corso di Informatica del I anno), ed alcune nozioni basilari dell'Analisi Matematica.
Programma
1. Complementi di programmazione C
o Programmazione a moduli
o Ricorsione
§ Il concetto di ricorsione e relativa implementazione;
§ Funzioni matematiche ricorsive.
o Tipi di dato astratto (ADT) e strutture dati:
§ Astrazione e interfaccia
§ Pile e code, matrici e vettori dinamici;
§ Liste e alberi

2. Concetti di base sugli algoritmi
o Complessità degli algoritmi:
§ Notazione asintotica, e complessità di caso peggiore
§ Equazioni alle ricorrenze e metodi di risoluzione delle equazioni di ricorrenza

3. Ordinamento e selezione
o insertion sort, merge sort, heap sort, quick sort, quick sort probabilistico.
o Studio della complessità degli algoritmi di ordinamento, limite inferiore dell'ordinamento per confronti.
o Algoritmi lineari, counting sort, radix sort, bucket sort.
o Algoritmi di selezione, minimo, massimo

4. Strutture dati complesse:
o Code, pile, liste, heap
o Alberi: alberi binari di ricerca, alberi RB,
o Tabelle Hash

5. Paradigmi algoritmici:
o divide and conquer
o algoritmi greedy
o programmazione dinamica
o paradigmi basati su ricerca: backtracking

6. Grafi
o Definizione e rappresentazione di un grafo
o Visita in ampiezza e in profondità; ordinamento topologico, componenti connesse
o Alberi di copertura di costo minimo (Prim e Kruskal)
o Cammini minimi a sorgente singola (Dijkstra e Bellman-Ford) e multipla (Floyd-Warshall e Johnson)


7.Teoria della complessita'
o Non determinismo e algoritmi non deterministici
o Classi P e NP
o Approssimazione ed euristiche
Laboratori e/o esercitazioni
Il corso prevede circa 10 ore di esercitazione in laboratorio, nelle quali alcuni degli algoritmi discussi in aula verranno tradotti in programmi.
Bibliografia
- Dispense del corso a cura del docente
- T. Cormen, C. Leiserson, R. Rivest, C. Stein, 'Introduzione agli Algoritmi e Strutture Dati', McGraw-Hill Italia.
- H.M.Deitel e P.J.Deitel, 'C: Corso completo di programmazione', Apogeo.
Verifica la disponibilita in biblioteca
Controlli dell'apprendimento / Modalità d'esame
L'esame consiste in una prova scritta a sua volta strutturata in due parti.
La prima parte è mirata ad accertare le conoscenze dello studente sugli aspetti teorici della materia (algoritmi e strutture dati);
la seconda parte valuta invece l'applicazione pratica dei concetti teorici, e prevede la realizzazione di un programma in linguaggio C che implementi la soluzione di un problema pratico che richiede l'uso di algoritmi o strutture dati complesse.
Orario delle lezioni
Statistiche superamento esami

Programma definitivo per l'A.A.2009/10
Indietro



© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
WCAG 2.0 (Level AA)
Contatti