Algorytmy i Struktury Danych

Wykład: Krzysztof Loryś

Ćwiczenia: Przemka Kanarek, Paweł Rzechonek, Tibor Różański,

Paweł Zalewski, Grażyna Zwoźniak

Pracownia: Piotr Wnuk-Lipiński

Ćwiczenia

· Aktualny ranking (administrowany przez P.Wnuk-Lipińskiego)

Zadania domowe

Proponowane terminy egzaminów:

· Kolokwium Połówkowe: 25.04.2005; godz.: 16-18;

·        Egzamin końcowy:                11.06.2005; godz.: 9-15;
II-gi termin                           23.06.2005; godz.: 9-15;
Egzamin poprawkowy           Zmiana!!!: 14.09.2005; godz.: 9-15

Projekty Programistyczne

· Projekty programistyczne

· Przydział projektów dla osób powtarzających

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.

· Wykład 2 (22.02): Algorytmy sortowania select i insert, maszyna RAM jako model obliczeń; notacja asymptotyczna. (Notatka nr 1.) Algorytmy zachłanne. Problem wydawania reszty, algorytmy znajdowania minimalnego drzewa rozpinającego: algorytm Prima, algorytm Kruskala, algorytm Sollina.

· Wykład 3 (23.02): Algorytmy zachłanne cd.: szeregowanie zadań, szeregowanie zadań z deadline’ami. (Notatka nr 2.)

· Wykłady 4 i 5 (1-2.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. Jednoczesne znajdowane maksimum i minimum. (Notatka nr 3.) Konstrukcja sieci permutacyjnych (sieci Beneša-Waksmana). Znajdowanie pary najbliżej położonych punktów. (Notatka nr 4.)

· Wykład 6 i 7 (8-9.03): Programowanie dynamiczne. Obliczanie współczynnika dwumianowego. „Stokrotki”:-). Najdłuższy wspólny podciąg. (Notatka nr 5.) Optymalna kolejność mnożenia macierzy. Przynależność słowa do języka bezkontekstowego. Drzewa rozpinające drabin. (Notatka nr 6.)

· Wykład 8 (15.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 9 (16.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. Analiza średniego przypadku: insertsort.

· Wykład 10 (22.03): 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 11 (23.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 12 (30.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. Algorytm oparty na próbkowaniu. (Notatka nr 10.)

· Wykład 13 (5.04): Kopiec. Definicja. Implementacja tablicowa. Realizacja operacji kopcowych. Zastosowania: heapsort, kolejka priorytetowa. Kopiec minmax – struktura implementująca podwójną kolejkę. (Notatka nr 11.)

· Wykład 14 (6.04): Kopiec dwumianowy (wersja eager). Zastosowanie: złączalne kolejki priorytetowe.

· Wykład 15 (12.04): Koszt zamortyzowany. Metoda kosztu sumarycznego. Metoda księgowania. Przykład: licznik w tablicy. Kopiec dwumianowy (wersja lazy).

· Wykład 16 (13.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 17 (19.04): Drzewa zbalansowane. Drzewa 1-2-3. Drzewa czerwono-czarne (definicja, rotacje, implementacja operacji słownikowych)

· Wykład 18 i 19 (20/26.04): 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 (27.04): Słowniki statyczne. Optymalne drzewa BST. Struktura oparta na dwupoziomowym hashowaniu.

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

· Wykład 22 (10.05): Union-Find. Metoda naiwna (tablica charakterystyczna zbioru) i jej modyfikacje (listy elementów, zbalansowane wykonywanie union). Struktura drzewiasta (zbalansowane wykonywanie union+skracanie ścieżek; analiza zamortyzowana)

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

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

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

· Wykład 26 i 27 (24/25.05): Wyszukiwanie wzorców. Algorytm naiwny. Wyszukiwanie wzorców automatem skończonym. Algorytm Karpa-Rabina. Algorytm KMP (Knutha-Morrisa-Pratta). Algorytm Boyera-Moore’a.

· Wykład 28 (31.05): Obliczenia równoległe. Model obliczeń – PRAM. Typy PRAM (EREW, CREW, CRCW: Common, Arbitrary, Priority, Robust). Znajdowanie maksimum w tablicy (algorytmy typu EREW i Common). Obliczenia prefiksowe. Klasa NC. Algorytmy NC dla problemów dodawania i mnożenia liczb.

· Wykład 29 (7.06): Sieci komparatorów. Kryteria efektywności. Zasada 0-1-kowa. Sortująca sieć bitoniczna Batchera.

· Wykład 30 (8.06): Algorytmy aproksymacyjne. Współczynnik aproksymacji. Problem znajdowania pokrycia wierzchołkowego grafu. Problem pokrywania zbioru (algorytm kombinatoryczny, redukcja do programowania całkowitoliczbowego).

Listy zadań

· Lista nr 1

· Lista nr 2

· Lista nr 3

· Lista nr 4

· Lista nr 5

· Lista nr 6

· Zadania z kolokwium połówkowego

· Lista nr 7

· Lista nr 8

· Lista nr 9

Komunikaty:

· Została podwieszona nowa wersja Notatki nr 1.

· Po „zmasowanych atakach” z Waszej strony udostępniam kolejne notatki. Bardzo proszę o czytanie ich z dużą dozą krytycyzmu i podejrzliwości. Będę wdzięczny za zgłaszanie mi wszelkich uwag (zależy mi zwłaszcza na wyeliminowaniu błędów merytorycznych i stylistycznych).

· Zmieniony został termin kolokwium połówkowego. Nie mogę gwarantować, że jest to ostatnia zmianaL

· wyniki kolokwium połówkowego.

· Zmuszony byłem zmienić termin egzaminu z AiSD (proszę o wyrozumiałość). Osoby, którym termin 11.06 nie odpowiada, mogą przyjść 23-ego (termin ten będzie potraktowany jako pierwszy).

· Częściowe wyniki egzaminu z 11-ego czerwca.

· wyniki egzaminu z 11-ego czerwca. Osoby, które uzyskały poniżej 10pkt z pierwszej części nie zdały egzaminu. Zapraszam je na egzamin 23-ego. Będą wówczas pisać obie części egzaminu.

· Wyniki pierwszej części egzaminu z 23-ego czerwca. Próg zaliczenia egzaminu wynosi 10 pkt.

· Wyniki egzaminu z 23-ego czerwca. Próg zaliczenia egzaminu został obniżony do 8.5 pkt.

· Punkty za ćwiczenia. Uwagi:

1. Zestawienie obejmuje tylko studentów uczęszczających na ćwiczenia w ostatnim semestrze.

2. Proszę pamiętać, że punktacja zależy od progów na oceny (a te różnią się w poszczególnych grupach)

· Pan Piotr Wnuk-Lipiński obiecał, że do końca tygodnia wyniki punktowe za projekty programistyczne ukażą się na stronie http://www.ii.uni.wroc.pl/~lipinski/aisd/notes.html

· W odpowiedzi na Wasze prośby zmieniam termin egzaminu poprawkowego na 14.09. 05 (poprzedni termin kolidował z terminem egzaminu z JF).

· Punkty za pracownię.

· Poniżej podaję progi punktowe na ocenę końcową. Na ich podstawie oraz na podstawie warunków zaliczenia przedmiotu każdy może określić sensowność zdawania egzaminu poprawkowego. Mogą przystąpić do niego także te osoby, które chcą jedynie poprawić obecną ocenę.