ASD ew( 06 2005 4

7. (1+3+1)

Pewien zbiór miast, oznaczonych liczbami 1.2,3,4,5.6.7, chcemy połączyć autostradami w taki sposób aby z dowolnego miasta można było przejechać korzystając tylko z autostrad, do dowolnego innego. Dla każdej pary miejscowości x, y, koszt wykonania autostrady, która by je połączyła bezpośrednio wynosi (x +y) mod 5+1. Przedsiębiorstwo AUTOSTRADA, wykonujące całość zadania, chce wybudować autostrady w taki sposób, by koszt całego przedsięwzięcia był jak najmniejszy. Problem polega na tym jak wybrać miejscowości, które powinny być bezpośrednio połączone.

Zadanie właściwe:

(a)    Zaproponuj metodę postępowania, która pozwoli rozwiązać ten problem.

(b)    Przedstaw kolejne etapy działania zaproponowanego algorytmu.

(c)    Narysuj otrzymaną sieć autostrad i oblicz koszt jej budowy.

8. (1+2)

Pewien zbiór X złożony z n elementów zapisano w tablicy.

a. Oszacuj możliwie najlepiej koszt sekwencyjnego wyszukiwania dowolnego elementu w tym zbiorze b. Załóżmy, że elementy zbioru zostały wpisane do tablicy w porządku rosnącym. Opisz ideę optymalnego algorytmu wyszukiwania dowolnie wskazanego elementu. Jaki jest jego koszt?