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
Docente Mandrioli Dino
Cfu 10.00 Tipo insegnamento Corso Integrato

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
070325 - INFORMATICA TEORICA

Programma dettagliato e risultati di apprendimento attesi

Obiettivi

 L'informatica ha subito un’evoluzione estremamente rapida dai suoi albori ai giorni d’oggi. Ciò ha prodotto notevoli benefici alla qualità della vita ma ha anche creato problemi legati all’affidabilità dei sistemi informatici. Spesso infatti le tecniche di progetto adottate si sono rivelate inadeguate alla complessità dei problemi affrontati.

Da più parti si è individuata, tra le cause principali della scarsa affidabilità dei sistemi informatici, la mancanza di solidi principi teorici su cui basare le tecniche di progettazione.

Il corso di algoritmi e principi dell'informatica ha lo scopo di colmare questa lacuna affrontando in maniera sistematica i problemi fondamentali dell’informatica e mettendo in evidenza come un approccio rigoroso e basato sui fondamenti teorici della disciplina abbia grande rilevanza nelle applicazioni pratiche. Soprattutto il corso intende sviluppare l'attitudine ad affrontare problemi nuovi e non ben precisati e ricavarne un modello preciso e adatto all'individuazione della miglior (o adeguata) soluzione.

Il corso è articolato in due moduli: Informatica Teorica e Informatica 3. I due moduli sono fruibili separatamente (in casi particolari) e in modo integrato (adozione prevista nei casi normali).

Segue il programma dettagliato dei due moduli.

 

Programma delle lezioni e delle esercitazioni

Primo modulo: Informatica teorica

1. I modelli dell'informatica 

  • Automi (a stati finiti, a pila, Macchine di Turing)
  • Modelli nondeterministici (automi, Reti di Petri)
  • Grammatiche
  • Introduzione alla logica matematica 
  • Uso della logica matematica per modellare sistemi e descriverne proprietà.

2. Teoria della computazione

  • Potenza dei modelli di calcolo
  • Tesi di Church
  • Problemi indecidibili
  • Tecniche di dimostrazione di indecidibilità
Secondo modulo:Informatica 3
 
3. Teoria della complessità

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

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

3.2.2 Astrazioni e notazione asintotica

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

3.2.4. Accelerazione lineare

3.3 La macchina RAM

3.3.1. Valutazione di complessità con criterio del costo costante
3.3.2  Il criterio logaritmico

3.4 Il teorema di correlazione polinomiale
3.5 Gerarchie di complessità

3.6 Cenni all'NP-completezza

4. Strutture dati e algoritmi fondamentali

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

4.3Tabelle hash: funzioni di hash, indirizzamento aperto.

4.4 Alberi e loro gestione

4.4.1 Alberi binari

4.4.2 Algoritmi di visita e gestione

4.4.3Alberi rosso-neri

4.5 Grafi, loro rappresentazione e gestione (cenni)

Prerequisiti

Il programma del corso assume la conoscenza degli argomenti trattati nel corso di Fondamenti di Informatica.
Inoltre, costituiscono prerequisito anche parte dei contenuti del corso di Logica e Algebra.


Note Sulla Modalità di valutazione

Verranno svolte due prove in itinere durante il corso.

Il primo appello del modulo Informatica 3 costitusce anche la seconda prova in itinere del corso integrato, la cui prima prova è quella associata al modulo 1. Verranno poi svolti appelli d'esame 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 copre l'intero programma del primo modulo e la parte Teoria della complessità del secondo.

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 e della parte Teoria della complessità del secondo.

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 secondo 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.


Mix Forme Didattiche
Tipo Forma Didattica Ore didattiche
lezione
60.0
esercitazione
40.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