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 Comai Sara
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) - CO (360) INGEGNERIA INFORMATICAIOLAZZZZ086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA

Programma dettagliato e risultati di apprendimento attesi

Obiettivi

 
L'obiettivo principale del modulo è quello di 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 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.). Tutti gli aspetti teorici verranno affiancati da esempi pratici sviluppati utilizzando il linguaggio C++.

 

Programma delle lezioni e delle 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

2. Algoritmi e strutture dati

2.1 Introduzione agli algoritmi e strutture dati. Analisi di complessità di algoritmi e strutture dati. 

2.2 Strutture dati e algoritmi fondamentali: Liste, Code e Pile, Alberi binari e generici

2.3 Algoritmi di ordinamento

2.4 Algoritmi di ricerca. Hashing e Indicizzazione

2.5 Grafi, loro rappresentazione e gestione

3. Argomenti avanzati

3.1 Tecniche di progettazione di algoritmi

3.2 Problemi NP-completi

 

Prerequisiti

Il corso richiede una buona conoscenza degli argomenti trattati nel corso di Fondamenti di informatica, che verranno dati per noti. Le conoscenze di base sugli aspetti fondamentali dell'architettura dei calcolatori possono essere utili.


Note Sulla Modalità di valutazione

Prove in itinere. La verifica dell'apprendimento dell'intero corso di API verrà effettuata attraverso 3 prove in itinere che possono riguardare tutti gli argomenti del corso. 

Prova in presenza. L'esame in presenza consiste in una prova scritta (non su calcolatore). Se necessario, il docente potrà richiedere un colloquio orale.

Valutazione. La valutazione della prova si baserà in parte sui risultati riportati nelle prove in itinere (fino a 3/30 per ciascuna prova) e in parte sui risultati della prova in presenza (per il punteggio rimanente); per i casi in cui non esista alcuna conformità tra i due tipi di risultato, il docente si riserva di annullare i risultati delle prove in itinere. Nel caso in cui lo studente sia impossibilitato a svolgere le prove in itinere, in presenza potrà recuperare fino a 2/30 per ciascuna prova in itinere non svolta.


Bibliografia
Risorsa bibliografica facoltativaClifford A. Shaffer, Data Structures and Algorithm Analysis http://people.cs.vt.edu/~shaffer/Book/C++3e20120605.pdf
Risorsa bibliografica facoltativaAlberto Montresor, Alan A. Bertossi, Algoritmi e strutture di dati, Editore: CittàStudi; 2 edizione, Anno edizione: 2010, ISBN: 8825173563
Risorsa bibliografica facoltativaThomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduzione agli algoritmi e strutture dati 3/ed, Editore: McGraw-Hill, Anno edizione: 2010, ISBN: 9788838665158
Risorsa bibliografica facoltativaDino Mandrioli e Paola Spoletini, Informatica teorica, Editore: CittàStudi; 2 edizione, Anno edizione: 2011, ISBN: 8825173652

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
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.6.5 / 1.6.5
Area Servizi ICT
27/09/2020