To tylko jedna z 8 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
© 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)