Algorytmy i Struktury Danych

Wykład: Krzysztof Loryś

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

Grażyna Zwoźniak,

Repetytorium: Grażyna Zwoźniak

Pracownia: Marcin Bieńkowski

· Zasady zaliczania przedmiotu

· Zasady oceniania na ćwiczeniach

Rankingi w grupach (wkrótce):

Komunikaty:

· Wyniki egzaminu poprawkowego (w ExceluL).

· Informacje ważne dla osób, które jeszcze nie zdały egzaminu (choć może nie tylko dla nich):

1. egzamin poprawkowy zaplanowałem na 14-tego września (godz. 8.30-15.00). Egzamin odbędzie się w dużej sali wykładowej.

2. do egzaminu mogą przystąpić także osoby, które zdały egzamin lecz chcą poprawić swoje notowania.

3. można poprawiać obie części lub tylko jedną (pierwszą lub drugą)

4. nie można pogorszyć swej punktacji z pierwszego terminu z jednym wszakże wyjątkiem, gdy osoba uzyska więcej niż dwa „!”. Wówczas zapominamy o punktach uzyskanych w pierwszym terminie (o punktach za pierwszą część egzaminu).

5. można zrezygnować z pisania egzaminu w trakcie jego trwania bez żadnych przykrych konsekwencji.

6. osoby, które w pierwszym terminie nie zdały egzaminu wyłącznie z powodu zbyt dużej liczby wykrzykników mogą zamiast egzaminu poprawkowego zdać jedynie materiał objęty zadaniami, które w pierwszym terminie zostały ocenione na „!”. Obiecuję, że w tym przypadku zadania będą gruntownie weryfikować wiedzę. Mogę taki egzamin przeprowadzić jeszcze lipcu (w środę 11-tego; w godzinach popołudniowych). Osoby chętne proszone są o zgłoszenie poprzez email na adres lorysster@gmail.com . Udział w tym egzaminie nie wyklucza udziału w terminie poprawkowym.

· Progi punktowe na ocenę końcową są następujące:

Celująca 90pkt

Bardzo dobra 70pkt

Dobra + 62pkt

Dobra 54pkt

Dostateczna + 46pkt

Dostateczna 38pkt

· Oceny będę wpisywać do indeksu w czwartek 5.06. (godz. 10-12). Oczywiście tylko tym, którzy spełnili wszystkie wymagania i chcą uzyskać wpis.

· Kompletne wyniki egzaminu (w ExceluL). Warunkiem zdania egzaminu było uzyskanie co najmniej 10 pkt w części I przy jednoczesnym „skompromitowaniu się” w nie więcej niż dwóch zadaniach („kompromitacje” oznaczone są przez „!”) . Wkrótce podam informacje istotne dla osób, które nie zdały (proszę zaglądać na tę stronę).

· Niestety nie wszyscy sprawdzający zdołają sprawdzić prace egzaminacyjne do jutra. Wobec tego wyniki egzaminu zostaną podane w środęL. Wówczas będę także do Waszej dyspozycji (od godziny 16-tej).

· Egzamin odbędzie się 30 czerwca w godz. 8-14. Barbarzyńska pora wynika z braku wolnych sal w późniejszych godzinachL

· Kompletne wyniki kolokwium.

· Kolokwium odbędzie się w godzinach 14-17. Pisać będziecie w salach wykładowych.

· Zmiana: Na prośbę studentów obecnych na wykładzie 8-go maja zmieniam termin kolokwium połówkowego na 19-ty maja (sobota). Godziny ustalę po tym, jak skompletuję ekipę osób pilnujących.

· Przypominam, że obowiązuje umiejętność rozwiązywania zadań nadobowiązkowych. Zadania te rozwiązywane są na repetytorium.

· Notatki 4-6 pojawią się wkrótce.

Spis treści wykładu

· Wykład 1 (27.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 (6.03): 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. Aproksymacyjny algorytm dla problemu Set Cover (Notatka nr 2.)

· Wykład 3 (8.03): 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 (15.03): Konstrukcja sieci permutacyjnych (sieci Beneša-Waksmana). (Notatka nr 4.) Programowanie dynamiczne. Obliczanie współczynnika dwumianowego. „Stokrotki”:-). Najdłuższy wspólny podciąg. (Notatka nr 5.)

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

· Wykład 6 (22.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. Liniowe drzewa decyzyjne: dolna granica dla problemu „Element Uniqueness”.

· Wykład 7 (27.03): Powtórka na życzenie: Liniowe drzewa decyzyjne: dolna granica dla problemu „Element Uniqueness”. Redukcje w dowodzeniu dolnych granic (redukcja Problemu Istnienia Cyklu Hamiltona do Problemu Przybliżonego Zliczania Cykli Prostych).

· Wykład 8 (29.03): Sortowanie: sortowanie przez zliczanie, sortowanie kubełkowe, sortowanie leksykograficzne ciągów jednakowej długości, sortowanie leksykograficzne ciągów dowolnej długości. (Notatka nr 8. – wersja robocza)

· Wykład 9 (3.04): Przykład zastosowania sortowania leksykograficznego: izomorfizm drzew. 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 10 (5.04): Kopiec. Definicja. Implementacja tablicowa. Realizacja operacji kopcowych. Zastosowania: heapsort, kolejka priorytetowa. Kopiec minmax – struktura implementująca podwójną kolejkę. (Notatka nr 10.)

· Wykład 11 (12.04): Selekcja: Przypadki szczególne: znajdowanie maksimum, znajdowanie drugiego co do wielkości elementu. Algorytm Hoare’a. Algorytm magicznych piątek.

· Wykład 12 (17.04) Selekcja: algorytm oparty na próbkowaniu.

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

· Wykład 14 (24.04): Kopiec dwumianowy (wersja lazy). Kopiec Fibonacciego. Zastosowanie: algorytm Dijkstry.

· Wykład 15 (26.04): Drzewa zbalansowane. Drzewa AVL (definicja, ograniczenie na wysokość drzew, rotacje, implementacja operacji słownikowych).

· Wykład 16 (8.05): Drzewa zbalansowane (cd.). B-drzewa (definicja, liczba operacji i/o jako miara złożoności, realizacja operacji słownikowych). Drzewa czerwono-czarne (definicja, implementacja operacji słownikowych, związek z B-drzewami)

· Wykład 17 (10.05): Problem UNION-FIND. Zastosowanie: algorytm Kruskala. Struktura listowa. Struktura drzewiasta (analiza zamortyzowana kosztu operacji). Tryby on-line i off-line wykonywania ciągu operacji.

· Wykład 18 (15.05): Drzewa zbalansowane. Drzewa czerwono-czarne (definicja, rotacje, implementacja operacji słownikowych, związek z 2-3 drzewami). Struktury samoorganizujące się. Idea. Heurystyki dla list samoorganizujących się. Drzewa rozchylane (splay trees). Operacja splay. Koszt zamortyzowany.

· Wykład 19 (22.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 20 i 22 (24.05 i 29.05): Stałe słowniki. Optymalne drzewa BST. Struktura oparta na podwójnym hashowaniu.

· Wykład 23 (31.05): Drzewce. Definicja. Jednoznaczność konstrukcji. Drzewce losowe. Implementacja operacji słownikowych na drzewcach. Analiza oczekiwanego czasu wykonania delete.