Teoria degli algoritmi
OII
Problemi delle Selezioni Scolastiche delle Olimpiadi Italiane di InformaticaDal problema alla risposta
- Problema Esecutore :: Algoritmo
- Dal problema alla risposta: #1 :: #2
- MACCHINA DI TURING
- Dalla MdT alla macchina a registri :: Dalle quintuple all'assembly
- MODELLO ASTRATTO DI CALCOLATORE
- Dal basso livello all'alto livello
Problemi
http://it.wikibooks.org/wiki/Implementazioni_di_algoritmiNumeri
- Aritmetica ricorsiva: somma, prodotto, potenza
- Fattoriale, Massimo Comun Divisore, minimo comune multiplo, numeri casuali
- Operare con i bit
- Algoritmo di Siracusa, numeri di Fibonacci
Ricerche
Fusioni
Ordinamenti
- Due elementi, bubblesort, shakersort, insertsort, selesort
- Mergesort, quicksort
Problemi difficili
Grafica
Tipi di dato
- Interi, reali, operazioni
- Array, Record, Stringhe
Controllo dell'esecuzione
- Sequenza
- Selezioni
- Ripetizioni
- Sottoprogrammi
Complessità degli algoritmi
- Criteri generali
- Complessità degli algoritmi di ricerca: sequenziale, binaria, confronto
- Calcolo della complessità in tempo, asintotica, dei problemi
- Complessità degli algoritmi di ordinamento: ingenui, evoluti, ingenui contro evoluti
- Problemi difficili
Abstract Data Type
Definizioni e progetto- Stack, Coda, coda doppia, coda con priorità
- Tabella di record, tabella ordinata di record
Memoria dinamica
Organizzazione della memoria dinamicaListe
- tipologia, operazioni
- lista semplice, lista con testa e coda, lista circolare
- lista bidirezionale, lista multipla
Alberi
- degli antenati, dei discendenti, ...
- alberi, alberi binari, alberi binari di ricerca
Grafi
- ...
Archivi classici
Concetti generali
...
Organizzazioni per chiave primaria
- Sequenziale, ad accesso diretto
- Con indice, a indici multipli
Organizzazioni per chiavi secondarie
- ...
Autoverifica
- 01, 02, 03
