Zestaw 2.

1. Co to jest i co zawiera schemat blokowy algorytmu

2. Co to jest rekurencja? Jakie są cechy algorytmu rekurencyjnego?

3. Podaj definicje złożoności obliczeniowej, pamięciowej i czasowej

4. Def. rzędu funkcji Jaki jest rząd funkcji n⁵+2n

5. Opisz algorytm wyszukiwania binarnego oparty na metodzie dziel i zwyciężaj. Wyznacz Złożoność czasowa i pesymistyczną algorytmu.

6. Narysuj Schemat blokowy alg. Sortowania szybkiego

7. Def. wartości prostych i złożonych danych

8. Opisz operacje wstawiania elementów do dwukopca

9. Podaj definicję kolejki Wymień operacje na kolejce

10 Opisz listę incydencji jaka jest złożoność pamieciowa algorytmu tworzącego listę incydencji

1. Schemat blokowy - składa się z bloków - klatek, połączeń pomiędzy nimi.W blokach zapisywane są operacje, które mamy wykonać .

Reguły łączenia bloków : do każdego bloku może dochodzić dowolna liczba strzałek, z każdego bloku(oprócz decyzyjnego) może wychodzić tylko jedna strzałka, blok graniczny lub łącznik może być pozbawiony jednej ze strzałek(dochodzącej lub wychodzącej).Pozostałe bloki muszą mieć zarówno strzałkę dochodzącą jak i wychodzącą,

Schemat blokowy powinien być uzupełniony o listę nazw z nazwami wszystkich zmiennych użytych w schemacie

2. Rekurencja - zaawansowana technika algorytmiczna ,polegająca na wywoływaniu procedury z wnętrza samej siebie .W wyniku rekurencji algorytm zostaje zagnieżdżony .Zakończenie procedury zewnętrznej wykonywane jest wtedy ,gdy zakończy się wywoływana przez nią procedura wewnętrzna.

Cechy algorytmu rekurencyjnego :zakończenie algorytmu musi być jednoznacznie określone (element znaleziony lub przekroczenie zakresu tablicy),rozbicie dużego problemu na problemy elementarne o mniejszym stopniu skomplikowania ,które możemy rozwiązać (z tablicy o rozmiarze n przechodzimy do tablicy o rozmiarze n-1)

Podstawowe błędy algorytmów rekurencyjnych : złe określanie zakończeń programu ,niewłaściwa (nieefektywna) dekompozycja problemu

3. Złożoność obliczeniowa to ilość zasobów komputerowych potrzebnych do jego wykonania

Złożoność obliczeniowa-złożoność algorytmu, miara jakości algorytmu wyrażana liczbą wykonywanych w nim elementarnych operacji, takich jak +-* lub porównanie.Zbliżone do złożoności obliczeniowej jest pojęcie efektywności, czyli czasu działania wykonującego algorytm programu komputerowego.

Złożoność czasowa-czas działania algorytmu, wyrażony liczbą jego operacji

Złożoność pamięciowa- zapotrzebowanie algorytmu na pamięć, wyrażona liczbą koniecznych do jego działania jednostek informacji

4. Funkcja f jest:1) co najwyżej rzędu g: f(n)=O(g(n)): 2) co najmniej rzędu g f(n)=Ω(g(n)), jeśli funkcja g jest co najwyżej rzędu f g(n)=O(f(n)) 3) dokładnie rzędu g, co zapisujemy jako f(n)=Θ(g(n)) jeśli zarówno f(n)=O(g(n)) jak i f(n)=Ω(g(n)) 4) jest asymptotycznie równoważna g, co oznaczamy jako f(n)≈g(n)

Rząd wielkości dwóch funkcji f(n) i g(n) mogą być porównywane przez obliczenie granicy E=lim[f(n)/g(n)]. Jeśli E=+∞, to g(n)=O(f(n)). Jeśli E=c>0 to f(n) ≈g(n). Jeśli E=0, to f(n)=O(g(n)).

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

6. D sortowany zbiór

ipp indeks pierwszego elementu partycji do posortowania

ipk indeks końcowego elementu partycji do posortowania

pivot wartość elementu środkowego potrzebna do ustalenia kolejności elementów przy pomocy funkcji porównującej

di i-ty element zbioru D

ilewy indeks elementu na lewo od pivotu

iprawy indeks elementu na prawo od pivotu

fp( ) funkcja porównująca określająca mocny porządek

7. Przez DANA rozumiemy uporządkowaną parę <n,i> której pierwszym elementem jest nazwa danej a drugim jej wartość

Wartość

- wartości prostych - niepodzielne

- wartości złożonych - są strukturami ( uporządkowanymi zbiorami danych których wartości mogą być wartościami prostymi lub klejonymi wartościami złożonymi

Uznanie wartości za wartości proste jest w pewnym sensie zależne od celów danego przetwarzania

Dana d=<n,r> nazywamy dana elementarna, jeżeli r jest wartością prostą. Dane elementowe są najmniejszymi adresowalnymi jednostkami informacji.

Dane, które nie są danymi elementami nazywamy danymi złożonymi

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

9. Kolejka- lista el zwiekszajaca się przed dodawanie el na jej koncu, a malejaca przy wykmowaniu el z poczatku, FIFO

Operacje na kolejce: initializa, oroznienie kol, empty sprawdzenie stosu czy jest pusty, full- sprawdzenie kol czy jest zapelninony, push- umieszczenie elementu na kol, pop- zdjecia najwyzszego el z kolejki. Enq- powoduje umieszczenie el. Na koncu kolejki, deq- usuniecie pierwszego el. Jedna z możliwych implementacji kolejki jest tablica.

Kolejka priorytetowa- el. W kol. Maja rozne priorytety

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

---