logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2017/2018
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 INFORMATICAI1AAE086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA
I1TAE086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA
II3AE086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA

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.3 Alberi 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

L'esame è scritto e con possibilità di consultazione dei testi. Gli appelli d'esame sono svolti secondo le regole di facoltà. Per il corso integrato gli appelli saranno basati su una prova unica.


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 complessita' 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. E' disponibile una versione breve del testo ritagliata appositamente per questo corso, ossia la versione "Create" predisposta da McGraw-Hill Italia secondo le indicazioni fornite dai docenti del corso.

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

Il testo puo' 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 e' un eserciziario che tratta gli argomenti del programma del primo modulo del corso integrato e della parte Teoria della complessita' 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
Disponibilità di libri di testo/bibliografia in lingua inglese
Possibilità di sostenere l'esame in lingua inglese
schedaincarico v. 1.6.5 / 1.6.5
Area Servizi ICT
20/09/2020