Zestaw 5

1. Kiedy sortowanie jest stabilne?

2. Co to jest wywołanie terminalne?

3. Miara wrażliwości pesymistycznej i oczekiwanej. Określ elementy wpływające na powyższe pojęcia.

4. jakie elementy należy uwzględnić podczas badania złożoności czasowej algorytmu

5. Podaj definicję cyklu Hamiltona a także przykład

6. Podaj definicje minimalnego drzewa rozpinającego a także przykład

7. Opisz macierz sąsiedztwa na wybranym przykładzie

8. Opisz dodawanie nowego elementu do listy jednokierunkowej posortowanej

9. porównaj strukturę kopca i dwukopca na wybranym przykładzie

10. Podaj definicje sortowania szybkiego omów na przykładzie

1. Stabilnymi algorytmami nazywamy algorytmy w których jeśli 2 elementy w porządkowanym ciągu mają taka samą wartość pewnej cechy , wg której odbywa się porządkowanie to ich kolejność względem siebie w uporządkowanym ciągu jest taka sama jak w danym ciągu danym do posortowania

2. Procedura iteracyjna jest równoważna procedurze rekurencyjnej P, jeśli wykonuje dokładnie to samo zadanie co P ,dając identyczne rezultaty.Wywoływanie rekurencyjne procedury P jest zwane terminalnym ,jeśli nie następuje po nim już żadna instrukcja tej proceduryProcedury P1 i P2 są wzajemnie równoważne pod warunkiem że P1 zawiera tylko jedno rekurencyjne wywołanie terminalne

3. Miara wrażliwości pesymistycznej

Delta(n)=max{t(d1)-t(d2):d1,d2 należy do Dn}

Miara wrażliwości oczekiwanej

Sigma(n)=dev(Xn)

Gdzie dev(Xn)-odchylenie standardowe zmiennej losowej „xn” dev(Xn)=sqrt(var(Xn))

Var(Xn)-wariacja zmiennej losowej „Xn” var(Xn)=E(k>0)((k-are(Xn))^2 pr(d))

Are(Xn)wartość oczekiwanej zmiennej losowej Xn

Twierdzenie:

Im większe są wartości delta(n) i sigma(n), tym algorytm jest bardziej wrażliwy na dane wejściowe i tym bardziej jego zachowanie w wypadku rzeczywistych danych może odbiegać od zachowania opisanymi funkcjami pesymistycznej i oczekiwanej złożoności czasowej.

4. Złożoność czasowa-czas działania algorytmu, wyrażony liczbą jego operacji Złożoność czasowa pesymistyczna- ilość wykonywanych operacji elementarnych dla danych „najgorszego” przypadku.

Złożoność czasowa oczekiwana- ilość wykonywanych operacji elementarnych dla danych „typowego” przypadku.

Definicja

Oznaczenia:

Dn- zbiór zestawów danych wejściowych rozmiaru n

t(d)- liczba operacji elementarnych wykonywanych dla danych wejściowych ”d”

pr(d)-prawdopodobieństwo, że dane ”d” są danymi wejściowymi algorytmu

Pesymistyczna złożoność czasowa algorytmu to funkcja(max-to kres górny zbioru)

Tmax(n)=max{t(d):d należy do Dn}

Oczekiwana(średnia) złożoność czasowa algorytmu to funkcja

Tśr(n)=E(d należy do Dn) pr(d).t(d)

Tym, czy funkcje Tmax i Tśr(n) są reprezentowane dla wszystkich danych wejściowych rozmiaru n decydują miary wrażliwości algorytmu.

5. CYKL HAMILTONA

Graf go posiada jeśli istnieje w nim cykl droga,( która zaczyna się i konczy w tym samym wierzchołku), który zawiera każdy wierzcholek dokladnie raz.

6 Niech będzie dany sojny graf nie skierowany o wierzcholkach v i krawędziach E.

Ponad to z kazda krawędzią będzie zwiazana tkz. waga, okreslana przez funkcje, która oznacza długość danej krawędzi

Jeżeli znajdziemy taki podzial T zawarty w zbiorze krawędzi E, który laczy wszystkie wierzcholki i taki, ze suma wszystkich wag krawędzi wchodzących w sklad T jest możliwie najmniejszy, to znajdziemy tzw. min. drzewo rozpinające.

7.

8. Nowy element może zostac wstawiony na poczatek, koniec lub w srodku listy posortowanej;;; należy znalezc miejsce wstawienia;

9 Kopiec (ang. heap) to drzewo binarne o następujących cechach:

klucze potomków węzła są w stałej relacji z kluczem rodzica, drzewo jest prawie pełne tzn. liście występują na ostatnim i ewentualnie przedostatnim poziomie w drzewie, liście na ostatnim poziomie są ściśle ułożone od lewej do prawej.

Dwukopiec- swoja budowa przypomina kopiec, posiada dwoch potomkow i dwoch przodkow, na pierwszym miejscu jestt korzen, interpretacja- tablica, kopiec est dzrewem binarnym

10. Quicksort - szybki algorytm sortowania jest realizowany w szeregu bibliotek

Algorytm ten polega na podziale uporządkowanego ciągu elementów r na dwie takie części, że w jednym znajdują się liczby nie większe niż r a w drugiej liczby nie mniejsze niż r

Następnie element r umieszczamy miedzy tymi podciągami i przechodzimy do sortowania obu podciągów tą sama metoda.

Kolejne wyniki wywołań rekurencyjnych - każdy następny wiersz zawiera o jeden element więcej, który w następnej iteracji zostanie wybrany do podziału i zajmuje swoją stałą pozycje w porządkowanym ciągu.

---