Spis treści
Wstęp
- Wprowadzenie do algorytmów na Khan Academy: Algorytmy
- K. Diks Po co komu te algorytmy? oraz Lepsze algorytmy = szybsza aplikacja
- Wizualizacja algorytmów: visualgo.net, Data Structure Visualizations, algo-visualizer, illustrated-algorithms, algomation, Algorithm Visualizer for Android
Złożoność i poprawność
- P. Beling Poprawność i złożoność obliczeniowa algorytmów – prezentacja
- M. Sydow Algorytmy i Struktury Danych, Poprawność Algorytmów i Złożoność Obliczeniowa Algorytmów – prezentacje
- K. Diks, A. Malinowski, W. Rytter, T. Waleń Algorytmy i struktury danych/Wstęp: poprawność i złożoność algorytmu
- G. Jagiella Skrypt do wykładu Programowanie 2 (Python) wykłady: 1: złożoność obliczeniowa i 2 (cz. 1): złożoność obliczeniowa, c.d.
- Elżbieta Richter-Wąs Teoretyczne Podstawy Informatyki - wykład 3
- Asymptotyczne tempo wzrostu na Khan Academy: Algorytmy
- J. Widuch Algorytmy i Struktury Danych 2, Część II Złożoność obliczeniowa algorytmów, od slajdu 12
- M. Pietraszek Samouczek Programisty / Podstawy złożoności obliczeniowej
Metody konstrukcji algorytmów
Algorytm zachłanne
Przykłady: algorytmy Dijkstry, Prima i Kruskala.
Programowanie dynamiczne
- P. Beling Algorytmy wyznaczania wartości symbolu Newtona – prezentacja
Programowanie dynamiczne realizują też, m.in.: algorytm wyznaczający najdłuższy wspólny podciąg, oraz Floyda-Warshalla.
Sortowanie tablic
- visualgo.net/sorting – wizualizacje
- http://www.algostructure.com/sorting/index.php – złożoności i wizualizacje
Algorytmy proste
- Sortowanie przez wybieranie i Sortowanie przez wstawianie na Khan Academy: Algorytmy
- M. Sydow Algorytmy i Struktury Danych / Sortowanie 1 – prezentacja
- Taniec ludowy, wideo, sortowanie: bąbelkowe, przez wstawianie, przez wybieranie (najmniejszego elementu)
Algorytmy efektywne
- Sortowanie przez scalanie i Szybkie sortowanie (quick sort) na Khan Academy: Algorytmy
- Wizualizacja: sortowanie szybkie (quick sort)
- M. Sydow Algorytmy i Struktury Danych / Sortowanie 2 – prezentacja
- Taniec ludowy, wideo, sortowanie: przez scalanie, szybkie (quick sort)
Tablice z haszowaniem
- P. Beling Słowniki i ich realizacja za pomocą haszowania – prezentacja
- P. Beling Doskonałe funkcje haszujące – prezentacja
- Rozdział Tablice z haszowaniem w części Struktury danych książki Wprowadzenie do algorytmów Thomasa H. Cormena, Charlesa E. Leisersona, Rolanda L. Rivesta, Clifforda Steina
- M. Sydow Algorytmy i Struktury Danych / Słowniki – prezentacja, omawia także drzewa poszukiwań binarnych, w tym AVL
- W. Horzelski Wykład 4 - Tablice z haszowaniem
- Tablica mieszająca w Wikipedii
- K. Diks, A. Malinowski, W. Rytter, T. Waleń Algorytmy i struktury danych/Wyszukiwanie
- visualgo.net/hashtable – wizualizacje
- A. Lundblad, S. Nilsson Programming.Guide: Hash Tables - ładne i kompletne opracowanie w języku angielskim, zawiera m.in. opis Robin Hood Hashing, heurystyki zwiększającej efektywność haszowania z adresowaniem otwartym, liniowym
- R. Shankar The Swiss Army Knife of Hashmaps – (dla zainteresowanych) omawia przykładowe, efektywne, współczesne implementacje tablic z haszowaniem (po angielsku)
Kolejki priorytetowe, kopiec binarny
- J. Wałaszek Kopiec binarny
- M. Karpiński Kopiec (binarny)
- visualgo.net, cs.usfca.edu – wizualizacje operacji na kopcu binarnym
- M. Sydow Algorytmy i Struktury Danych / Kolejka Priorytetowa – prezentacja
Algorytmy Łańcuchowe
Wyszukiwanie wzorca w tekście
Algorytm Sunday’a
- P. Beling Algorytmy wyszukiwania wzorca - naiwny i Sunday’a – prezentacja
- Prezentacje dotyczące algorytmu Sunday’a przygotowane przez studentów (zawierają przykłady działania): 1, 2, 3
- C. Charras, T. Lecroq Quick Search algorithm – zawiera aplet Javy
- H. W. Lang Sunday algorithm
- D. M. Sunday A Very Fast Substring Search Algorithm, Communications of the ACM, 33, 8, 132-142 (1990)
Algorytm Knuth’a-Morris’a-Pratt’a (KMP)
- J. Radoszewski Wykład 1. Liniowe algorytmy tekstowe oraz mirror wideo z wykładu na youtube (uwaga: tak naprawdę wykład dotyczy algorytmu Morris’a-Pratt’a (MP), a nie KMP)
- R. Olechowski Algorytm Knuth–Morris–Pratt
- J. Wałaszek Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
- Tushar Roy Coding Made Simple Knuth–Morris–Pratt (KMP) Pattern Matching (Substring search) and Part 2
Algorytm Boyer’a-Moore’a
- J. Wałaszek Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore’a
- Atul Kumar Boyer Moore Algorithm Bad Character Heuristic, Good Suffix heuristic
- Kj Huang Boyer-Moore Algorithm Good Suffix Rule – wizualizacja (wideo) działania zasady dobrego sufiksu
- C. Charras, T. Lecroq Turbo-BM algorithm – wersja algorytmu zapewniająca liniowy (pesymistyczny) czas działania; zawiera też aplet Javy
Najdłuższy wspólny podciąg
(z wykorzystaniem programowania dynamicznego)
- Najdłuższy wspólny podciąg w Wikipedii
- Marcin Oczeretko Najdłuższy wspólny podciąg
- Dynamic Programming (Longest Common Subsequence) – wizualizacja
Grafowe
- M. Sydow Algorytmy i Struktury Danych / Wprowadzenie do grafów – prezentacja zawierające podstawowe pojęcia oraz sposoby reprezentacji grafów
- A. Mróz Algorytmy i struktury danych / Teoria grafów i algorytmy grafowe
- A. Mróz Elementy teorii grafów, sposoby reprezentacji grafów w komputerze slajdy i wersja do druku
- visualgo.net/graphds – reprezentacja grafów w pamięci, wizualizacja
Szukanie najkrótszych ścieżek
- visualgo.net/sssp – wizualizacje
Przeszukiwanie grafu wszerz (BFS) (dla grafów bez wag)
- A. Mróz Podstawowe algorytmy grafowe i ich zastosowania (DFS, BFS) slajdy i wersja do druku
- M. Sydow Algorytmy i Struktury Danych / Algorytmy przeglądania grafów i drzew – prezentacja
- G. Jagiella Skrypt do wykładu Programowanie 2 (Python): Wykład 7 - grafy i algorytm BFS
Algorytm Dijkstry (dla grafów z wagami, jedno źródło)
- A. Mróz Najkrótsze drogi w grafach z wagami slajdy i wersja do druku – algorytm Dijkstry i Bellmana-Forda
- Złożoność algorytmu Dijsktry (wideo) – przykład, analiza złożoności, omówienie kopca binarnego
- M. Sydow Algorytmy i Struktury Danych / Znajdowanie najkrótszych ścieżek w grafach – prezentacja o algorytmach Dijkstry i Belmana-Forda
Algorytm Floyda-Warshalla (pomiędzy każdą parą wierzchołków w grafie ważonym)
- K. Diks, W. Rytter, P. Sankowski Zaawansowane algorytmy i struktury danych/Zaawansowane algorytmy grafowe II: Najkrótsze ścieżki
- dr inż. Zbigniew Kokosiński Badania Operacyjne, wykład 7: Najkrótsze ścieżki w grafie 2
- J. Wałaszek Algorytm Floyda-Warshalla
- Algorytm Floyda-Warshalla w Wikipedii
- wizualizacje/przykłady: 1, 2
Szukanie minimalnego drzewo rozpinającego
- dr Andrzej Mróz Minimalne drzewo rozpinające slajdy i wersja do druku – algorytm Kruskala, Prima, zbiory rozłączne
- visualgo.net/mst – wizualizacje algorytmów Prima i Kruskala
- M. Sydow Algorytmy i Struktury Danych / Minimalne drzewa rozpinające – prezentacja o algorytmach Prima i Kruskala
Algorytm Prima
- Opis algorytmu w wikipedii
- Algorytm Prima (wideo) – przykład działania i dowód poprawności
- Przykład działania (wideo)
Algorytm Kruskala i struktury danych dla zbiorów rozłącznych (find-union)
- Algorytm Kruskala (wideo) – przykład działania i dowód poprawności
- K. Diks, A. Malinowski, W. Rytter, T. Waleń Algorytmy i struktury danych/Find-Union – zawiera opis polecanej implementacji find-union, t.j. drzewiastej z łączeniem według wysokości i kompresją ścieżki
- visualgo.net/ufds – wizualizacja metody find-union
- find_union_tree.py – czytelna implementacja find-union w Pythonie
Generowanie labiryntów z wykorzystaniem teorii grafów
- Maze generation algorithm w Wikipedii
- Jamis Buck Maze Generation: Algorithm Recap (zawiera wizualizacje)
- Maze generation algorithms na algostructure.com (zawiera wizualizacje)
- Fauzan Hilmi Ramadhian Implementation of Prim’s and Kruskal’s Algorithms’ on Maze Generation
Polecane książki
- Thomas H. Cormen, Charles E. Leiserson, Roland L. Rivest, Clifford Stein Wprowadzenie do algorytmów
Algorymy z przykładami w wybranych językach
Python
- B. Miller i D. Ranum Problem Solving with Algorithms and Data Structures using Python
- G. Jagiella Skrypt do wykładu Programowanie 2 (Python)