Algorytmy i struktury danych

Ostatnia aktualizacja Sep 4, 2022

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-Morrisa-Pratta (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 Boyera-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

Algorytm Karpa-Rabina

J. Wałaszek Wyszukiwanie wzorca algorytmem Karpa-Rabina

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łady działania (wideo): 1, 2

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, tj. 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