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 TETA)
* COMPLESSITÀ ASINTOTICA DEGLI ALGORITMI E DEI PROBLEMI
* ANALISI DEL CASO MIGLIORE, MEDIO, PEGGIORE
* DETERMINAZIONE DELLA COMPLESSITÀ A PARTIRE DALLO PSEUDOCODICE


STRUTTURE DI DATI ELEMENTARI
============================

* PILE E CODE
* LISTE CONCATENATE E DOPPIAMENTE CONCATENATE
* ALBERI BINARI
* TABELLE HASH
* ALBERI BINARI DI RICERCA
* ALBERI ROSSO-NERI
* B-ALBERI

ALGORITMI DI ORDINAMENTO
========================

* ORDINAMENTO TRAMITE MERGE-SORT
IL PARADIGMA DIVIDE ET IMPERA
EQUAZIONI DI RICORRENZA
ANALISI DI COMPLESSITÀ DEL MERGE-SORT
ANALISI DI COMPLESSITÀ DEL BIN-SEARCH
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
ANALISI 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 ORDINATE
USO DI LISTE PER RAPPRESENTARE ALTRE STRUTTURE DATI