Algorytmy i struktury danych

Spis treści

Wstęp

Złożoność i poprawność

Metody konstrukcji algorytmów

Algorytm zachłanne

Przykłady: algorytmy Dijkstry, Prima i Kruskala.

Programowanie dynamiczne

Programowanie dynamiczne realizują też, m.in.: algorytm wyznaczający najdłuższy wspólny podciąg, oraz Floyda-Warshalla.

Sortowanie tablic

Algorytmy proste

Algorytmy efektywne

Tablice z haszowaniem

Kolejki priorytetowe, kopiec binarny

Algorytmy Łańcuchowe

Wyszukiwanie wzorca w tekście

Algorytm Sunday’a

Algorytm Knuth’a-Morris’a-Pratt’a (KMP)

Algorytm Boyer’a-Moore’a

Najdłuższy wspólny podciąg

(z wykorzystaniem programowania dynamicznego)

Grafowe

Szukanie najkrótszych ścieżek

Przeszukiwanie grafu wszerz (BFS) (dla grafów bez wag)

Algorytm Dijkstry (dla grafów z wagami, jedno źródło)

Algorytm Floyda-Warshalla (pomiędzy każdą parą wierzchołków w grafie ważonym)

Szukanie minimalnego drzewo rozpinającego

Algorytm Prima

Algorytm Kruskala i struktury danych dla zbiorów rozłącznych (find-union)

Generowanie labiryntów z wykorzystaniem teorii grafów

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

Projekty, prace domowe

Piotr Beling
Piotr Beling
adiunkt

Moje główne zaintersowania naukowe obejmują sztuczną inteligencję i teorię gier.