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ść

• K. Diks, A. Malinowski, W. Rytter, T. Waleń Algorytmy i struktury danych/Wstęp: poprawność i złożoność algorytmu
• 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

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

• P. Beling Słowniki i ich realizacja za pomocą haszowania – 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
• 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
• R. Shankar The Swiss Army Knife of Hashmaps – (dla zainteresowanych) omawia przykładowe, efektywne, współczesne implementacje tablic z haszowaniem

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

• dr Andrzej Mróz Algorytmy i struktury danych / Teoria grafów i algorytmy grafowe
• dr Andrzej 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 w wszerz (BFS) (dla grafów bez wag)

• dr Andrzej Mróz Podstawowe algorytmy grafowe i ich zastosowania (DFS, BFS) slajdy i wersja do druku

Algorytm Dijkstry (dla grafów z wagami)

• dr Andrzej Mróz Najkrótsze drogi w grafach z wagami slajdy i wersja do druku – algorytm Dijkstry i Bellmana-Forda
• https://www.youtube.com/watch?v=XzPzaPQJsiY – przykład, analiza złożoności, omówienie kopca binarnego

Szukanie minimalnego drzewo spinają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

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

• Algorytm Kruskala (wideo) – przykład działania i dowód poprawności
• visualgo.net/ufds – wizualizacja metody find-union
• find_union_tree.py – czytelna implementacja find-union w Pythonie

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