Algorytmy i Struktury Danych

Wykład: Krzysztof Loryś

Ćwiczenia: Przemka Kanarek, Krzysztof Loryś, Paweł Rzechonek, ,

Grzegorz Stachowiak, Paweł Zalewski,

Repetytorium: Grażyna Zwoźniak

Pracownia: Marcin Bieńkowski

· Zasady zaliczania przedmiotu

· Zasady oceniania na ćwiczeniach

Rankingi w grupach:

· Grupa G.Stachowiaka (format *.sxc)

· Grupa P.Zalewskiego (format *.ods)

Komunikaty:

· 19.09. Częściowe wyniki egzaminu poprawkowego (brakuje jeszcze wyników zadania nr 1 z pierwszej części)

· Egzamin poprawkowy odbędzie się 14-tego września (początek: godz. 9.00)

· Progi punktowe na poszczególne oceny zostają ustalone na takim samym poziomie jak w ubiegłym roku (patrz ubiegłoroczna strona wykładu).

· We wtorek (4 lipca) w godzinach 12-14 będzie można obejrzeć własne prace, porozmawiać o rozwiązaniach i sposobie oceniania.

· Próg zaliczenia pierwszej części egzaminu został ustalony na 46pkt. Osoby, które uzyskały mniej punktów zapraszam na egzamin wrześniowy.

· 26.06. Wyniki egzaminu (jeszcze będą weryfikowane)

· 15.05. Wyniki kolokwium połówkowego.

· 12.05. Najbliższe repetytorium poświęcone będzie kolokwium połówkowemu. W szczególności:

o Przedstawimy rozwiązania

o Omówimy najczęstsze błędy

o Poznacie kryteria oceny

o Będzie możliwość wglądu we własną pracę i złożenia reklamacji (będzie to jedyna taka sposobność).

· 20.04. Kolokwium połówkowe odbędzie się w czwartek w 27.04.06 w godzinach 12-14.

· 9.03. Wprowadziłem zmiany a liście nr 5

· 22.03. Awaria strony została (chwilowo) usunięta.

· 4.03. Uwagi do kartkówki nr 1.

· 25.02. Proszę pamiętać, że na kartkówkach obowiązuje także materiał omówiony na (wszystkich, dotychczasowych) wykładach.

· 18.02. Już na pierwszych ćwiczeniach można spodziewać się kartkówki, a na niej:

o Zadań z pierwszej listy (także tych nieobowiązkowych)

o Pytań do treści pierwszego wykładu

Spis treści wykładu

· Wykład 1 (16.02): Podstawowe pojęcia: problemy, algorytmy, programy, złożoność. Algorytmy: mnożenie „po rosyjsku”, szybkie potęgowanie, szybkie obliczanie liczb Fibonacciego. Algorytmy sortowania select i insert, maszyna RAM jako model obliczeń; notacja asymptotyczna. (Notatka nr 1.)

· Wykład 2 (21.02): Algorytmy zachłanne. Problem wydawania reszty, algorytmy znajdowania minimalnego drzewa rozpinającego: algorytm Prima, algorytm Kruskala, algorytm Sollina. szeregowanie zadań, szeregowanie zadań z deadline’ami. (Notatka nr 2.)

· Wykład 3 (23.02): Metoda Dziel i Zwyciężaj. Algorytmy sortowania: mergesort i quicksort. Algorytm mnożenia długich liczb: podział na 2 części; uogólnienie na większą liczbę części. (Notatka nr 3.)

· Wykład 4 (28.02): Jednoczesne znajdowane maksimum i minimum. Konstrukcja sieci permutacyjnych (sieci Beneša-Waksmana). Znajdowanie pary najbliżej położonych punktów. (Notatka nr 4.)

· Wykład 5 (2.03): Programowanie dynamiczne. Obliczanie współczynnika dwumianowego. „Stokrotki”:-). Najdłuższy wspólny podciąg. (Notatka nr 5.)

· Wykład 6 (7.03): Optymalna kolejność mnożenia macierzy. Przynależność słowa do języka bezkontekstowego. Drzewa rozpinające drabin. (Notatka nr 6.)

· Wykład 7 (9.03): Dolne granice. Drzewa decyzyjne: dolna granica na liczbę porównań algorytmów sortujących (złożoność najgorszego i średniego przypadku). Gra adwersarza z algorytmem: dolna granica w modelu drzew decyzyjnych dla problemu jednoczesnego znajdowania minimum i maksimum.

· Wykład 8 (14.03): Dolne granice (cd). Redukcje w dowodzeniu dolnych granic: dolna granica dla problemu znajdowania otoczki wypukłej. Liniowe drzewa decyzyjne: dolna granica dla problemu „Element Uniqueness”. Redukcje przestrzeni rozwiązań. Definicja algebraicznych drzew decyzyjnych.

· Wykład 9 (16.03): Sortowanie: sortowanie prze zliczanie, sortowanie kubełkowe, sortowanie leksykograficzne ciągów jednakowej długości, sortowanie leksykograficzne ciągów dowolnej długości.

· Wykład 10 (21.03): Przykład zastosowania sortowania leksykograficznego: izomorfizm drzew. Selekcja. Przypadki szczególne: znajdowanie maksimum, znajdowanie drugiego co do wielkości elementu. Algorytm Hoare’a. Algorytm magicznych piątek.

· Wykład 11 (23.03): Selekcja: algorytm oparty na próbkowaniu. Kopiec. Definicja. Implementacja tablicowa. Realizacja operacji kopcowych. Zastosowania: heapsort, kolejka priorytetowa. Kopiec minmax – struktura implementująca podwójną kolejkę.

· Wykład 12 (28.03): Kopiec dwumianowy (wersja eager). Zastosowanie: złączalne kolejki priorytetowe. Koszt zamortyzowany. Metoda księgowania. Przykład: licznik w tablicy.

· Wykład 13 (30.03): Kopiec dwumianowy (wersja lazy). Analiza średniego kosztu na przykładzie insertsort (zastosowanie liniowości wartości oczekiwanej)

· Wykład 14 (4.04): Drzewa zbalansowane. Drzewa AVL (definicja, ograniczenie na wysokość drzew, rotacje, implementacja operacji słownikowych). B-drzewa (definicja, liczba operacji i/o jako miara złożoności, realizacja operacji słownikowych).

· Wykład 15 (6.04): Drzewa zbalansowane.. Drzewa czerwono-czarne (definicja, rotacje, implementacja operacji słownikowych, związek z 2-3 drzewami)

· Wykład 16 i 17 (11.04 i 13.04) Problem Union-Find.

· Wykład 18 (20.04): Quicksort: metody wyboru pivota (deterministyczna, losowa, mediana z małej próbki); analiza oczekiwanego czasu działania przy losowym pivocie; usprawnienia Quicksorta (trójpodział, eliminacja rekursji, „quicksort w miejscu”.

· Wykład 19 (25.04): Sortowane zewnętrzne.

· Wykład 20 i 21 (27.04 i 4.05): Hashowanie. Podstawy teoretyczne (schemat urnowy). Przykłady funkcji hashujących. Kolizje. Pamiętanie elementów kolidujących (nawlekanie, adresowanie otwarte). Usuwanie kolizji (metoda liniowa, metoda kwadratowa, podwójne hashowanie). Oczekiwana liczba prób przy poszukiwaniu elementu. Uniwersalne rodziny funkcji hashujących.

· Wykład 22 (9.05): Słowniki statyczne. Struktura oparta na dwupoziomowym hashowaniu.

· Wykład 23 (16.05): Kopce Fibonacciego. Zastosowanie: Algorytm Dijkstry. Struktura kopca. Kaskadowe odcinanie poddrzew. Analiza zamortyzowana ciągu operacji kopcowych.

· Wykład 24 (18.05):Struktury samoorganizujące się. Idea. Heurystyki dla list samoorganizujących się. Drzewa rozchylane (splay trees). Operacja splay. Koszt zamortyzowany.

· Wykład 25 (23.05): Mnożenie macierzy. Metoda Strassena. Mnożenie macierzy logicznych. Metoda czterech Rosjan.

· Wykład 26 (25.05): FFT. Idea. Własności n-tych pierwiastków z jedności. Zastosowanie do mnożenia macierzy.

· Wykład 27 i 28 (30.05/1.06): Wyszukiwanie wzorców. Algorytm naiwny. Wyszukiwanie wzorców automatem skończonym. Algorytm Karpa-Rabina. Algorytm KMP (Knutha-Morrisa-Pratta). Algorytm Boyera-Moore’a. Algorytm Shift-And. Algorytm Bakera. Algorytm Karpa-Millera-Rosenberga.