Next: About this document ...
Fac Simile di Scritto (A)
ASD1 2002-2003
Exercise 2
Dimostrare che
![$\sum_{t=1}^n t^k = \Theta(n^{k+1})$](img7.png)
,
per ogni numero naturale
![$n$](img8.png)
.
Exercise 3
Ordinare le seguenti funzioni per ordine di crescita asintotico non
decrescente, ove
![$k>2$](img9.png)
sia una costante positiva comune.
Ve ne sono alcune che presentano lo stesso ordine di crescita?
Come cambia la situazione per
![$k=1$](img10.png)
?
E cosa succede per
![$0<k<1$](img11.png)
?
![$f(n)= \log n^k$](img12.png)
,
![$f(n)=\log n^{\log n}$](img13.png)
,
![$f(n)= \log^k n$](img14.png)
,
![$f(n)= 2^{\log_k n}$](img15.png)
.
Exercise 4
Un grafo di dice
Euleriano
se è connesso ed ogni nodo ha grado pari.
Un cammino che parta da un nodo
![$v_0$](img16.png)
,
attraversi tutti gli archi una ed una sola volta
(possibilmente ripassando per uno stesso nodo più di una volta),
ritornando infine in
![$v_0$](img16.png)
,
è detto un
cammino Euleriano.
- Dimostrare che un grafo
ammette un cammino Euleriano se e solo se è Euleriano.
- Descrivere un algoritmo con tempo di calcolo
(ossia lineare)
che dato in input un grafo Euleriano
restituisca un cammino Euleriano in
.
Exercise 5
Si consideri il seguente algoritmo di Trémaux.
- 1.
- mi risveglio in una stanza di un labirinto ignoto;
- 2.
- finchè vi è un cunicolo che esca dalla stanza in cui mi trovo
ed il cui imbocco non sia stato ancora marcato
- 3.
- scelgo uno dei cunicoli non marcati,
ne marco l'imbocco con una croce, e lo attraverso;
- 4.
- come giungo nella stanza all'altra estremità del cunicolo,
se mi ritrovo in una nuova stanza,
allora marco l'imbocco che mi ha ivi condotto con una
;
altrimenti, lo marco con una croce, e ripercorro il cunicolo a ritroso;
- 5.
- se nella stanza in cui mi trovo vi è un cunicolo marcato con
,
allora attraverso tale cunicolo e vado al Passo 2;
- 6.
- altrimenti, la mia esplorazione è finita.
Dimostrare che ogni arco viene attraversato,
nella stessa direzione, al più una volta.
Se ne deduca un upper bound sul tempo di calcolo.
Si dimostri che se il grafo è connesso allora
ogni arco viene attraversato precisamente una volta
in entrambe le direzioni.
Next: About this document ...
Romeo Rizzi
2002-11-14