Università Roma Tre

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

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