1. Esempi di analisi asintotica di caso peggiore in funzione della dimensione dell'input
2. Discussione sulla dimensione dell'input
3. Metodologia di progetto di algoritmi "divide et impera"
4. Merge-sort: algoritmo ed analisi
5. Equazioni di ricorrenza
6. Generalità sui tipi astratta di dati (ADT)
7. Specifica Java attraverso interfacce degli ADT

1. ricerca binaria: codice e costo
2. algoritmo per riconoscimento di stringhe parenteticamente corrette

1. considerazioni su eliminazione della ricorsione
2. eliminazione ricorsione sull'algoritmo di visita in preordine di un albero
3. considerazioni di costo
4. concetto di chiave
5. chiavi in Java e interface Comparable
6. alberi binari di ricerca (BST)
7. rappresentazione dei nodi
8. operazioni sui BST
9. ricerca iterativa e ricorsiva nei BST
10. costo della ricerca nei BST (caso peggiore)

1. ricerca nei BST: analisi di caso medio (distribuzione uniforme)
2. ricerca predecessore e successore nei BST: algoritmi e costi
3. inserimento in un BST: algoritmo e costo

1. eliminazione da un BST
2. algoritmi e costi
3. ADT dizionario
4. operazioni sul dizionario
5. alberi perfettamente bilanciati

1. alberi perfettamente bilanciati: prestazioni e limiti
2. bilanciamento in altezza e alberi AVL
3. alberi di Fibonacci
4. altezza di un albero di Fibonacci
5. altezza di un albero AVL
6. discussione sui requisiti degli algoritmi di inserimento/eliminazione

1. algoritmo di inserimento in AVL
2. rotazione semplice, rotazione doppia
3. costo inserimento in AVL
4. algoritmo di eliminazione da AVL
5. costo eliminazione da AVL

1. coda di priorità
2. heap
3. rappresentazione degli heap
4. operazioni sugli heap: inserimento, eliminazione e getFirst
5. operazione heapify
6. array2heap

1. algoritmo di Floyd
2. analisi algoritmo di Floyd
3. HeapSort e sua analisi
4. SelectionSort e sua analisi
5. sorting di elementi Comparable

1. quicksort e sua analisi
2. lower bound
3. alberi di decisione e lower bound del sorting

1. indirizzamento diretto
2. tabelle hash
3. funzioni hash
4. paradosso del compleanno
5. funzioni hash su interi e su stringhe
6. tecniche di risoluzione delle collisioni
7. concatenazione
8. open addressing
9. clustering primario e secondario

1. cancellazione nelle tavole hash
2. considerazioni sul fattore di carico delle tavole hash
3. introduzione ai grafi
4. definizioni e proprietà
5. rappresentazioni dei grafi e loro proprietà

1. Visita DFS ricorsiva
2. DFS iterativa
3. significato delle marcature
4. proprietà della DFS
5. costo DFS
6. DAG e ordini parziali
7. definizione topological sort

Bacheca di Algoritmi e Strutture Dati a.a. 2007-08 - canale A - L

forum del corso

ultima modifica: 03/04/2008 23.36

by FdA