Ponadto w notatce można znaleźć: przeszukiwanie grafu wszerz, przeszukiwanie grafu wgłąb. problem znajdowania najkrótszej drogi, problem chińskiego listonosza, problem komiwojażera.
AKGORYTMY I STRUKTURY DANYCH pytania na egzamin + opracowanie
1) Wprowadzenie do algorytmów (cechy algorytmu, paradygmaty tworzenia, etapy konstruowania, sposoby zapisu, struktury sterujące).Cechy algorytmu:Algorytm musi być:Poprawny - tzn., dla każdego zestawu danych, po wykonaniu skończonej liczby czynności, prowadzi do poprawnych wyników,Jednoznaczny, tzn., w każdym przypadku jego zastosowania, dla tych samych danych uzyskamy ten sam wynik,Szczegółowy - aby wykonawca algorytmu rozumiał opisane czynności i potrafił je wykonać,Uniwersalny, aby posłużył do rozwiązywania pewnej grupy zadań, a nie tylko jednego zadania (np. algorytm jest przepisem na rozwiązanie równania postaci ax+b=0 dla dowolnych współczynników a i b, a nie - jednego konkretnego równania, np. 2x+3=0.
Podstawowe paradygmaty tworzenia algorytmów komputerowych:
dziel i zwyciężaj - dzielimy problem na kilka mniejszych, a te znowu dzielimy, aż ich rozwiązania staną się oczywiste,
programowanie dynamiczne - problem dzielony jest na kilka, ważność każdego z nich jest oceniana i po pewnym wnioskowaniu wyniki analizy niektórych prostszych zagadnień wykorzystuje się do rozwiązania głównego problemu,
metoda zachłanna - nie analizujemy podproblemów dokładnie, tylko wybieramy najbardziej obiecującą w tym momencie drogę rozwiązania,
programowanie liniowe - oceniamy rozwiązanie problemu przez pewną funkcję jakości i szukamy jej minimum,
poszukiwanie i wyliczanie - kiedy przeszukujemy zbiór danych aż do odnalezienia rozwiązania,
algorytm probabilistyczny - algorytm działa poprawnie z bardzo wysokim prawdopodobieństwem, ale wynik nie jest pewny,
heurystyka - człowiek na podstawie swojego doświadczenia tworzy algorytm, który działa w najbardziej prawdopodobnych warunkach, rozwiązanie zawsze jest przybliżone.
Etapy konstruowania algorytmu:1. Sformułowanie zadania.2. Określenie danych wejściowych.3. Określenie wyniku oraz sposobu jego prezentacji.4. Ustalenie metody wykonania zadania.5. Przy użyciu wybranej metody następuje zapisanie algorytmu.6. Dokonujemy analizy poprawności rozwiązania.7. Testowanie rozwiązania dla różnych danych.8. Ocena skuteczności tegoż algorytmu.
Sposoby zapisu algorytmu:1. Zapis algorytmu w postaci listy kroków.2. Zapis algorytmu w pseudojęzku.3. Zapis algorytmu za pomocą schematu blokowego.4. Zapis algorytmu w języku programowania.
Podstawowe struktury sterujące to:
bezpośrednie następstwo - wykonaj instrukcję A, potem instrukcję B, potem instrukcję C, itd.
wybór warunkowy - jeśli warunek Q jest spełniony wykonaj instrukcję A, jeśli nie to wykonaj instrukcję B.
iteracja ograniczona - wykonaj instrukcję A dokładnie N razy.
iteracja warunkowa „dopóki” - dopóki warunek Q jest spełniony wykonuj instrukcję A.
Iteracja warunkowa „aż do” - wykonuj instrukcję A dopóki warunek Q jest spełniony.
(…)
…) od elementu x[k], to zmiennej k przypisujemy wartość i
3. Element minimalny to element o indeksie k. Jego wartość to x[k]. Kończymy algorytm.
Algorytm jest bardzo prosty. Oto idea algorytmu (różni się od realizacji): Zakładamy, że elementem najmniejszym jest pierwszy element. Następnie każdy następny element porównujemy z elementem pierwszym i jeśli element ten jest mniejszy od pierwszego elementu…
… - strategia podziału pomaga nam w szybkim osiągnięciu zwycięstwa nad problemem, czyli w szybkim znalezieniu poszukiwanego elementu.
Algorytmy tekstowe mają decydujące znaczenie przy wyszukiwaniu informacji typu tekstowego, ten typ informacji jest szczególnie popularny w informatyce, np. w edytorach tekstowych i wyszukiwarkach internetowych. Tekst jest ciągiem symboli. Przyjmujemy, że jest on zadany tablicą…
…/siecznych, ale stycznymi.
7) Numeryczne metody interpolacji (definicja interpolacji, zastosowania, interpolacja wielomianowa, interpolacja Lagrange?a, interpolacja Newtona, interpolacja Taylora, interpolacja funkcjami sklejanymi).
Interpolacja - metoda numeryczna polegająca na wyznaczaniu w danym przedziale tzw. funkcji interpolacyjnej, która przyjmuje w nim z góry zadane wartości w ustalonych punktach, nazywanych węzłami. Stosowana jest ona często w naukach doświadczalnych, gdzie dysponuje się zazwyczaj skończoną liczbą danych do określenia zależności między wielkościami oraz w celu uproszczenia skomplikowanych funkcji, np. podczas całkowania numerycznego. Interpolacja jest szczególnym przypadkiem metod numerycznych typu aproksymacja.
zastosowania interpolacji:
zastępowanie skomplikowanego wzoru funkcji…
…, itd.
wybór warunkowy - jeśli warunek Q jest spełniony wykonaj instrukcję A, jeśli nie to wykonaj instrukcję B.
iteracja ograniczona - wykonaj instrukcję A dokładnie N razy.
iteracja warunkowa „dopóki” - dopóki warunek Q jest spełniony wykonuj instrukcję A.
Iteracja warunkowa „aż do” - wykonuj instrukcję A dopóki warunek Q jest spełniony.
2) Algorytmy rekurencyjne( definicja rekurencji, schemat…
... zobacz całą notatkę
Komentarze użytkowników (0)