nerd911 / aisd-skrypt

Skrypt do przedmiotu "Algorytmy i Struktury Danych"

aisd-skrypt

Skrypt do przedmiotu "Algorytmy i Struktury Danych"

Konwencja:

W tekście:

• zmienne matematyczne i liczby piszemy w $dolarach$
• jeśli odwołujemy się do zmiennych w algorytmie to używamy \texttt{tekstu o stałej szerokości}

Po każdym zdaniu stawiamy enter.

Nie numerujemy wzorów jeśli potem z nich nie korzystamy.

Nie zaczynamy zdania od wzoru.

Nie zaczynamy rozdziału od programu (patrz rozdział wzorcowy).

Podział (grupa 4 wspaniałych):

• Lazy Select (KPI)
• Drzewa Splay (Tomek)
• Drzewce (Przemek)
• Drzewa dwumianowe leniwe (Marcin)

Zrobione:

• Algorytm Strassena (KPI)
• Sortowanie Bitoniczne (KPI)
• Fibonacci algorytm macierzowy (Rafał Florczak)
• Master Theorem (Marcin Bartkowiak + KPI)
• element uniqness (KPI)
• problem plecakowy (Marcin Bartkowiak + KPI)

W toku:

• counting sort (Dominika)
• pokrycie wierzchołkowe (Krzysztof Starzyk)
• Algorytm rosyjskich wieśniaków (Przemek Joniak)
• Pokrycie zbioru (Michał Wierzbicki)
• Algorytm Dijkstry (Mikołaj Słupiński)
• Cut Property / Circle Property (Mateusz Ciesiółka)
• Algorytm dwóch najbliższych punktów (Tomasz Nanowski)
• Sieć Banesa-Waksmana (Marcin Bartkowiak)
• Algorytm sprawdzający czy słowo należy do języka (Przemek Joniak)
• problemy NP (Wojtek Balik)

Do wzięcia:

• Union-find
• Drzewa przedziałowe
• Hashowanie
• Shift-And
• Wyszukiwanie wzorca za pomocą automatu
• MP / KMP
• KR
• Drzewa czerwono-czarne
• B-drzewa
• Słownik statyczny
• Geometria obliczeniowa
• Kopce Fibonacciego
• Szybka transformata
• Drzewa Bossa
• bucket sort
• model drzew decyzyjnych
• dolna granica min-maks
• dolne granice
• optymalna kolejność mnożenia macierzy
• drzewa rozpinające drabiny
• Cykl Hamiltona
• 3SAT
• 3-wymiarowe skojarzenie
• algorytm stokrotek
• Algorytm D&Z otoczki wypukłej
• O modelach obliczeń
• Programowanie dynamiczne na drzewach
• LCS
• Algorytm Karatsuby
• Algorytm Boruvki
• O złożoności obliczeniowej
• Algorytm szeregownia
• Minimalne Drzewa Rozpinające (Kruskal, Prim)
• Sortowanie (Ania Karaś)
• Sortowanie topologiczne
• Kopiec binarny
• Statystyki pozycyjne
• Algorytm magicznych piątek
• Drzewa AVL
• izomorfizm drzew
• sortowanie ciągów różnej długości