Podstawy algorytmiki Flashcards
(12 cards)
Definicja algorytmu, cechy poprawnego algorytmu, złożoności algorytmów i sposoby
jego zapisu.
> Algorytm to definiowane krok po kroku rozwiązanie problemu lub zadania. Algorytm musi być precyzyjny i zawsze dawać taki sam rezultat po wykonaniu tych samych operacji.Cechy poprawnego algorytmu:
- Poprawność: algorytm musi być skonstruowany tak, aby zawsze dawał prawidłowy wynik.
- Kompozycja: algorytm powinien być składany z elementarnych operacji, które są łatwe do zrozumienia i wykonania.
- Efektywność: algorytm powinien być wykonywany w rozsądnym czasie.
- Pseudokod: to zapis algorytmu w formie zbliżonej do języka naturalnego, ale zawierającego również elementy składniowe z języka programowania. Pseudokod jest łatwiejszy do zrozumienia dla osób nie będących programistami.
- Diagram blokowy: to graficzny sposób zapisywania algorytmu, w którym poszczególne elementy są reprezentowane przez różne kształty i są ze sobą połączone liniami.
- Język programowania: algorytm może być również zapisany w języku programowania, co pozwala na jego automatyczne wykonanie przez komputer.
Podstawowe techniki algorytmiczne: dziel i zwyciężaj, metoda zachłanna,
programowanie dynamiczne, rekurencja.
Technika dziel i zwyciężaj (ang. divide and conquer) polega na podzieleniu problemu na mniejsze podproblemy, rozwiązaniu każdego z nich osobno i połączeniu ich w celu rozwiązania problemu głównego. Technika ta jest często stosowana w algorytmach sortujących, takich jak sortowanie przez scalanie (merge sort).
Metoda zachłanna (ang. greedy algorithm) polega na wybieraniu w każdym kroku rozwiązania problemu tej opcji, która wydaje się być najlepszą w danym momencie, bez względu na to, jakie będą jej dalsze konsekwencje. Metoda ta jest często stosowana w problemach optymalizacyjnych, takich jak problem komiwojażera (ang. traveling salesman problem).
Programowanie dynamiczne (ang. dynamic programming) polega na zapamiętywaniu wyników wcześniej obliczonych podproblemów i wykorzystywaniu ich przy obliczaniu rozwiązania problemu głównego. Dzięki temu unika się powtarzania obliczeń i algorytm jest bardziej efektywny.
Rekurencja to technika, w której algorytm wywołuje sam siebie w celu rozwiązania problemu. Algorytm rekurencyjny musi mieć warunek zakończenia, tzw. warunek brzegowy, który pozwala na zakończenie rekurencji i zwrócenie wyniku. Rekurencja jest często stosowana w problemach, w których rozwiązanie problemu głównego może być podzielone na mniejsze podproblemy, które są do siebie podobne.
Algorytmy sortowania elementów w tablicy: BubleSort, InsertSort, SelectSort,
QuickSort, MergeSort.
> Sortowanie bąbelkowe (ang. bubble sort) to algorytm, w którym porównuje się elementy sąsiadujące ze sobą i zamienia miejscami te, które są w nieodpowiedniej kolejności. Proces ten jest powtarzany, aż do momentu, gdy cała tablica jest posortowana. Sortowanie bąbelkowe jest prostym algorytmem, ale jego złożoność obliczeniowa jest O(n^2), co sprawia, że nie jest ono zbyt wydajne w przypadku dużych tablic.Sortowanie przez wstawianie (ang. insertion sort) polega na przesuwaniu elementów w tablicy tak, aby zawsze po lewej stronie znajdowały się posortowane elementy. Elementy są wstawiane na odpowiednie miejsca poprzez porównywanie ich z innymi elementami i przesuwanie ich w lewo, jeśli są mniejsze. Złożoność obliczeniowa tego algorytmu to O(n^2).Sortowanie przez wybieranie (ang. selection sort) polega na wyszukiwaniu najmniejszego elementu w tablicy i przenoszeniu go na jej początek. Proces ten jest powtarzany, aż do momentu, gdy cała tablica jest posortowana. Złożoność obliczeniowa tego algorytmu również wynosi O(n^2).Sortowanie szybkie (ang. quick sort) to algorytm oparty na idei dziel i zwyciężaj. Podziel tablicę na dwie części, tak aby w lewej znajdowały się elementy mniejsze od elementu pivota, a w prawej elementy większe od niego. Następnie zastosuj tę samą procedurę do obu podtablic. Sortowanie szybkie jest zazwyczaj bardzo wydajne, ale w najgorszym wypadku jego złożoność obliczeniowa wynosi O(n^2).Sortowanie przez scalanie (ang. merge sort) to algorytm oparty na technice dziel i zwyciężaj. Podziel tablicę na dwie równe części i posortuj każdą z nich osobno, a następnie połącz je w jedną posortowaną tablicę. Proces ten jest powtarzany, aż do momentu, gdy pozostaje jedna posortowana tablica. Sortowanie przez scalanie jest bardzo wydajne, a jego złożoność obliczeniowa wynosi O(n*log(n)). Jest to jeden z najszybszych algorytmów sortujących.
Algorytm flagi polskiej i flagi francuskiej. Selekcja - algorytm Hoare’a, „magicznych
piątek”.
> Algorytm flagi Polskiej może oznaczać sposób rozwiązania problemu, który polega na przeszukaniu posortowanej tablicy przy użyciu trzech wskaźników, podczas gdy algorytm flagi francuskiej może oznaczać metodę rozwiązania problemu, która polega na wykorzystaniu rekurencji.Algorytm selekcji Hoare’a, zwany również algorytmem QUICKSORT, jest popularnym algorytmem sortowania, który działa na zasadzie dziel i zwyciężaj. Algorytm bierze jeden element z tablicy (nazywany pivotem) i rozdziela pozostałe elementy na dwie podgrupy: te, które są mniejsze od pivotu i te, które są większe od pivotu. Następnie algorytm rekurencyjnie sortuje obie podgrupy. Dzięki temu pivot znajduje się na swoim miejscu w posortowanej tablicy, a proces sortowania jest przyspieszany dzięki zmniejszaniu rozmiaru poszczególnych podgrup.Natomiast “magiczne piątki” to nie jest algorytm, to raczej koncepcja dotycząca pewnego rodzaju problemów, gdzie cecha jest, że odpowiednie rozwiązanie jest dostępne po pięciu przykładach, czy pięciu testach.
Algorytmy wyszukiwania informacji w tablicach.
> Algorytmy wyszukiwania informacji w tablicach to grupa algorytmów, które pozwalają na znalezienie określonego elementu w tablicy. Najczęściej używane algorytmy wyszukiwania to:
- Wyszukiwanie liniowe (linear search): Algorytm przeszukuje każdy element tablicy od pierwszego do ostatniego, aż znajdzie element o poszukiwanej wartości. Jest to najprostszy algorytm wyszukiwania, ale jednocześnie najwolniejszy, zwłaszcza dla dużych tablic.
- Wyszukiwanie binarne (binary search): Algorytm działa tylko na posortowanych tablicach i polega na dzieleniu tablicy na pół, w celu określenia, która połowa tablicy zawiera szukany element. Następnie proces jest powtarzany dla wybranej połowy, aż zostanie znaleziony szukany element. Jest to algorytm szybszy niż wyszukiwanie liniowe, ale wymaga tablicy posortowanej.
- Wyszukiwanie interpolacyjne (interpolation search): Algorytm podobny do wyszukiwania binarnego, ale zamiast dzielenia tablicy na równe części, używa interpolacji, aby określić, w której części tablicy znajduje się poszukiwany element. Jest to algorytm bardziej skomplikowany niż wyszukiwanie binarne, ale może być szybszy dla odpowiednio skonstruowanych tablic.
Algorytmy wyszukiwania wzorca w tekście, zastosowanie funkcji haszujących.
Algorytmy wyszukiwania wzorca w tekście służą do wyszukiwania wystąpień danego wzorca (np. słowa, ciągu znaków) w tekście. Jest to ważne zagadnienie w informatyce, ponieważ jest używane w wielu różnych dziedzinach, takich jak przeszukiwanie i indeksowanie stron internetowych, systemy komunikacyjne, bezpieczeństwo komputerowe itp.
Funkcje haszujące są często stosowane w algorytmach wyszukiwania wzorca w tekście, ponieważ pozwalają one na szybkie porównanie dwóch ciągów znaków. Funkcja haszująca jest to funkcja, która przetwarza ciąg znaków na skrócony ciąg cyfr, zwany skrótem (czasem hashem), który jest unikalny dla danego ciągu znaków. Dlatego, jeśli dwa ciągi znaków mają taki sam skrót, to jest bardzo prawdopodobne, że są one takie same.
Dynamiczne struktury danych: stos, kolejka, lista.
> Dynamiczne struktury danych to struktury danych, które pozwalają na zmianę rozmiaru w trakcie działania programu. Poniżej znajdują się krótkie opisy trzech popularnych dynamicznych struktur danych: stosu, kolejki i listy:
- Stos (ang. stack) to struktura danych, która działa na zasadzie “ostatni wchodzi, pierwszy wychodzi” (LIFO - Last In, First Out). To znaczy, że element, który został dodany jako ostatni, jest pierwszy do usunięcia. Stos jest często wykorzystywany w algorytmach i językach programowania, np. do implementowania rekurencji, tworzenia historii nawigacji w przeglądarce czy obsługi przełączników w linii poleceń.
- Kolejka (ang. queue) to struktura danych, która działa na zasadzie “pierwszy wchodzi, pierwszy wychodzi” (FIFO - First In, First Out). To oznacza, że element, który został dodany jako pierwszy, jest pierwszy do usunięcia. Kolejki są często używane do przetwarzania zadań w kolejności ich wystąpienia, takie jak kolejkowanie zadań w systemie operacyjnym czy wirtualnej maszynie.
- Lista (ang. list) to struktura danych, która pozwala na przechowywanie i dostęp do elementów w dowolnej kolejności. Listy pozwalają na dodawanie, usuwanie i wyszukiwanie elementów w dowolnym miejscu na liście. W zależności od implementacji, listy mogą być pojedynczo lub podwójnie wiązane, co oznacza, że każdy element zawiera informację o poprzednim i następnym elemencie. Listy są często używane do implementacji algorytmów, takich jak sortowanie i graficzne interfejsy użytkownika.
Definicja drzewa i podstawowe na nim operacje: BST, AVL, B-drzewa.
> Drzewo (ang. tree) to struktura danych, która składa się z węzłów (ang. nodes) połączonych liniami. Każdy węzeł może mieć co najwyżej jednego rodzica, ale może mieć wiele dzieci. Węzeł, który nie ma rodzica, jest korzeniem drzewa.BST (ang. Binary Search Tree) to drzewo binarne, gdzie wartość każdego węzła jest większa niż wartość każdego węzła z lewego poddrzewa i mniejsza niż wartość każdego węzła z prawego poddrzewa.AVL (ang. Adelson-Velsky Landis Tree) to drzewo binarne, które jest BST i jego wysokość jest zawsze największa o 1 w porównaniu do innych drzew binarnych o tej samej liczbie węzłów. Jest to drzewo balansowaneB-drzewa (ang. B-Trees) to drzewa, które mają więcej niż 2 dzieci, co pozwala na efektywne przechowywanie dużych zbiorów danych na dysku. B-drzewa są często używane w bazach danych i systemach plików, aby umożliwić szybkie wyszukiwanie i wstawianie danych.Podstawowe operacje na tych drzewach:
- Wstawianie elementu do drzewa
- Usuwanie elementu z drzewa
- Wyszukiwanie elementu w drzewie
- Przejście po drzewie (in-order, pre-order, post-order)
- Znalezienie największego/najmniejszego elementu w drzewie
- Znalezienie następnika/poprzednika dla danego elementu
Definicja kopca, sortowanie przez kopcowanie.
> Kopiec (ang. heap) to specyficzny rodzaj drzewa binarnego, którego struktura zapewnia pewne użyteczne właściwości. Istnieją dwa rodzaje kopców: kopiec minimalny i kopiec maksymalny.Kopiec minimalny (ang. min heap) jest to taki kopiec, gdzie wartość każdego węzła jest mniejsza niż wartość każdego z jego dzieci. W przypadku kopca minimalnego korzeń jest najmniejszym elementem w całym drzewie.Kopiec maksymalny (ang. max heap) jest to taki kopiec, gdzie wartość każdego węzła jest większa niż wartość każdego z jego dzieci. W przypadku kopca maksymalnego korzeń jest największym elementem w całym drzewie.Sortowanie przez kopcowanie (ang. heap sort) jest to algorytm sortowania, który korzysta z kopca. Algorytm działa w następujący sposób:
- Tworzymy kopiec (minimalny lub maksymalny) z danych wejściowych.
- Usuwamy korzeń (największy/najmniejszy element) z kopca i przenosimy go na końcu tablicy.
- Przywracamy właściwości kopca poprzez przesuwanie węzła w odpowiednie miejsce.
- Powtarzamy kroki 2 i 3, aż do otrzymania posortowanej tablicy.
Grafy, algorytmy grafowe i ich zastosowania.
> Grafy to matematyczne modele reprezentujące związki między obiektami. Są one składają się z wierzchołków (ang. vertices) oraz krawędzi (ang. edges) między nimi. Krawędzie mogą być skierowane (ang. directed) lub nieskierowane (ang. undirected), a każdy wierzchołek może mieć dowolną liczbę incydentnych krawędzi.Algorytmy grafowe to algorytmy, które przetwarzają lub wykonują obliczenia na grafach. Niektóre popularne algorytmy grafowe to:
- Przeszukiwanie w głąb (ang. Depth-First Search, DFS) - algorytm przeszukujący graf od korzenia, najpierw przeglądając wszystkie dzieci danego węzła, a następnie przechodząc do kolejnego poziomu.
- Przeszukiwanie wszerz (ang. Breadth-First Search, BFS) - algorytm przeszukujący graf od korzenia, najpierw przeglądając wszystkie węzły na danym poziomie, a następnie przechodząc do następnego poziomu.
- Dijkstra - algorytm znajdujący najkrótszą ścieżkę między dwoma węzłami w grafie ważonym.
- Prima - algorytm znajdujący minimalne drzewo rozpinające w grafie ważonym.
- Kruskal - algorytm znajdujący minimalne drzewo rozpinające w grafie nie ważonym.
- Planowanie tras w systemach nawigacji
- Znajdowanie najkrótszej ścieżki między miastami w mapie
- Projektowanie systemów logistycznych i rozwiązywanie problemów transportowych
- Analiza sieci społecznościowych i marketingu sieciowego
- Wyszukiwanie podobieństw w dany
Otoczka wypukła – algorytm Grahama.
> Otoczka wypukła (ang. convex hull) to zbiór punktów w przestrzeni, które zawierają wszystkie punkty leżące wewnątrz lub na granicy zdefiniowanej figury geometrycznej (np. wypukłego wielokąta). Otoczka wypukła jest często wykorzystywana w różnych dziedzinach, takich jak robotyka, grafika komputerowa, geometria komputerowa i analiza danych.Algorytm Grahama jest jednym z algorytmów do obliczania otoczki wypukłej. Algorytm działa w następujący sposób:
- Znajdujemy punkt o najniższej wysokości (lub o najniższym x-ie, jeśli wysokości są takie same) i ustalamy go jako punkt startowy.
- Tworzymy listę wszystkich punktów, wykluczając punkt startowy.
- Posortowanie punktów według ich kąta z punktem startowym.
- Dodajemy pierwszy punkt z posortowanej listy do stosu.
- Dla każdego pozostałego punktu na liście:
a) Dopóki ilość punktów na stosie jest większa niż 2 i kąt między ostatnim punktem na stosie, przedostatnim punktem na stosie i bieżącym punktem jest nie wypukły, usuwaj punkty z początku stosu.
b) Dodajemy bieżący punkt do stosu. - Otoczka wypukła jest teraz przechowywana na stosie, od końca stosu do pierwszego punktu.
Problemy klasy NP i NP-zupełne
roblemy klasy NP (ang. Non-deterministic Polynomial time) to takie problemy, dla których istnieje algorytm rozwiązujący, który działa w czasie polynomialnym, pod warunkiem dostępności oracle’a (tj. specjalnego algorytmu), który jest w stanie szybko rozwiązać podproblemy związane z danym problemem.
Problemy klasy NP-zupełne (ang. NP-complete) to problemy klasy NP, które są połączone z każdym innym problemem z klasy NP za pomocą redukcji polynomialnej. To znaczy, że dla każdego problemu z klasy NP istnieje algorytm pozwalający na przekształcenie go w problem NP-zupełny, w taki sposób, że rozwiązanie problemu NP-zupełnego automatycznie rozwiązuje problem z klasy NP.
Problem NP-zupełny przykładem jest problem koloruowania grafów, tzn. jakiego najmniejszego kolorowania wierzchołków potrzebujemy by żadne dwie sąsiadujące wierzchołki nie miały takiego samego koloru
