Presentazione

Organizzazione della Didattica

DM270
INFORMATICA ORD. 2011


9

Corsi comuni

 

Frontali Esercizi Laboratorio Studio Individuale
ORE: 56 16 0 136

Periodo

AnnoPeriodo
II anno2 semestre

Frequenza

Facoltativa

Erogazione

Convenzionale

Lingua

Italiano

Calendario Attività Didattiche

InizioFine
27/02/201709/06/2017

Tipologia

TipologiaAmbitoSSDCFU
caratterizzanteDiscipline informaticheINF/019


Responsabile Insegnamento

ResponsabileSSDStruttura
Prof. BALDAN PAOLOINF/01Dipartimento di Matematica

Altri Docenti

DocenteCoperturaSSDStruttura
Prof. BALDAN PAOLOAffidamentoINF/01Dipartimento di Matematica

Attività di Supporto alla Didattica

Non previste.

Bollettino

Elementi di programmazione Matematica discreta Analisi matematica

Il corso intende fornire un'introduzione agli algoritmi e alla loro analisi. Lo studente apprende alcuni algoritmi e strutture dati fondamentali che sono alla base dello sviluppo dei sistemi software. L'analisi di tali algoritmi aiuta lo studente a sviluppare una sensibilità per la realizzazione di programmi efficienti e corretti.

Lezioni ed esercitazioni.

- Fondamenti Analisi dettagliata di InsertSort: Pseudocodice. Calcolo diretto del tempo calcolo in funzione di n. Tasso di crescita e notazione asintotica. L'algoritmo MergeSort e la tecnica divide et impera. Analisi della complessità di MergeSort. Soluzione delle ricorrenze. Il teorema dell'esperto. QuickSort. Complessità media di QuickSort e analisi probabilistica. Randomizzazione di QuickSort. - Ordinamento e Statistiche d'Ordine HeapSort e sua analisi. Limite inferiore per la complessità degli algoritmi di ordinamento. Implementazione di code con priorità mediante heap. Ordinamento in tempo lineare. Algoritmi CountingSort e RadixSort. - Strutture Dati Tavole hash. Alberi binari di ricerca. Alberi rosso-neri. Aumento di strutture dati. Teorema dell'aumento per alberi rosso-neri. Alberi di intervalli. - Tecniche avanzate di progettazione e analisi Programmazione dinamica. Algoritmi golosi. Analisi ammortizzata.

Prova scritta ed esame orale.

Gli esercizi della prova scritta mirano a valutare la capacità dello studente di utilizzare le nozioni apprese per l'individuazione di soluzioni algoritmiche efficienti a problemi assegnati. La prova orale verifica la conoscenza degli argomenti teorici discussi a lezione.

T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein, Introduzione agli Algoritmi e Strutture Dati (terza edizione). : McGraw-Hill Italia, 2010


Elementi di programmazione Matematica discreta Analisi matematica

Il corso intende fornire un'introduzione agli algoritmi e alla loro analisi. Lo studente apprende alcuni algoritmi e strutture dati fondamentali che sono alla base dello sviluppo dei sistemi software. L'analisi di tali algoritmi aiuta lo studente a sviluppare una sensibilità per la realizzazione di programmi efficienti e corretti.

Lezioni ed esercitazioni.

- Fondamenti Analisi dettagliata di InsertSort: Pseudocodice. Calcolo diretto del tempo calcolo in funzione di n. Tasso di crescita e notazione asintotica. L'algoritmo MergeSort e la tecnica divide et impera. Analisi della complessità di MergeSort. Soluzione delle ricorrenze. Il teorema dell'esperto. QuickSort. Complessità media di QuickSort e analisi probabilistica. Randomizzazione di QuickSort. - Ordinamento e Statistiche d'Ordine HeapSort e sua analisi. Limite inferiore per la complessità degli algoritmi di ordinamento. Implementazione di code con priorità mediante heap. Ordinamento in tempo lineare. Algoritmi CountingSort e RadixSort. - Strutture Dati Tavole hash. Alberi binari di ricerca. Alberi rosso-neri. Aumento di strutture dati. Teorema dell'aumento per alberi rosso-neri. Alberi di intervalli. - Tecniche avanzate di progettazione e analisi Programmazione dinamica. Algoritmi golosi. Analisi ammortizzata.

Prova scritta ed esame orale.

Gli esercizi della prova scritta mirano a valutare la capacità dello studente di utilizzare le nozioni apprese per l'individuazione di soluzioni algoritmiche efficienti a problemi assegnati. La prova orale verifica la conoscenza degli argomenti teorici discussi a lezione.

T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein, Introduzione agli Algoritmi e Strutture Dati (terza edizione). : McGraw-Hill Italia, 2010