Nazwa forum

1.    Pojęcie algorytmu w tym algorytmu rekurencyjnego.
Dział I pytanie 1.
2.    Podstawowe algorytmy: sortowanie, selekcja, wyszukiwanie.
Celem algorytmu sortowania jest uporządkowanie ciągu nieuporządkowanych wyrazów w zadanej kolejności. Znanych jest wiele algorytmów sortujących. Do najpopularniejszych należą
-Sortowanie bąbelkowe - Polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona porządek, w jakim się sortuje tablicę (malejąco, rosnąco). Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmiany.
-Sortowanie przez wybieranie- Polega na wyszukaniu elementu mającego się znaleźć na zadanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Operacja jest wykonywana dla wszystkich indeksów sortowanej tablicy.
Algorytm przedstawia się następująco:
1.    wyszukaj minimalną wartość z tablicy spośród elementów od i+1 do końca tablicy
2.    zamień wartość minimalną, z elementem na pozycji i

-Sortowanie przez wstawianieAlgorytm polega na usuwaniu pewnego elementu z danych wejściowych i wstawianiu go na odpowiednie miejsce w wynikach. Wybór następnego elementu z danych jest dowolny
Schemat działania algorytmu
1.    Utwórz zbiór elementów posortowanych i przenieś do niego dowolny element ze zbioru nieposortowanego.
2.    Weź dowolny element ze zbioru nieposortowanego.
3.    Wyciągnięty element porównuj z kolejnymi elementami zbioru posortowanego póki nie napotkasz elementu równego lub elementu większego (jeśli chcemy otrzymać ciąg niemalejący) lub nie znajdziemy się na początku/końcu zbioru uporządkowanego.
4.    Wyciągnięty element wstaw w miejsce gdzie skończyłeś porównywać.
5.    Jeśli zbiór elementów nieuporządkowanych jest niepusty wróć do punkt 2.

-Sortowanie przez scalanie Algorytm ten jest dobrym przykładem algorytmów typu Dziel i zwyciężaj (ang. divide and conquer), których ideą działania jest podział problemu na mniejsze części, których rozwiązanie jest już łatwiejsze.
Wyróżnić można trzy podstawowe kroki:
1.    Podziel zestaw danych na dwie, równe części (w przypadku nieparzystej liczby wyrazów jedna część będzie o 1 wyraz dłuższa);
2.    Zastosuj sortowanie przez scalanie dla każdej z nich oddzielnie, chyba że pozostał już tylko jeden element;
3.    Połącz posortowane podciągi w jeden.
Procedura scalania dwóch ciągów A[1..n] i B[1..m] do ciągu C[1..m+n]:
1.    Utwórz wskaźniki na początki ciągów A i B → i=1, j=1
2.    Jeżeli ciąg A wyczerpany (i>n), dołącz pozostałe elementy ciągu B do C i zakończ pracę.
3.    Jeżeli ciąg B wyczerpany (j>m), dołącz pozostałe elementy ciągu A do C i zakończ pracę.
4.    Jeżeli A[i] ≤ B[j] dołącz A[i] do C i zwiększ i o jeden, w przeciwnym przypadku dołącz B[j] do C i zwiększ j o jeden
5.    Powtarzaj od kroku 2 aż wszystkie wyrazy A i B trafią do C

-Quicksort – sortowanie szybkie - Algorytm działa rekursywnie - wybierany jest pewien element tablicy, tzw. element osiowy, po czym na początek tablicy przenoszone są wszystkie elementy mniejsze od niego, na koniec wszystkie większe, a w powstałe między tymi obszarami puste miejsce trafia wybrany element. Potem sortuje się osobno początkową i końcową część tablicy. Rekursja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, jako że jednoelementowa podtablica nie wymaga sortowania
Algorytm selekcji polega na wybraniu k-tego kolejnego elementu z nieposortowanej listy tak jakby lista była posortowana. Celem użycia algorytmu jest uzyskanie tego elementu bez konieczności sortowania listy a co za tym idzie szybsze jego odnalezienie.
Algorytmy wyszukiwania mają podać indeks poszukiwanego wyrazu w ciągu posortowanym, lub stwierdzić brak takiego wyrazu.
Zadanie to można rozwiązać poprzez dużą złożoność obliczeniową sprawdzając po kolei każdy wyraz ciągu lub zastosować szybsze algorytmy. Przykładowe algorytmy wyszukiwania
Przeszukiwanie liniowe (lub wyszukiwanie sekwencyjne) to najprostszy algorytm wyszukiwania informacji w ciągu danych, np. zapisanych w tablicy lub na liście. Polega na porównywaniu żądanego klucza z kolejnymi kluczami z sekwencji danych – wyszukiwanie kończy się powodzeniem, gdy zostanie znaleziony klucz, albo niepowodzeniem, gdy zostaną przejrzane wszystkie klucze.
-Wyszukiwanie binarne jest algorytmem opierającym się na metodzie dziel i zwyciężaj, który w czasie logarytmicznym stwierdza, czy szukany element znajduje się w uporządkowanej tablicy i jeśli się znajduje, podaje jego indeks. Uporządkowana tablica jest dzielona na coraz mniejsze przedziały do momentu, gdy szukany element zostanie znaleziony, bądź przedział osiągnie długość zero, co oznacza brak elementu.
3.    Abstrakcyjne struktury danych: listy, drzewa, grafy, słowniki, drzewa poszukiwań binarnych, stosy, kolejki.
Kiedy chcemy skorzystać z dodatkowej pamięci, nie wiedząc z góry ile nam jej będzie potrzeba i uzależniając jej ilość od danych, których wartości nie są znane, wygodnie jest używać mechanizmu dynamicznej alokacji pamięci.
Listy czyli struktury, które umożliwiają tworzenie ciągów danych w taki sposób, że każda dana pamięta gdzie się znajduje kolejna. Są to listy jednokierunkowe. Można także tworzyć listy dwukierunkowe w których każda dana pamięta gdzie znajduje się kolejna ale także gdzie znajduje się poprzednia.
Drzewa stanowią podstawę wielu ważnych algorytmów. Te pożyteczne struktury danych pozwalają organizować informację w sposób umożliwiający zarówno szybkie do niej dotarcie (jak w przypadku tablic), jak i szybką modyfikację: usuwanie i dodawanie nowych danych (jak to ma miejsce w przypadku list). Nadają się one więc doskonale do reprezentowania zbiorów skończonych, które w zastosowaniach informatycznych powstają najczęściej przez dodawanie kolejnych elementów, usuwanie ich i sprawdzanie, czy dany element znajduje się w zbiorze (typowe operacje bazodanowe). Jedyną istotną różnicą między listami a drzewami jest to, że każdy element listy ma co najwyżej jeden następnik, a węzeł drzewa (czyli odpowiednik elementu listy) może mieć ich kilka. Jeśli ma co najwyżej dwa, to takie drzewo nazwiemy binarnym
Grafy ????
Słownik to struktura danych reprezentująca dynamiczny (tzn. mogący zmieniac się w czasie) zbiór elementów (kluczy), na którym można wykonywać następujące operacje:
- Find(S,x): zwraca klucz x ze słownika S, albo NULL jeśli tego klucza nie ma w słowniku;
- Insert(S,x): wstawia klucz x do słownika S;
- Delete(S,x): usuwa klucz x ze słownika S.
Binarne drzewo poszukiwań (skrót BST, z ang. Binary Search Tree) – dynamiczna struktura danych w postaci drzewa binarnego stosowana do szybkiego wyszukiwania. Drzewa BST służą do realizacji bardziej abstrakcyjnych struktur danych, np. zbiorów, czy słowników.
W każdym z węzłów drzewa BST przechowywany jest klucz. Wartość klucza jest zawsze nie mniejsza niż wartości wszystkich kluczy z lewego poddrzewa, a nie większa niż wartości wszystkich kluczy z prawego poddrzewa (relacja może być odwrócona, to kwestia umowy). Relacje niemniejszości i niewiększości można zamienić odpowiednio na relacje większości i mniejszości, ale ograniczamy się wówczas do przypadku unikalności kluczy (wykluczamy klucze, które mogą się powtarzać). Przechodząc drzewo metodą inorder, uzyskuje się ciąg wartości posortowanych niemalejąco (lub rosnąco w przypadku unikatowych kluczy).
Stos – liniowa struktura danych, w której dane dokładane są na wierzch stosu i z wierzchołka stosu są pobierane (bufor typu LIFO, Last In, First Out; ostatni na wejściu, pierwszy na wyjściu). Ideę stosu danych można zilustrować jako stos położonych jedna na drugiej książek – nowy egzemplarz kładzie się na wierzch stosu i z wierzchu stosu zdejmuje się kolejne egzemplarze.
Kolejka – liniowa struktura danych, w której nowe dane dopisywane są na końcu kolejki, a z początku kolejki pobierane są dane do dalszego przetwarzania (bufor typu FIFO, First In, First Out; pierwszy na wejściu, pierwszy na wyjściu).

4.    Podstawowe algorytmy grafowe.
Graf jest to struktura złożona z niepustego zbioru wierzchołków oraz zbioru krawędzi. Rozróżnia się grafy skierowane zwane też grafami zorientowanymi i grafy nieskierowane
Przeszukiwanie w głąb
Idea przeszukiwania w głąb polega na tym, że od pewnego wierzchołka idziemy ścieżką po wierzchołkach jeszcze nieodwiedzonych tak głęboko jak się da. Gdy nie możemy już przedłużyć ścieżki - wycofujemy się do poprzedniego wierzchołka i próbujemy z niego wyruszyć dalej po wierzchołkach nieodwiedzonych
Metoda polega na przypisaniu każdemu wierzchołkowi statusu nieodwiedzony, wybraniu pewnego wierzchołka u e V jako startowego, nadaniu mu statusu odwiedzony, a następnie na rekurencyjnym zastosowaniu tej metody do wszystkich następników wierzchołka u, czyli do tych wierzchołków v, dla których istnieje krawędź wiodąca od u do v. Jeżeli wszystkie wierzchołki grafu zostaną w ten sposób odwiedzone, przeszukiwanie zostaje zakończone, a jeżeli w grafie pozostaną wierzchołki nieodwiedzone, wybiera się którykolwiek z nich jako startowy i powtarza od niego przeszukiwanie. Postępowanie kontynuuje się dopóty, dopóki wszystkie wierzchołki grafu nie zostaną odwiedzone.

Przeszukiwanie w szerz
Podobnie jak w przypadku procedury DFS zakładamy, że początkowo wszystkie wierzchołki grafu są nieodwiedzone. Najpierw do wstępnie pustej kolejki Q wstawiamy, przekazany w parametrze przez wartość, wierzchołek u, od którego rozpoczyna się przeszukiwanie. Potem, dopóki kolejka Q nie jest pusta, pobieramy z niej wierzchołek u, a wstawiamy do niej wszystkie nieodwiedzone wierzchołki będące sąsiadami u. Umieszczanym w kolejce wierzchołkom nadajemy status odwiedzony.

Algorytm Dijkstry
Jednym z podstawowych problemów w teorii grafów jest znajdowanie połączeń pomiędzy dwoma wybranymi wierzchołkami. Ścieżką (ang. path) nazywamy uporządkowany zbiór wierzchołków, które musimy kolejno przejść, aby dotrzeć w grafie od jednego wybranego wierzchołka do innego wybranego wierzchołka. Ścieżek takich może być kilka (lub może nie istnieć żadna)
Tworzymy tablicę wierzchołków, nadajemy im wartość nieskończoności
Wierzchołkowi startowemu nadajemy wartość 0

Wybieramy wierzchołek z najmniejszą wartością, oznaczamy go, a następnie odczytujemy koszt jaki poniesiemy od niego do każdego z jego bezpośrednich sąsiadów, których do tej pory nie odwiedziliśmy.
Wpisujemy tę wartość + koszt do wierzchołka, z którego aktualnie zaczęliśmy, do tablicy pod pozycję oznaczającą wierzchołek do którego prowadzi ścieżka, o ile nowa wartość jest mniejsza od wartości znajdującej się w tej pozycji. Powtarzamy operację dopóki każdy z wierzchołków nie zostanie przeszukany.
(warto pomyśleć o jakimś przykładowym grafie i go rozwiązać)
5.    Złożoność obliczeniowa.
Głównym jej celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów. Ilość zasobów niezbędnych do wykonania algorytmu można rozumieć jako jego złożoność. W zależności od rozważanego zasobu mówimy o złożoności czasowej czy też pamięciowej. Oczywiście w większości wypadków ilość potrzebnych zasobów będzie się różnić w zależności od danych wejściowych z zakresu danego zagadnienia.
Przyjętą miarą złożoności czasowej jest liczba operacji podstawowych w zależności od rozmiaru wejścia. Pomiar rzeczywistego czasu zegarowego jest mało użyteczny ze względu na silną zależność od sposobu realizacji algorytmu, użytego kompilatora oraz maszyny na której algorytm wykonujemy. Dlatego w charakterze czasu wykonania rozpatruje się zwykle liczbę operacji podstawowych (dominujących). Operacjami podstawowymi mogą być na przykład: podstawienie, porównanie lub prosta operacja arytmetyczna.
Klasa złożoności to klasa zagadnień obliczeniowych o podobnej złożoności obliczeniowej - innymi słowy problemy do których rozwiązania potrzebna jest podobna ilość zasobów łączymy w klasy. Przykładowo mówimy o problemach o liniowej złożoności pamięciowej, jeśli ilość potrzebnej pamięci rośnie liniowo względem rozmiaru danych; czy też o problemach o kwadratowej złożoności czasowej, jeśli liczba operacji podstawowych rośnie z kwadratem rozmiaru danych. Podobne określenia stosujemy do algorytmów.
6.    Problemy NP.-zupełne i nierozstrzygalne
Problem NP (niedeterministycznie wielomianowy, ang. nondeterministic polynomial) to problem decyzyjny, dla którego rozwiązanie można zweryfikować w czasie wielomianowym. Równoważna definicja mówi, że problem jest w klasie NP, jeśli może być rozwiązany w wielomianowym czasie na niedeterministycznej maszynie Turinga.
Problem NP-zupełny (NPC) czyli problem zupełny w klasie NP ze względu na redukcje wielomianowe, to problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym. Czasami zamiast redukcji w czasie wielomianowym używa się redukcji w pamięci logarytmicznej.
Problemy NP-zupełne można traktować jako najtrudniejsze problemy klasy NP (z punktu widzenia wielomianowej rozwiązywalności). Przykładem problemu NP-zupełnego może być Problem komiwojażera
Istnieje też klasa problemów nierozstrzygalnych. To zaskakujące, ale są problemy, których nie da się rozwiązać. Nie da się w tym sensie, że niezależnie od mocy obliczeniowej komputera i czasu jaki mu damy (nawet setki lat), nie poda poprawnego wyniku (tzn. może i poda, bo można napisać program losujący odpowiedź i kiedyś pewnie trafi (np. gdy odpowiedzi należą do zbioru {tak, nie}, ale my nie będziemy wiedzieli czy to dobre rozwiązanie). Takim problemem jest np. sprawdzenie czy program wypisuje "hello world". Mamy dany, na wejściu, kod źródłowy i chcemy stwierdzić czy po wykonaniu na ekranie pojawi się "hello world". O ile w prostych przypadkach (sprawdzenie czy jest instrukcja print, a potem krótki tekst) to jest łatwe, o tyle w innych może być gorzej.

Ogólny program sprawdzający powyższe nie istnieje. Można tego dowieść matematycznie. Jeżeli jednak ustalimy program wejściowy (źródło), to da się napisać program, który da dobrą odpowiedź. Czyli nie musimy rozwiązywać problemu, w ogólności, ale w konkretnym przypadku. Łatwo udowodnić, że da się napisać taki program. Piszemy dwa. Jeden wypisuje "tak", drugi "nie". Któryś wynik na pewno jest poprawny.

Klasa problemów nierozstrzygalnych jest ciekawa, ale...

Klasa NP (ang. nondeterministic polynomial - niedeterministycznie wielomianowe) jest jeszcze ciekawsza. O ile w przypadku powyższych klas wiemy wszystko (P - problemy daje się rozwiązać, Nierozstrzygalne - problemów nie da się rozwiązać), o tyle o NP nie wiadomo jeszcze nic.
Problem Stopu - jako problem nierozstrzygalny
Rozważmy algorytm:
dopóki x <> 1, dopóty wykonuj:
Jeśli X jest parzyste, to  x := x/2
W przeciwnym przypadku (X nieparzyste) wykonaj x := 3*x+1
Zatrzymaj się.
Algorytm dzieli x na pół, jeśli jest ono parzyste, ale zwiększa je więcej niż trzykrotnie, jeśli jest nieparzyste. Np. dla x=7 mamy: 7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1, tak więc algorytm zatrzymuje się.
Wykonując algorytm dla dowolnej liczby naturalnej stwierdzimy, że zawsze się zatrzymuje, ale nikt nie potrafi udowodnić, że zatrzymuje się on dla wszystkich liczb naturalnych (chociaż większość uważa, że tak jest). Widać więc jak trudne jest analizowanie własności kończenia się nawet bardzo prostych algorytmów.

Brak grafów w pytaniu 3