Docente
|
PATRIGNANI MAURIZIO
(programma)
PROGRAMMA DELLA PARTE DI TEORIA
GENERALITÀ:
* DEFINIZIONE DI PROBLEMA COMPUTAZIONALE, ALGORITMO, STRUTTURA DI DATI * RANDOM ACCESS MACHINE E PSEUDOCODICE * STUDIO ASINTOTICO DELLE FUNZIONI (NOTAZIONI O-GRANDE, OMEGA E THETA) * COMPLESSITÀ ASINTOTICA DEGLI ALGORITMI * ANALISI DEL CASO MIGLIORE, MEDIO, PEGGIORE * DETERMINAZIONE DELLA COMPLESSITÀ A PARTIRE DALLO PSEUDOCODICE * COMPLESSITÀ ASINTOTICA DEI PROBLEMI
STRUTTURE DI DATI ELEMENTARI:
* PILE E CODE * LISTE CONCATENATE E DOPPIAMENTE CONCATENATE * ALBERI E ALBERI BINARI * TABELLE HASH * ALBERI BINARI DI RICERCA * ALBERI ROSSO-NERI * GRAFI
ALGORITMI DI ORDINAMENTO:
* ORDINAMENTO TRAMITE SELECTION-SORT LA TECNICA GREEDY IL CONCETTO DI INVARIANTE DI CICLO ALGORITMI DI ORDINAMENTO "IN-LOCO" ALGORITMI DI ORDINAMENTO "STABILI" * ORDINAMENTO TRAMITE INSERTION-SORT ALGORITMI INCREMENTALI
* ORDINAMENTO TRAMITE MERGE-SORT IL PARADIGMA DIVIDE ET IMPERA EQUAZIONI DI RICORRENZA ANALISI DI COMPLESSITÀ DEL MERGE-SORT TEOREMI PER L'ANALISI DI FUNZIONI RICORSIVE
* ORDINAMENTO TRAMITE HEAP-SORT PROCEDURA HEAPIFY HEAP SORT CODE DI PRIORITÀ * ORDINAMENTO TRAMITE QUICK-SORT DESCRIZIONE DEL QUICK-SORT PRESTAZIONI DEL QUICK-SORT
* ORDINAMENTO IN TEMPO LINEARE LOWER BOUND PER ORDINAMENTO BASATO SU CONFRONTO ORDINAMENTO LINEARE TRAMITE COUNTING-SORT ORDINAMENTO LINEARE TRAMITE BUCKET-SORT GENERALIZZAZIONI DEL COUNTING-SORT
ALGORITMI SU GRAFI:
* RAPPRESENTAZIONE DI GRAFI CON MATRICI E LISTE DI ADIACENZA * GRAFI E CONNETTIVITÀ * VISITE IN AMPIEZZA E PROFONDITÀ * COMPLESSITÀ DELLE VISITE SU GRAFI
PROGRAMMA RELATIVO AL LINGUAGGIO C
INTRODUZIONE ALLA PROGRAMMAZIONE IMPERATIVA. TIPI DI DATO ELEMENTARI. FUNZIONI. PUNTATORI, ARRAY E STRINGHE PUNTATORI, RECORD, GESTIONE DELLA MEMORIA LISTE E LORO USO PER RAPPRESENTARE ALTRE STRUTTURE DATI GESTIONE DEI FILE
(testi)
T.H.CORMEN, C.E.LEISERSON, R.L.RIVEST, C.STEIN INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI (TERZA EDIZIONE) MCGRAW-HILL, 2010
OPPURE L'ORIGINALE IN INGLESE
T.H.CORMEN, C.E.LEISERSON, R.L.RIVEST, C.STEIN INTRODUCTION TO ALGORITHMS (THIRD EDITION) MIT PRESS, 2009
B.W.KERNIGHAM, D.M.RITCHIE IL LINGUAGGIO C, PRINCIPI DI PROGRAMMAZIONE E MANUALE DI RIFERIMENTO (SECONDA EDIZIONE) PEARSON EDUCATION ITALIA, 2004
OPPURE L'ORIGINALE IN INGLESE
B.W.KERNIGHAM, D.M.RITCHIE THE C PROGRAMMING LANGUAGE (SECOND EDITION) PRENTICE HALL, 1988
|