ASD

===============================
PROGRAMMA DELLA PARTE DI TEORIA
===============================

Generalità e strumenti
======================
* Definizione di problema computazionale, algoritmo, struttura di dati
* Random Access Machine e pseudocodice

* Studio asintotico delle funzioni (notazioni O-grande, Omega e Teta)
* Complessità asintotica degli algoritmi e dei problemi
* Analisi del caso migliore, medio, peggiore

* Ricorsione ed equazioni di ricorrenza
* Teoremi per l’analisi di funzioni ricorsive

Tipi astratti di dato
=====================

* Tipi astratti di dato e loro rappresentazioni
esempi già noti: insiemi, pile, code, liste, ecc.
* Alberi
Alberi binari
Alberi di grado arbitrario
Visite di alberi
Alberi binari di ricerca
Alberi rosso-neri
* Tabelle hash
* Grafi
Rappresentazione con matrici e liste di adiacenza
Visite in ampiezza e profondità
Grafi e connettività
Componenti connesse
Cammini minimi su grafi

Paradigmi algoritmici
=====================

* Algoritmi greedy
(esempio: Ordinamento tramite selection sort)
* Algoritmi iterativi
(esempio: Ordinamento tramite insertion sort)
* Algoritmi divide et impera
(esempi: Ordinamento tramite merge-sort, ordinamento tramite quick-sort)

==================================
PROGRAMMA RELATIVO AL LINGUAGGIO C
==================================

Introduzione alla programmazione imperativa.
Tipi di dato elementari.
Funzioni.
Puntatori e Array
Stringhe
Gestione della memoria: Heap e Stack
Gestione di progetti in C: prototipi e implementazioni
Ricorsione e Memoria
Puntatori e Record
Gestione dinamica della memoria
Gestione di File
Liste concatenate: semplicemente, doppiamente, circolari, con sentinella
Operazioni elementari su liste: inserimento, cancellazione e ricerca di nodi
Alberi binari (di ricerca)
Operazioni elementari su alberi binari: inserimento e ricerca di nodi