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 088926 - ALGORITMI E PRINCIPI DELL'INFORMATICA
Docente Rossi Matteo Giovanni
Cfu 10.00 Tipo insegnamento Monodisciplinare

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

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.

 

 

Programma delle lezioni e delle esercitazioni

1. I modelli dell'informatica 

  • Automi (a stati finiti, a pila, Macchine di Turing)
  • Modelli nondeterministici
  • Grammatiche
  • 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à

3. Teoria della complessità

  • Nozioni e notazioni fondamentali per l’analisi di complessità
  • I modelli di calcolo e le relazioni tra le loro complessità computazionali
  • Accelerazione lineare. Gerarchie di complessità.

4. La complessità degli algoritmi e delle strutture dati

  • Concetti di base. Lo pseudocodice come linguaggio per descrivere algoritmi.
  • Algoritmi di ordinamento
  • Strutture dati elementari (pile, code, liste): rappresentazione, algoritmi di ricerca e gestione.
  • Tabelle hash: funzioni di hash, indirizzamento aperto.
  • Alberi: alberi binari ed alberi rosso-neri: : rappresentazione, algoritmi di ricerca e gestione.
  • Grafi: rappresentazione, algoritmi di visita dei grafi.

5. Argomenti avanzati (cenni)

  • Gerarchie di complessità, la complessità delle computazioni nondeterministiche.
  • Problemi NP-completi. 

 

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, non obbligatorie, durante il corso. Verranno poi svolti appelli d'esame secondo le regole di facoltà. L'esame si basa essenzialmente su prove scritte, eventualmente integrate, a discrezione del docente, da ulteriori domande orali.


Bibliografia
Risorsa bibliografica obbligatoriaD. Mandrioli, P. Spoletini, Informatica teorica (II edizione), Editore: De Agostini, Anno edizione: 2011
Risorsa bibliografica facoltativaT. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduzione agli algoritmi e alle strutture dati, 3/ed, Editore: McGraw-Hill, Anno edizione: 2010
Risorsa bibliografica facoltativaA. Bertossi, A. Montresor, Algoritmi e strutture dati, Editore: Ed. Città Studi
Risorsa bibliografica facoltativaD. Mandrioli, L. Lavazza, A. Morzenti, P. San Pietro, P. Spoletini, Esercizi di Informatica Teorica, 3/ed, Editore: Esculapio

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
Disponibilità di libri di testo/bibliografia in lingua inglese
Possibilità di sostenere l'esame in lingua inglese
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.6.5 / 1.6.5
Area Servizi ICT
05/12/2020