|
Docente
|
GIAMMARRESI DORA
(programma)
Introduzione ai computer e alla programmazione.Il linguaggio C: variabili e tipi di dati fondamentali. Istruzioni di input-output. Controllo del flusso. Operatori aritmetici, logici e relazionali. Le funzioni e il passaggio dei parametri. Le funzioni ricorsive. Gli array: definizioni e applicazioni. Media, mediana, moda. Problemi di ricerca e ordinamento su array. Le strutture. I puntatori e le strutture autoreferenzianti.
La valutazione degli algoritmi e la complessità computazionale. Notazione asintotica. Upper bound e lower
bound. Il teorema fondamentale delle ricorrenze . Il problema dell'ordinamento: selectionsort, bubblesort, insertionsort, mergesort, heapsort e quicksort. Analisi degli algoritmi e implementazione in C. Calcolo del lower bound.
Stutture dati elementari: liste, pile e code. Definizioni e loro implementazioni con strutture linkate.
Alberi: definizioni, notazioni e proprieta'. Implementazione con strutture linkate. Visita di alberi.
Alberi binari di ricerca: definizione e implementazione in C.
Grafi: definizioni e notazioni. Implementazioni con matrici di adiacenza e liste di adiacenza. Visite in ampiezza e in profondità di grafi non diretti e diretti. Analisi della complessita' degli algoritmi di visita e loro proprietà. Cammini e grafi Euleriani: definizioni e proprieta'. Cammini e grafi hamiltoniani: definizione. Cenni sulle classi di complessità computazionale P e NP.
 Testi di riferimento:
H.Deitel,P.Deitel
Il linguaggio C-Fondamenti e Tecniche di Programmazione
Pearson Education.
C. Demetrescu, I. Finocchi, G.F.Italiano
Algoritmi e Strutture Dati
McGraw-Hill
|
