Politecnico di Torino
Politecnico di Torino
   
Login  
en
Politecnico di Torino
Anno Accademico 2011/12
02MNOOA, 02MNONZ
Algoritmi e programmazione
Corso di Laurea in Ingegneria Informatica - Torino
Corso di Laurea in Ingegneria Delle Telecomunicazioni - Torino
Docente Qualifica Settore Lez Es Lab Anni incarico
Camurati Paolo Enrico ORARIO RICEVIMENTO PO ING-INF/05 60 20 20 7
SSD CFU Attivita' formative Ambiti disciplinari
ING-INF/05 10 B - Caratterizzanti Ingegneria informatica
Precedenze:
04JCJ o 12BHD
ORA-01722: invalid number
Presentazione
Insegnamento obbligatorio della Laurea in Ingegneria Informatica, collocato al II periodo didattico del I anno.
Il corso approfondisce i concetti necessari per acquisire adeguate conoscenze di programmazione, intesa quale strumento per la soluzione di problemi. Si accentua il passaggio dalle capacitÓ analitiche a quelle progettuali. Vengono presentate le soluzioni algoritmiche "classiche" dei problemi, e la teoria che sta alla loro base, con particolare riferimento a realizzazioni in C. Si propongono agli studenti esempi pratici di soluzione di problemi complessi, con analisi dei principali paradigmi risolutivi, e sono svolte esercitazioni pratiche ad essi connesse.
Risultati di apprendimento attesi
- Conoscenza dei meccanismi di allocazione della memoria e utilizzo dei puntatori
- AbilitÓ di programmazione in C, utilizzando puntatori e strutture dat dinamiche
- Conoscenza delle nozioni elementari di analisi della complessitÓ
- Conoscenza degli algoritmi di ordinamento
- AbilitÓ di valutare la complessitÓ di algoritmi e di migliorarne l'efficienza in termini di tempo di esecuzione e/o uso di memoria
- Conoscenza di strutture dati complesse e ADT (liste, code, heap, alberi, tabelle di hash e grafi) e dei relativi algoritmi
- Conoscenza delle strategie elementari di programmazione modulare in C
- Conoscenza dei paradigmi di programmazione ricorsiva e greedy, della programmazione dinamica e con memorizzazione
- AbilitÓ di utilizzo di strumenti di ausilio alla programmazione
- AbilitÓ di problem solving mediante progetto di strutture dati e algoritmi
- AbilitÓ nelle tecniche di programmazione ricorsiva
Prerequisiti / Conoscenze pregresse

- Conoscenza dell'architettura elementare dei sistemi di elaborazione (modello di Von Neumann)
- Conoscenza di sintassi, tipi di dato e costrutti base del linguaggio C
- CapacitÓ di sviluppare semplici programmi in C, utilizzando construtti condizionali e iterativi, dati scalari a aggregati, I/O standard, file testo e funzioni
- CapacitÓ di soluzione di problemi (algoritmici) elementari
Programma

- Analisi di algorÝtmi (8 h)
- analisi asintotica e complessitÓ di caso peggiore; notazione 0, Q, W; equazioni alle ricorrenze
- Algoritmi di ordinamento: ordinamenti quadratico (selection sort, insertion sort), lineare (counting sort) linearitmico (quicksort, heapsort, mergesort);

- Strutture dati statiche e dinamiche e loro realizzazione in C (6 h)
- rappresentazione dei dati in memoria e gestione della memoria in runtime;
- puntatori (o riferimento a oggettý);
- allocazione di memoria statica, su stack, e dinamica;
- strutture linkate;
- strategie per scegliere la struttura dati.

- ModularitÓ e realizzazione modulare di algoritmi e strutture dati (4 h)
- Il modello implementazione-interfaccia-client
- La realizzazione di un programma C con pi¨ sorgenti e header file
- Utilizzo elementare di strumenti di sviluppo e debug: es. make, gdb, cvs, '

- Ricorsione e programi ricorsivi (4 h)
- il concetto di ricorsione
- funzioni matematiche ricorsive
- procedure ricorsive semplici
- backtrack e implementazione della ricorsione.

- Matematica discreta (2 h)
- insiemi, relazioni, funzioni,
- grafi e alberi

- Oggetti astratti, collezioni di oggetti e ADT (6 h)
- Esempi modulari di strutture composte: es. vettori di liste, multi liste, '
- liste, stack, code FIFO, code generalizzate, coda prioritaria, heap

- Paradigmi algoritmici (6 h)
- divide et impera
- il paradigma greedy
- la programmazione dinamica e la ricorsione con memorizzazione

- Problem solving (4 h)
- Strategie di analisi e di definizione di strutture dati e algoritmi
- Problemi di ricerca e di ottimizzazione

- Strutture dati per tabelle di simboli (6 h)
- Alberi Binari di Ricerca
- Alberi bilanciati (RB-tree)
- B-tree
- Tabelle di hash

- Algoritmi sui grafi (8 h)
- visite in profonditÓ e ampiezza
- applicazioni delle visite
- cammini minimi
- alberi ricoprenti minimi