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ść
- 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
- K. Diks, A. Malinowski, W. Rytter, T. Waleń Algorytmy i struktury danych/Wstęp: poprawność i złożoność algorytmu
Sortowanie tablic
- visualgo.net/sorting – wizualizacje
Algorytmy proste
- Sortowanie przez wybieranie i Sortowanie przez wstawianie na Khan Academy: Algorytmy
- 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)
- Taniec ludowy, wideo, sortowanie: przez scalanie, szybkie (quick sort)
Tablice z haszowaniem
- 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
- J. Koszelew Operacje słownikowe realizowane w tablicy z haszowaniem
- 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
Tekstowe – wyszukiwanie wzorca
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
Grafowe
- visualgo.net/graphds – reprezentacja grafów w pamięci, wizualizacja
Szukanie najkrótszych ścieżek
- visualgo.net/sssp – wizualizacje
Szukanie minimalnego drzewo spinającego
- visualgo.net/mst – wizualizacje algorytmów Prima i Kruskala
Algorytm Prima
Algorytm Kruskala
- visualgo.net/ufds – wizualizacja metody find-union
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
- Brad Miller i David Ranum Problem Solving with Algorithms and Data Structures using Python