Next: About this document ...
Quarto Scritto
ASD1 2002-2003
Exercise 2
Si determini l'andamento asintotico nel caso peggiore
di un tempo di calcolo
soggetto
alla seguente ricorrenza
E nel caso migliore?
Exercise 3
Ordinare le seguenti funzioni per ordine di crescita asintotico non
decrescente, ove
sia una costante positiva comune.
Ve ne sono alcune che presentano lo stesso ordine di crescita?
Come cambia la situazione per
?
,
,
,
,
.
Exercise 4
Un grafo
di dice
bipartito
se posso bipartizionare
in due sottoinsiemi
disgiunti
e
tali che ogni arco in
abbia un estremo in
e l'altro in
.
- Dimostrare che un grafo è bipartito
se e solo se non contiene cicli dispari.
- Descrivere un algoritmo con tempo di calcolo
(ossia lineare)
che dato in input un grafo connesso
restituisca o una dimostrazione che
non è bipartito (ciclo dispari)
od una dimostrazione che
è bipartito (una bipartizione valida ).
Exercise 5
Si descrivano in maniera efficace
gli Heaps binomiali
e le relative operazioni.
(L'obiettivo è dimostrarmi che avete colto
il principio di funzionamento di questa struttura dati.
Cercate quindi di puntare al nocciolo. Nel dubbio,
confrontatevi con me. Non perdete tempo).
Next: About this document ...
Romeo Rizzi
2003-06-23