Lgorytmy i metody obliczeń - omówienie

Nasza ocena:

3
Pobrań: 63
Wyświetleń: 679
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Lgorytmy i metody obliczeń - omówienie - strona 1 Lgorytmy i metody obliczeń - omówienie - strona 2 Lgorytmy i metody obliczeń - omówienie - strona 3

Fragment notatki:

© 2007 cih997  – 1 –  1.  Algorytmy i modele obliczeń    --- podstawowe pojęcia ---  - algorytm – przepis prowadzący do rozwiązania określonego zadania  - modele obliczeń – zestaw dostępnych poleceń  + maszyna ze swobodnym dostępem do pamięci (RAM)  + maszyna ze swobodnym dostępem do pamięci i pamiętanym programem        (RASP)  + maszyna turinga  - dziedzina algorytmiczna – zbiór obiektów i dostępnych w nich pierwotnych                  operacji  - cechy algorytmu      - analiza algorytmów – poprawność + złoŜoność obliczeniowa  - poprawność algorytmu – dot. pojęć i metod związanych z dowodzeniem                  poprawności alg. (własność stopu, częściowa poprawność, metoda                     niezmienników, itp.)    --- złoŜoność algorytmu ---  - rozmiar zadania – konkretna liczba charakteryzująca obj. danych wejściowych  - złoŜoność czasowa – czas potrzebny na wykonanie algorytmu  - asymptotyczna złoŜoność czasowa – charakter złoŜoności czasowej przy            dąŜeniu do wartości granicznej wraz ze wzrostem rozmiaru zadania  - notacje asymptotyczne  + f(n) jest O(g(n))   0 ≤ f(n) ≤ cg(n)  + f(n) jest  (g(n))   cg(n) ≤ f(n)  + f(n) jest Θ(g(n))   c1g(n) ≤ f(n) ≤ c2g(n)     --- model obliczeniowy RAM ---  - schemat maszyny RAM    + taśma wejściowa – ciąg klatek zawierających liczby całkowite    + taśma wyjściowa    + pamięć    --- pseudokod ---  - operatory pseudokodu    + zmienna   wartosć – przypisanie wartości zmiennej    + jeśli ... to ... inaczej – warunek    + dopóki ... wykonuj – pętla dopóki    + powtarzaj ... aŜ_do – pętla powtarzaj    + dla ...   ... [w_dół_]do ... wykonuj – pętla dla     --- złoŜoność pesymistyczna i oczekiwana ---  - złoŜoność obliczeniowa – określanie zasobów (czas i pamięć) jakie są                   potrzebne do wykonania badanego algorytmu  - jednostka złoŜoności maszyny – słowo pamięci maszyny  - operacje dominujące – charakterystyczne operacje dla danego algorytmu     o liczbie proporcjonalnej do liczby wykonań wszystkich operacji jednostkowych     w dowolnej realizacji komputerowej danego algorytmu  © 2007 cih997  – 2 –  - jednostka złoŜoności czasowej – wykonanie jednej operacji dominującej   - złoŜoność pesymistyczna – mówimy o niej, gdy dla ustalonego rozmiaru    wejścia w charakterze miary złoŜoności przyjąć największą ze złoŜoności dla 

(…)

… tylko jedna krawędź
- drzewo nieskierowane – graf nieskierowany spójny, acykliczny, ma korzeń
- drzewo binarne – jest to drzewo, gdzie:
1. KaŜdy węzeł posiada co najwyŜej dwóch synów
2. Wśród synów kaŜdego węzła wyróŜniamy lewego i prawego
- potomek – w drzewie skierowanym jest wtedy, gdy istnieje droga od v do w to
w jest potomkiem; w drzewie niezorientowanym węzeł v jest połoŜony
wyŜej w strukturze
- poddrzewo…

- kolejka
- ENQUEUE – dodawanie do kolejki, DEQUEUE – usuwanie z kolejki
- zapis postfiksowy oraz infiksowy, potrzebne algorytmy
–4–
© 2007 cih997
--- grafy ---
- graf – para zbiorów G = (V, E) gdzie V – wierzchołki, E – krawędzie
- stopień wierzchołka – graf niekierowany: liczba incydentnych z nim krawędzi;
graf skierowany: stopień wyjściowy i wejściowy, ^ analogicznie 8)
- ścieŜka w grafie – to skończony…

- rząd drzewa – jest k, jeśli stopień dowolnego węzła nie przekracza k
- metody przechodzenia węzłów drzewa binarnego
1. preorder
–5–
© 2007 cih997
2. postorder
3. inorder
- reprezentacja drzewa binarnego za pomocą wskaźników
–6–
© 2007 cih997
3. Drzewa i algorytmy przeszukiwania
--- BST ---
- drzewa przeszukiwań binarnych (BST) – klasa drzew binarnych dla której
łatwo skonstruować podstawowe algorytmy…
… wszystkich węzłów z podanego kryterium
a nie tylko pierwszego
- generowanie dróg rozwiązań – droga w drzewie przeszukiwań od stanu
początkowego do rozwiązania
4. Sortowanie
--- ogólnie ---
- sortowanie – polega na zmianie kolejności elementów pewnego ciągu tak, aby
zostały one ustawione w porządku niemalejącym bądź nierosnącym
- częściowy porządek – cz. p. na zbiorze S nazywamy relację R o
właściwościach
1…
... zobacz całą notatkę



Komentarze użytkowników (0)

Zaloguj się, aby dodać komentarz