logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2014/2015
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA
  • 086065 - ALGORITMI E PRINCIPI DELL'INFORMATICA (MOD 2 - INFORMATICA 3)
Docente Mandrioli Dino
Cfu 5.00 Tipo insegnamento Modulo Di Corso Strutturato

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (1 liv.)(ord. 270) - MI (358) INGEGNERIA INFORMATICAI1APZZZZ086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA
061238 - INFORMATICA 3

Programma dettagliato e risultati di apprendimento attesi

Obiettivi

Il corso di Informatica 3 costituisce il secondo modulo del corso integrato Algoritmi e Principi dell'Informatica (API), alla cui scheda si rimanda per una sua presentazione di carattere generale. In circostanze particolari i due moduli sono fruibili separatamente, tuttavia nella grande maggioranza dei casi è previsto che gli studenti seguano integralmente il corso di API.
L'obiettivo principale di questo modulo del corso integrato è fornire allo studente la capacità di risolvere problemi combinando i due aspetti fondamentali della programmazione: le strutture di dati, che riflettono il modo con cui le informazioni possono essere organizzate, e gli algoritmi, che rappresentano il modo con cui l'informazione viene manipolata. Dopo una breve analisi teorica della complessità degli algoritmi verranno trattate le strutture dati fondamentali ed avanzate, quali liste, pile, code, alberi, grafi e loro varianti. Per quanto riguarda gli algoritmi verranno presentati i principali algoritmi di ordinamento, ricerca, indicizzazione e alcuni algoritmi legati ad applicazioni specifiche avanzate (per esempio legate alla grafica, all'elaborazione dei segnali, ecc.).

 

Programma dettagliato delle lezioni ed esercitazioni

1. Teoria della complessità

1.1 Nozioni e notazioni fondamentali per l’analisi di complessità
1.2. I modelli di calcolo e le relazioni tra le loro complessità computazionali

1.2.1 Definizione di complessità spaziale e temporale per macchina di Turing deterministica

1.2.2 Astrazioni e notazione asintotica

1.2.3 Complessità di automi a stati finiti, a pila e macchina di Turing a nastro singolo

1.2.4. Accelerazione lineare

1.3 La macchina RAM

1.3.1. Valutazione di complessità con criterio del costo costante
1.3.2  Il criterio logaritmico

1.4 Il teorema di correlazione polinomiale
1.5 Gerarchie di complessità

1.6 Cenni all'NP-completezza

2. Strutture dati e algoritmi fondamentali

2.1 Algoritmi di ricerca e ordinamento
2.2 Strutture dati elementari (pile, code, liste): rappresentazione, algoritmi di ricerca e gestione

2.3Tabelle hash: funzioni di hash, indirizzamento aperto.

2.4 Alberi e loro gestione

2.4.1 Alberi binari

2.4.2 Algoritmi di visita e gestione

2.4.3Alberi rosso-neri

2.5 Grafi, loro rappresentazione e gestione (cenni)

 

 

Prerequisiti

Il corso richiede una buona conoscenza degli argomenti trattati negli insegnamenti di Fondamenti di informatica e di Informatica teorica, ossia il primo modulo del corso integrato. Le conoscenze di base sugli aspetti fondamentali dell'architettura dei calcolatori possono essere utili.


Note Sulla Modalità di valutazione

Verranno svolte 2 prove in itinere durante lo svolgimento del corso integrato. La prima di queste copre il programma del primo modulo e naturalmente la seconda copre gli argomenti del presente modulo.

Verranno poi svolti appelli regolari secondo le regole della scuola sia per i due moduli separati che per il coprso integrato.


Bibliografia
Risorsa bibliografica obbligatoriaMandrioli D. , Spoletini P., Informatica Teorica, Editore: De Agostini, Anno edizione: 2011
Note:

Il testo oltre a coprire l'intero programma del primo modulo del corso integrato, tratta la parte Teoria della complessità del presente modulo.

Risorsa bibliografica obbligatoriaCormen T., Leiserson C., Rivest R., Stein C., Introduzione agli algoritmi e strutture dati, Editore: McGraw-Hill, Anno edizione: 2010, ISBN: 9788838665158
Note:

Il testo copre la parte Strutture dati e algoritmi fondamentali del modulo. Esso è suggerito in alternativa, ma preferibile, al testo Di Bertossi e Montresor.

Risorsa bibliografica facoltativaBertossi A., Montresor A., Algoritmi e strutture di dati, Editore: De Agostini, Anno edizione: 2010
Note:

Il testo può surrogare il testo principale di Cormen et al.

Risorsa bibliografica obbligatoriaMandrioli D., Lavazza L., Morzenti, A., San Pietro P.L., Spoletini P., Esercizi di Informatica Teorica, III Edizione, Editore: Esculapio, Anno edizione: 2005
Note:

Il testo è un eserciziario che tratta gli argomenti del programma del primo modulo del corso integrato e della parte Teoria della complessità del presente modulo.


Mix Forme Didattiche
Tipo Forma Didattica Ore didattiche
lezione
30.0
esercitazione
20.0
laboratorio informatico
0.0
laboratorio sperimentale
0.0
progetto
0.0
laboratorio di progetto
0.0

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Italiano
schedaincarico v. 1.6.1 / 1.6.1
Area Servizi ICT
08/12/2019