Zestaw 1.

1. Def. Drzewa i jego elementów

2. Lista incydencji (opisać), jaka jest złożoność pamięciowa alg. tworzącego listę incydencji

3. Def. Listy dwukierunkowej, schemat listy

4. Omów podział alg. sortowania ze względu na złożoność obliczeniowa

5. Kiedy drzewo binarne staje się kopcem

6. Def. Metody dziel i zwyciężaj

7. Wyznacz oczekiwaną złożoność czasową dla przeszukiwania sekwencyjnego

8. Kiedy alg. Jest całkowicie poprawny a kiedy częściowo

9. W jakim celu stosowane jest sprawdzanie warunku w algorytmie?

10. Jakie cechy powinien mieć algorytm w sensie informatycznym

1. .Drzewo algorytmu (obliczeń):korzeń - wierzchołek, w którym rozpoczyna się działanie algorytmu. Wierzchołki pośrednie w których umieszczone są operacje w programie. Wierzchołki końcowe (liście) ,które odpowiadają różnym wynikom zakończenia obliczeń w algorytmieDrzewo wyrażenia: ma ograniczone, zastosowanie jako reprezentacja algorytmu - jest przede wszystkim stosowana do obliczania wartości wyrażeń arytmetycznych zawierających nawiasy

2. LISTA INCYDENCJI

Lista krawędzi - jest to lista, na której przechowujemy wszystkie krawędzie występujące w grafie.

Macierz incydencji to tablica o rozmiarach V*E. Sklada się z E kolumn i V wierszy

- jeśli krawędź wychodzi z danego wierzcholka to piszemy w odpowiedniej kolumnie l-1

-jeśli do niego wchodzi piszemy l+1

jeśli wierzcholek nie należy do krawędzi piszemy 0

jeśli jest to petla wlasna piszemy 2

Macierz grafu: tablica o rozmiarach (V+2)^2. Wierzcholki i krawędzie numerujemy od 0 do v+1

3. Listy dwukierunkowe: maja dwa wskazniki co przyspiesza wszystkie operacje. mozna sie poruszac w 2 kierunkach

4. 1 algorytmy w których liczba porównań jest proporcjonalna do kwadratu liczby elementów n^2 - sortowanie bąbelkowe

przez umieszczanie (l.por<n^2 ale l. przestawień może być tego rzędu)

algorytm szybki Algorytm w których liczba porównań i zamian jest proporcjonalna do nlogn - alg przez scalanie

5. 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.

6. Dziel i rządź: 1 Podzielić problem na podproblemy. 2 Znalezienie rozwiązania podproblemów. 3 Połączenie rozważanych podproblemów w rozwiązanie głownego problemu.

7. przeszukiwanie sekwencyjne ciągu

Begin

i:=1;

L[N+1]:=a;

While L[j]<>a do

j:=j+1

if j<=N then p:=j

end

Rozmiar danych wejściowych- |d|=n

Operator porównania-L[j]<>a

Pesymistyczna złożoność czasowa- Tmax(n)=n+1

Pesymistyczna wrażiwość czasowa- delta(n)=n

Wyznaczanie oczekiwanej złożoności czasowej

Pr(d)=1/n; t(d)=k dla k=1,2,...,n

Wówczas oczekiwana(średnia) złożoność czasowa

Tśr(n)=E(od k=1 do n) pr(d)*t(d)=1/nE(od k=1 do n) t(d)= 1/nE(od k=1 do n) k

Tśr(n)=n(n+1)/2n =n+1/n

f(d)- liczba operacji elementarnych wykonanych dla danych wejściowych „d”

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

8. WP-warunek początkowy-formuła logiczna definiująca dane wejściowe algorytmu

WK-warunek końcowy-formuła logiczna definiująca dane wyjściowe algorytmu uzyskane dla danych wejściowych spełniających WP

Definicje

Algorytm A jest częściowo poprawny wzglądem danego warunku WP i danego warunku WK wtedy i tylko wtedy, gdy dla dowolnych danych wejściowych spełniających warunek Wp, jeżeli algorytm A zatrzymuje się to dane wyjściowe algorytmu spełniają warunek WK

Algorytm A jest całkowicie poprawny- def wyżej, ale bez „jeżeli”

Przykład:

WP: n>0 i n należy do N

WKs=1+3+5+...+n i n mod 2<>0 lub

S=1+3+5+...+n-1 i n mod 2=0

Algorytm

S:=0 i i:=0

While i<>n+2 do

Begin

s:=s+i

i:=i+2

end

Algorytm jest poprawny częściowo, gdyż gdy n jest parzyste -zapętla się

9.

10. komputerowychAlgorytm w sensie informatycznym powinien : posiadać dane wejściowe(w ilości x>=0),generować określony wynik, być precyzyjnie zdefiniowany, być skończony.

---