algorytmy i struktury danych

Celem wykładu jest zaprezentowanie studentom wielu różnorodych zadań obliczeniowych oraz skutecznych i efektywnych metod ich rozwiązywania. Na wykładzie omawiane są podstawowe techniki konstuowania algorytmów i analizy ich złożoności obliczeniowej, a dla wybranych problemów przedstawione są ich dolne granice złożonościowe. Szczególny nacisk jest położony na sposób, w jaki dane są przechowywane w pamięci komputera, gdyż od organizacji danych bardzo często zależy czas działania programu rozwiązującego określone zadanie.

Zakłada się, że po zakończeniu wykładu studenci będa potrafili przeanalizować zadany problem, wybrać odpowiednią technikę jego rozwiązania, będą umieli zaprogramować wybrany lub wymyślony algorytm wykorzystując najbardziej odpowiednią strukturę danych dla danego zadania oraz będą potrafili oszacować jego czas działania i zapotrzebowanie na pamięć.

wymagane przygotowanie
  • Podstawowa wiedza z przedmiotów programowanie i matematyka dyskretna.
  • Umiejętność programowania w języku C/C++ oraz znajomość elementarnych struktur danych (tablice, listy, drzewa, grafy).
literatura

Literatura podstawowa:

  • T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein: Wprowadzenie do algorytmów. WNT, Warszawa 2004.
  • L.Banachowski, K.Diks, W.Rytter: Algorytmy i struktury danych. WNT, Warszawa 1996.

Literatura uzupełniająca:

  • R.Neapolitan, K.Naimipour: Podstawy algorytmów z przykładami w C++. Helion, Gliwice 2004.
  • R.Sedgewick: Algorytmy w C++. RM, Warszawa 1999.
  • A.V.Aho, J.E.Hopcroft, J.D.Ullman: Projektowanie i analiza algorytmów. Helion, Gliwice 2003.
  • A.V.Aho, J.E.Hopcroft, J.D.Ullman: Algorytmy i struktury danych. Helion, Gliwice 2003.
  • A.V.Aho, J.D.Ullman: Wykłady z informatyki z przykładami w języku C. Helion, Gliwice 2003.
  • N.Wirth: Algorytmy + struktury danych = programy. WNT, Warszawa 2004.
  • D.Knuth: Sztuka programowania (tom 1, 2, 3). WNT, Warszawa 2001.
  • J.Bentley: Perełki oprogramowania. WNT, Warszawa 2001.
  • D.Harel: Rzecz o istocie informatyki. Algorytmika. WNT, Warszawa 2001.

Literatura anglojęzyczna:

  • J.Kleinberg, E.Tardos: Algorithm design. Addison-Wesley, 2005.
  • G.Brassard, P.Bratley: Algorithmics - theory & practice. Prentice Hall, 1993.
  • D.C.Kozen: The Design and analysis of algorithms. Springer-Verlag, 1992.
program wykładu
  • Złożoność obliczeniowa i jej szacowanie. Pesymistyczna i oczekiwana złożoność algorytmu.
  • Sortowanie: elementarne metody, sortowanie Shella. Model drzew decyzyjnych i dolne ograniczenie na problem sortowania. Sortowanie w czasie liniowym: counting-sort, radix-sort, bucket-sort.
  • Scalanie i sortowanie przez scalanie merge-sort. Sortowanie zewnętrzne.
  • Podział i sortowanie szybkie quick-sort. Problem wyboru: algorytmy Hoare'a i "magicznych piątek".
  • Analiza kosztu zamortyzowanego. Tablice dynamiczne.
  • Haszowanie: rozwiązywanie kolizji metodą łańcuchową i za pomocą adresowania otwartego.
  • Słowniki: drzewa BST, losowe BST, drzewa SPLAY, drzewa zrównoważone AVL i RBT. Słowniki zewnętrzne: B-drzewa i 2-3-4-drzewa. Słowniki pozycyjne: drzewa RST i TRIE.
  • Kolejki priorytetowe: kopiec, kopiec minimaksowy. Złączalne kolejki priorytetowe: kopce dwumianowe, drzewa lewicowe.
  • Zbiory rozłączne: reprezentacja listowa i drzewiasta.
  • Projektowanie algorytmów metodą "dziel i~zwyciężaj". Przykłady: mnożenie długich liczb, mnożenie macierzy metodą Strassena. Uniwersalne twierdzenie o rekurencji.
  • Projektowanie algorytmów za pomocą programowania dynamicznego. Przykłady: najdłuższy wspólny podciąg, optymalne mnożenie macierzy. Rekurencja ze spamiętywaniem.
  • Projektowanie algorytmów przy pomocy strategii zachłannej. Przykłady: wydawanie reszty, kody Huffmana, ciągły problem plecakowy, problem wyboru zajęć.
  • Algorytmy wielomianowe, pseudowielomianowe i ponadwielomianowe. Wielomianowe redukcje. Problemy optymalizacyjne i odpowiadające im problemy decyzyjne. Algorytmy niedeterministyczne i weryfikacja w czasie wielomianowym. Klasy problemów P i NP. Problemy NP-zupełne: CIRCUIT-SAT, SAT, 3-CNF.

powrót na początek strony

Terminarz

dzienne studia licencjackie

zajęcia
kolokwia
  • kolokwium 1: piątek, 16.11.2007, godz.8:15, s.118
  • kolokwium 2: piątek, 14.12.2007, godz.8:15, s.25
  • kolokwium 3: piątek, 25.01.2008, godz.8:15, s.25
egzaminy
  • podstawowy: poniedziałek, 4.02.2008, godz.14-18, s.25
  • uzupełniający: sobota, 9.02.2008, godz.10-14, s.141
  • poprawkowy: piątek, 15.02.2008, godz.10-14, s.141

wieczorowe studia licencjackie

zajęcia
kolokwia
  • kolokwium 1: środa, 14.11.2007, godz.16:15, s.118 (kameralna zachodnia)
  • kolokwium 2: środa, 19.12.2007, godz.16:15, s.118 (kameralna zachodnia)
  • kolokwium 3: środa, 23.01.2008, godz.16:15, s.118 (kameralna zachodnia)
egzaminy
  • podstawowy: wtorek, 5.02.2008, godz.16-20, s.25
  • uzupełniający: sobota, 9.02.2008, godz.10-14, s.141
  • poprawkowy: piątek, 15.02.2008, godz.16-20, s.141

powrót na początek strony

Ogłoszenia

24.02.2008 (egzamin)
Jutro 12:15, czyli w poniedziałek 25.02.2008, będę robił wpisy do indeksów z egzaminu (i z laboratorium) z AiSD.
13.02.2008 (egzamin poprawkowy)
Osoby, które zaliczyły test w terminie podstawowym są zwolnione z testu w terminie poprawkowym. Mogą go napisać jeszcze raz, ale wówczas kasuje im się poprzedni wynik (a test na egzaminie poprawkowym na pewno nie jest łatwiejszy - wielomianowa redukcja jednego testu do drugiego zadziałałaby w jednym kierunku, ale w przeciwną stronę niekoniecznie :).
12.02.2008 (egzamin)
Omówienie wyników egzaminu podstawowego i zadań jutro (środa 13.02.2008) o godz.18:15 w salach 103 (st.wiecz.) i 105 (st.dz.).
11.02.2008 (egzamin)
Są już wyniki z egzaminu.
10.02.2008 (egzamin)
Jutro wieczorem pojawią się wyniki z egzaminu.
29.01.2008 (laboratorium)
Przychylając się do prośby studentów, przesunąłem termin nadsyłania zadania 4 na laboratorium do czwartku 31.01.2008.
19.01.2008 (kolokwium)
Trzecie kolokwium odbędzie się w przyszłym tygodniu podczas repetytorium (szczegóły w terminarzu). Materiał, z którego należy się przygotować to drzewa pozycyjne (RST), kolejki priorytetowe (kopce binarne i dwumianowe), zbiory rozłączne (struktura listowa i drzewiasta) i rozwiązywanie problemów obliczeniowych techniką "dziel i zwyciężaj" - obejmuje materiał z list 10/11-13.
18.01.2008 (repetytorium - studia wieczorowe)
Dodatkowe repetytorium, na którym zostaną omówione zadania z listy 15 (strategia zachłanna), odbędzie się w środę 30.01.2008 o 16:15 w sali obok laboratorium.
16.01.2008 (laboratorium)
Przychylając się do gorących próśb studentów, przesunąłem termin nadsyłania zadania 3 na laboratorium do piątku 18.01.2008.
11.01.2008 (kolokwium)
Trzecie kolokwium odbędzie się za dwa tygodnie podczas repetytorium (szczegóły w terminarzu). Materiał, z którego należy się przygotować to drzewa pozycyjne, kolejki priorytetowe, zbiory rozłączne i rozwiązywanie problemów obliczeniowych techniką "dziel i zwyciężaj" - obejmuje materiał z list 10/11-13.
11.01.2008 (laboratorium)
Zostało opublikowane ostatnie zadanie na laboratorium z terminem na 27.01.2008.
4.01.2008 (egzamin)
Został zmieniony termin egzaminu poprawkowego z AiSD na studiach dziennych i wieczorowych w sesji zimowej. Egzamin poprawkowy odbędzie się w piątek 15 lutego 2008r.
18.12.2007 (laboratorium)
Na prośbę studentów przesunąłem terminy oddawania zadań na laboratorium - drugie zadanie na 6.01.2008 i trzecie na 13.01.2008.
Będzie jeszcze zadanie czwarte (dotyczące programowania dynamicznego albo metody dziel i zwyciężaj) z terminem na 27.01.2008.
14.12.2007 (egzamin)
Zostały już wyznaczone terminy egzaminów z AiSD na studiach dziennych i wieczorowych w sesji zimowej. Proszę sobie zawczasu zarezerwować czas ;)
12.12.2007 (kolokwium - studia wieczorowe)
Drugie kolokwium na studiach wieczorowych odbędzie się w przyszłym tygodniu w środę podczas repetytorium (szczegóły w terminarzu). Materiał, z którego należy się przygotować to koszt zamortyzowany, haszowanie i słowniki - obejmuje materiał z list 6-10.
9.12.2007 (laboratorium)
Zostały opublikowane kolejne dwa zadania na laboratorium - drugie z terminem 23.12.2007 i trzecie z terminem 6.01.2008.
Pierwsze zadanie postaram się sprawdzić przed świętami.
7.12.2007 (repetytorium - studia wieczorowe)
W przyszłym tygodniu 12.12.2007 repetytorium dla studentów wieczorowych w zastępstwie za A.Jeża poprowadzi P.Gawrychowski.
6.12.2007 (kolokwium - studia dzienne)
Drugie kolokwium na studiach dziennych odbędzie się w przyszłym tygodniu w piątek podczas repetytorium (szczegóły w terminarzu). Materiał, z którego należy się przygotować to koszt zamortyzowany, haszowanie i słowniki - obejmuje materiał z list 6-10.
18.11.2007 (kolokwium)
Są już dostępne wyniki z kolokwium 1.
18.11.2007 (ćwiczenia)
Lista 7 to lista awaryjna - nie odbył się wykład, bo czwartek 15.11.2007 był dniem wolnym od zajęć. Ale myślę, że nie będziecie się nudzili rozwiązując te zadania. Powodzenia!
14.11.2007 (laboratorium)
Termin nadsyłania programów na laboratorium przesunął się o jeden tydzień, czyli na 25.11.2007, ponieważ sprawdzaczka jeszcze nie jest uruchomiona :-(
14.11.2007 (kolokwium - studia wieczorowe)
Kolokwium dla studentów wieczorowych rozpocznie się o godzinie 16:15 w sali kameralnej zachodniej nr 118 (sala nr 105 okazała się zbyt mała jak na tak liczną grupę).
7.11.2007 (kolokwium)
Pierwsze kolokwium odbędzie się w przyszłym tygodniu podczas repetytorium (szczegóły w terminarzu). Materiał, z którego należy się przygotować to zagadnienia porządkowe (sortowanie, scalanie, podział, wybór k-tego elementu) - obejmuje materiał z list 1-5.
1.11.2007 (ćwiczenia)
Pierwszy ranking w moich grupach już jest zrobiony.
23.10.2007 (ćwiczenia)
Pierwszy ranking w moich grupach pojawi się pod koniec miesiąca.
20.10.2007 (wykład/ćwiczenia - studia wieczorowe)
Został zmieniony termin zajęć na studiach wieczorowych - od następnego tygodnia wykład i ćwiczenia z algorytmów i struktur danych będzie we wtorek.
3.10.2007 (ćwiczenia)
W pierwszym tygodniu semestru ćwiczenia nie odbędą się. Zostaną one odpracowane w ostatnim tygodniu semestru.

powrót na początek strony

Przebieg zajęć

wykład

Na wykładzie będą omawiane następujące zagadnienia z dziedziny algorytmiki:

  • złożoność obliczeniowa (szacowanie z dołu trudności problemów i z góry efektywności algorytmów);
  • zagadnienia porządkowe (sortowanie, scalanie, podział, wybór mediany);
  • zaawansowane struktury danych (tablice z haszowaniem, słowniki, kolejki priorytetowe, zbiory rozłączne);
  • metody konstruowania i analizy algorytmów dla problemów łatwych należących do klasy P (metoda "dziel i zwyciężaj", programowanie dynamiczne, technika zachłanna);
  • techniki rozwiązywania zadań trudnych z klasy NP (algorytmy z powrotami, metoda podziału i ograniczeń, algorytmy aproksymacyjne, algorytmy zrandomizowane, algorytmy ewolucyjne);
Pod koniec semestru w czasie sesji zostanie przeprowadzony egzamin sprawdzający wiadomości studentów z tego materiału.

Uwaga: Informacja o ostatecznym terminie egzaminów będzie ogłoszona na wykładzie (i na tej stronie) co najmniej miesiąc wcześniej.

repetytorium

Repetytorium jest uzupełnieniem wykładu i na zajęciach tych będą:

  • omawiane problemy i analizowane algorytmy, które je rozwiąziją;
  • szczególowo badane struktury danych i operacje na tych strukturach;
  • prezentowane rozwiązania wybranych zadań.
W czasie repetytorium będą zorganizowane trzy kolokwia sprawdzające wiadomości studentów z części omówionego materiału.

Uwaga: Punkty zdobyte z zaliczonych kolokwiów będą wliczane do punktacji z egzaminu. Informacja o terminie kolokwiów będzie ogłoszana na wykładzie (i na tej stronie) co najmniej tydzień wcześniej.

laboratorium

Laboratorium to praktyczne wykorzystanie wiedzy zdobytej na wykładzie. Projekty laboratoryjne będą polegały na pisaniu programów rozwiązujących określone problemy lub implementujących zaawansowane struktury danych, na testowaniu ich efektywności i sporządzaniu sprawozdań z przeprowadzanych eksperymentów.

Uwaga: Ocena z laboratorium będzie miała wpływ na dodatkowe punkty wliczane do punktacji z egzaminu.

ćwiczenia

Ćwiczenia sprawdzają zrozumienie materiału omówionego na wykładzie poprzez rozwiązywanie zadań algorytmicznych. Na każde ćwiczenia przygotowana będzie lista z zadaniami (będą one związane tematyczne z treścią ostatnich wykładów).

Uwaga: Ocena z ćwiczeń będzie miała wpływ na dodatkowe punkty wliczane do punktacji z egzaminu.

powrót na początek strony

Zasady zaliczeń

ćwiczenia
informacje ogólne

Na każde ćwiczenia będzie przygotowana osobna lista z zadaniami związana tematycznie z zagadnieniami omawianymi na wykładzie/repetytorium. Zadaniom na liście będzie przypisana określona liczba punktów (1, 2 lub 3) zależna od stopnia ich trudności. Przed rozpoczęciem zajęć każdy student powinien złożyć u prowadzącego deklarację, które zadania z bieżącej listy rozwiązał i potrafi zaprezentować przy tablicy. Osobę prezentującą rozwiązanie zadania przy tablicy wyznacza prowadzący na podstawie wcześniej złożonych deklaracji. Listy zadań będą przygotowywane na kilka dni przed zajęciami i udostępniane w internecie (na tej stronie).

szczegóły dotyczące zajęć
  • Po zakończeniu zajęć każdy student/studentka otrzymuje punkty za zadeklarowane zadania: w całości za zadania rozwiązane przy tablicy i 1/2 za zadania których nie zdążono zaprezentować w czasie zajęć. Dodatkowe punkty otrzymują studenci prezentujący swoje rozwiązania przy tablicy.
  • Za prezentację rozwiązania w czasie ćwiczeń przy tablicy można uzyskać dodatkowo podwojoną liczbę punktów przypisaną zadaniu (konsekwencje błędnych rozwiązań albo braku znajomości rozwiązania pomimo deklaracji są opisane poniżej). Prezentacje rozwiązań mają być dobrze przygotowane, w przeciwnym razie student nie zostanie wynagrodzony pełną liczbą możliwych do uzyskania punktów.
  • Na niektórych ćwiczeniach będą niezapowiedziane kartkówki. Na kartkówce, oprócz zadań niespodzianek, będzie się mogło znaleźć zadanie łatwe z bieżącej listy albo dowolne zadanie z listy wcześniejszej. Kartkówki będą przeprowadzane niezależnie w każdej grupie ćwiczeniowej. Łączna liczba punktów jaką można uzyskać za kartkówki w trakcie semestru będzie wynosić 10 punktów.
  • Za nieusprawiedliwioną nieobecność student otrzymuje minus połowę punktów możliwych do uzyskania za pełną deklarację zadań z bieżącej listy.
  • Za niepowodzenie przy tablicy (student miał dobry pomysł na rozwiązanie zadania, ale pomylił sie w obliczeniach lub zrobił inny drobny błąd) będzie studentowi skreślone dane zadanie z deklaracji.
  • Wykryte oszustwo, czyli nieznajomość rozwiązania pomimo deklaracji, będzie karane:
    • przy pierwszym wykroczeniu: -5 punktów karnych i skreślenie tego zadania z bieżącej deklaracji;
    • przy drugim wykroczeniu: -10 punktów karnych i skreślenie tego zadania z bieżącej deklaracji;
    • przy trzecim i kolejnym wykroczeniu: -10 punktów karnych i skreślenie wszystkich zadań z bieżącej deklaracji.
ocena z ćwiczeń

Oznaczmy przez S sumę punktów możliwych do uzyskania za pełne deklaracje z wszystkich list (oprócz listy rozruchowej) plus 10 możliwych do zdobycia punktów z kartkówek. Ocena zaliczeniowa z ćwiczeń będzie następująco zależeć od zdobytych punktów:

punkty ocena
<0.4*S 2
0.4*S... 3
0.5*S... 3+
0.6*S... 4
0.7*S... 4+
0.8*S... 5

Ocena z ćwiczeń będzie przeliczana na dodatkowe punkty wliczane do punktacji z egzaminu: liczba punktów z ćwiczeń to dwukrotna wartość oceny.

laboratorium
informacje ogólne

W ramach pracowni trzeba będzie napisać 4 programy, związane tematycznie z omawianymi na wykładzie/repetytorium algorytmami lub strukturami danych. Tematy projektów programistycznych wraz z terminami ich realizacji będą ogłaszane na listach z zadaniami. Każda lista z zadaniem będzie przygotowana na kilka tygodni przed ostatecznym terminem realizacji projektu i udostępniona w internecie (na tej stronie).

szczegóły dotyczące zajęć
  • Programy mają być napisane w czystym języku ANSI C/C++. Proszę nie korzystać z niestandardowych bibliotek specyficznych dla poszczególnych producentów oprogramowania (Microsoft, Borland, etc.). Programy będą kompilowane kompilatorem gcc 4.2.0 i uruchamiane pod kontrolą systemu operacyjnego SunOS 5.10 na serwerze swiatowit.
  • Zadania oceniane będą automatycznie za pośrednictwem sprawdzaczki (serwisu automatycznie testującego poprawność programów). Wysłanie zadania do oceny jest możliwe po uprzednim zarejestrowaniu się i zalogowaniu na tej stronie.
  • Dane do programu mają być czytane ze standardowego wejścia a wyniki mają być wypisywane na standardowym wyjściu. Należy bezwzględnie przstrzegać formatu danych i wyników. Dodatkowe komentarze i komunikaty można posyłać tylko do standardowego wyjścia dla błędów (w ogóle nie jest to potrzebne w ostatecznej wersji programu).
  • Każdy program zostanie uruchomiony dla kilku lub kilkunasu różnych zestawów danych, zwanych testami. Oceniany program otrzymuje liczbę punktów zależną od liczby poprawnie wykonanych testów.
  • Programy mają być napisane z myślą o efektywności (powinny być testowane na dużych danych). Dla poszczególnych zadań będzie wyznaczony czas odcięcia, czyli dopuszczalny czas na wykonanie się programu. Programy działające dłużej będą likwidowane przez system testujący.
  • Programy mają być napisane w sposób staranny i czytelny. Powinny być opatrzone stosownymi komentarzami (należy opisać użyty algorytm i zasosowane struktury danych). Na początku każdego programu powinno się znaleźć imię i nazwisko oraz numer indeksu autora. Wszystkie programy będą ze sobą porównywane. W przypadku wykrycia identycznych lub bardzo podobnych rozwiązań ich autorom grożą sankcje, włącznie z niezaliczeniem przedmiotu.
ocena z laboratorium

Oznaczmy przez S sumę punktów możliwych do uzyskania za całkowicie poprawne zaprogramowanie wszystkich zadań. Ocena zaliczeniowa z laboratorium będzie następująco zależeć od zdobytych punktów:

punkty ocena
<0.4*S 2
0.4*S... 3
0.5*S... 3+
0.6*S... 4
0.7*S... 4+
0.8*S... 5

Ocena z laboratorium będzie przeliczana na dodatkowe punkty wliczane do punktacji z egzaminu: liczba punktów z laboratorium to wartość tej oceny.

kolokwia
informacje ogólne

W czasie semestru odbędą się 3 kolokwia. Udział studentów w kolokwiach jest obowiązkowy.

szczegóły dotyczące kolokwium

Każde kolokwium będzie się składało z dwóch części: testowej (5 prostych pytań) i zadaniowej (2 zadania). Za udzielenie poprawnych odpowiedzi do wszystkich pytań z części testowej będzie można dostać 5 punktów, a za poprawne rozwiązanie obu zadań z części zadaniowej 10 punktów (łącznie 15 punktów). Kolokwium uważa się za zaliczone, jeśli student otrzyma co najmniej 2 punkty z części testowej oraz co najmniej 6 punktów z obu części. Kolokwiów nie można poprawiać.

oceny z kolokwiów

Punkty uzyskane z zaliczonych kolokwiów wliczają się do punktacji z egzaminu.

egzamin
informacje ogólne

Do egzaminu mogą przystąpić tylko te osoby, które mają zaliczone ćwiczenia i laboratorium. Każdy student ma prawo przystąpić do egzaminu dwukrotnie: raz w sesji egzaminacyjnej i raz w sesji poprawkowej. W sesji egzaminacyjnej będą wyznaczone dwa terminy egzaminu podstawowego (drugi termin jest tylko dla osób, które z ważnych powodów nie mogły uczestniczyć w pierwszym terminie). Dla osób, którym się nie powiodło za pierwszym razem, będzie zorganizowany egzamin poprawkowy w sesji poprawkowej.

szczegóły dotyczące egzaminu

Egzamin będzie się składał z dwóch części: testowej (10 prostych pytań) i zadaniowej (4 zadania). Za udzielenie poprawnych odpowiedzi do wszystkich pytań z części testowej będzie można dostać 20 punktów, a za poprawne rozwiązanie czterech zadań z części zadaniowej 40 punktów (łącznie 60 punktów). Egzamin uważa się za zdany, jeśli student otrzyma co najmniej 8 punktów z części testowej oraz co najmniej 24 punkty z obu części.

oceny z egzaminu

Ocena końcowa z egzaminu będzie wyliczona na podstawie oceny z ćwiczeń, oceny z laboratorium, punktów zdobytych na kolokwiach i przede wszystkim punktów zdobytych na egzaminie:

punkty ocena
<39 2
39... 3
52... 3+
65... 4
78... 4+
91...120 5

powrót na początek strony

Notatki

wykład
  • 4/5.10.2007 - złożoność obliczeniowa, efektywność algorytmów:
    • podstawowe pojęcia: algorytmy i problemy;
    • złożoność obliczeniowa: pamięciowa i czasowa;
    • asymptotyka: górne i dolne ograniczenia
    • przykład: tradycyjne mnożenie macierzy;
    • wydajność algorytmów;
    • przykład: mnożenie długich liczb metodą naiwną i po rosyjsku;
    • przykład: obliczanie liczb Fibonacciego metodą rekurencyjną, iteracyjną i macierzową;
    • złożoność obliczeniowa: w każdym przypadku, w najgorszym i w średnim;
    • przykład: wyszukiwanie zadanej wartości w nieuporządkowanej tablicy.
  • 11/12.10.2007 - sortowanie, dolna granica na sortowanie, sortowanie liniowe: (pdf/ps)
    • definicja problemu sortowania;
    • elementarne metody sortowania (bąbelkowe, przez zamianę, przez wstawianie, przez wyszukiwanie);
    • sortowanie Shella;
    • [*] drzewa decyzyjne i dolna granica dla problemu sortowania;
    • sortowanie przez zliczanie;
    • sortowanie kubełkowe;
    • sortowanie leksykograficzne.
  • 18/19.10.2007 - scalanie, sortowanie przez scalanie, sortowanie zewnętrzne:
    • definicja problemu scalania;
    • scalanie z wykorzystaniem zewnętrznego bufora pomocniczego;
    • [*] algorytm Kronroda - scalanie w miejscu;
    • rekurencyjna implementacja sortowania przez scalanie;
    • sortowanie zewnętrzne.
  • 23/25/30.10.2007 - podział, sortowanie szybkie, wybór k-tego elementu:
    • definicja problemu podziału;
    • algorytmy podziału (algorytm Lomuta, algorytm Sedgewicka);
    • sortowanie szybkie (przez podział);
    • definicja problemu wyboru k-tego co do wielkości elementu;
    • jednoczesne znajdowanie minimum i maksimum;
    • algorytmy wyboru k-tego elementu (algorytm Hoare'a, algorytm magicznych piątek).
  • 6/8.11.2007 - koszt zamortyzowany, tablice dynamiczne:
    • definicja kosztu zamortyzowanego dla ciągu operacji;
    • metoda kosztu sumarycznego;
    • metoda księgowania;
    • metoda potencjału;
    • [*] tablice dynamiczne;
    • [*] analiza kosztu zamortyzowanego ciągu operacji na tablicy dynamicznej.
  • 13/20/22.11.2007 - haszowanie:
    • zbiór dynamiczny;
    • słownik statyczny;
    • adresowanie bezpośrednie;
    • tablice z haszowaniem;
    • dobre funkcje haszujące;
    • [*] uniwersalna rodzina funkcji haszujących;
    • łańcuchowa metoda rozwiązywania kolizji;
    • rozwiązywanie kolizji metodą adresowania otwartego (liniowego, kwadratowego i podwójnego);
    • koszt zamortyzowany wykonania ciągu operacji słownikowych na tablicy z haszowaniem.
  • 27/29.11.2007 - słowniki:
    • slownik i operacje słownikowe;
    • drzewa BST (binarnych poszukiwań);
    • losowe drzewa BST;
    • drzewa AVL;
    • drzewa RBT (czerwono-czarne).
  • 4/6.12.2007 - słowniki zewnętrzne, drzewa pozycyjne:
    • drzewa SPLAY (samoorganizujące się);
    • drzewa pozycyjne RST, TRIE i PATRICIA;
    • B-drzewa i 2-3-4-drzewa.
  • 11/13.12.2007 - kolejki priorytetowe:
    • kolejka priorytetowa i operacje kolejkowe
    • listowa implementacja kolejek priorytetowych
    • kopiec i jego implementacja tablicowa
    • sortowanie z wykorzystaniem kolejki priorytetowej
    • [*] kolejki minimaksowe
  • 18/20.12.2007 - zbiory rozłączne:
    • złączalne kolejki priorytetowe
    • kopce dwumianowe
    • wyszukiwanie zbioru do którego należy element i sumowanie zbiorów rozłącznych
    • listowa reprezentacja zbiorów rozłącznych
    • łączenie według rozmiaru w listowej reprezentacji zbiorów rozłącznych
    • drzewiasta reprezentacja zbiorów rozłącznych
    • łączenie według rozmiaru i kompresja ścieżki podczas wyszukiwania w drzewiastej reprezentacji zbiorów rozłącznych
    • [*] zamortyzowana analiza ciągu operacji na zbiorach rozłącznych
  • 3/8.01.2008 - metoda "dziel i zwyciężaj" (divide and conquer):
    • metoda naiwna (brute-force) i jej zastosowanie w algorytmie szukania elementu w nieuporządkowanym zbiorze
    • rozwiązywanie problemów metodą "dziel i zwyciężaj"
    • własność podstruktury
    • uniwersalne twierdzenie o rekurencji
    • zastosowanie metody "dziel i zwyciężaj" do problemów porządkowych: jednoczesne znajdowanie minimum i maksimum, merge-sort, quick-sort i stooge-sort
    • mnożenie długich liczb
    • mnożenie macierzy metodą Strassena
    • obliczanie optymalnej wartości progowej (threshold)
    • metoda redukcji (reduction technique) i jej zastosowanie w algorytmie wyszukiwania binarnego w zbiorze uporządkowanym
  • 10/15.01.2008 - programowanie dynamiczne (dynamic programming):
    • rozwiązywanie problemów metodą programowania dynamicznego
    • własność optymalnej podstruktury
    • własność wspólnych podproblemów
    • metoda rekurencji ze spamiętywaniem (memoization)
    • zastosowanie metody programowania dynamicznego w obliczeniach: liczba Fibonacciego, symbol Newtona
    • stokrotki (przejście przez tablicę z wagami)
    • najdłuższy wspólny podciąg
    • [*] optymalne mnożenie macierzy
  • 17/22.01.2008 - strategia zachłana (greedy approach):
    • rozwiązywanie problemów metodą zachłanną
    • własność optymalnej podstruktury
    • własność wyboru zachłannego
    • wydawanie reszty
    • ciągły problem plecakowy
    • [*] kody Huffmana
  • 24.01.2008 - [*] klasy problemów P, NP i NPC:
    • algorytmy wielomianowe, ponadwielomianowe i pseudowielomianowe
    • klasyfikacja problemów ze względu na ich trudność w kategoriach złożoności czasowej
    • grupa problemów o nieustalonej trudności
    • wielomianowe redukcje problemów
    • problemy optymalizacyjne i odpowiadające im problemy decyzyjne
    • weryfikacja świadectwa w czasie wielomianowym
    • klasy problemów P i NP
    • klasa problemów NP-zupełnych
    • hipoteza P&neq;NPC
    • przynależność problemu do klasy problemów NPC
  • 29.01.2008 - [*] problemy NP-zupełne:
    • ...
repetytorium (studia dzienne)

Repetytorium prowadzi T.Jurdziński.

repetytorium (studia wieczorowe)

Repetytorium prowadzi A.Jeż.

powrót na początek strony

Listy zadań

ćwiczenia
  • lista nr 0 (rozruchowa): złożoność obliczeniowa (pdf/ps)
  • lista nr 1: efektywność algorytmów
    studia dzienne (pdf/ps)
    studia wieczorowe (pdf/ps)
  • lista nr 2: sortowanie
    studia dzienne (pdf/ps)
    studia wieczorowe (pdf/ps)
  • lista nr 3: scalanie, sortowanie przez scalanie
    studia dzienne (pdf/ps)
    studia wieczorowe (pdf/ps)
  • lista nr 4: podział, sortowanie szybkie
    studia dzienne (pdf/ps)
    studia wieczorowe (pdf/ps) - razem z listą 5
  • lista nr 5: wybór k-tego elementu
    studia dzienne (pdf/ps)
    studia wieczorowe (pdf/ps) - razem z listą 4
  • lista nr 6: koszt zamortyzowany
    studia dzienne (pdf/ps)
    studia wieczorowe (pdf/ps)
  • lista nr 7: elementarne struktury danych
    studia dzienne (pdf/ps)
    studia wieczorowe (pdf/ps)
  • lista nr 8: haszowanie
    studia dzienne (pdf/ps)
    studia wieczorowe (pdf/ps)
  • lista nr 9: słowniki i drzewa BST
    studia dzienne (pdf/ps)
    studia wieczorowe (pdf/ps)
  • lista nr 10: słowniki zewnętrzne i drzewa pozycyjne
    studia dzienne (pdf/ps)
    studia wieczorowe (pdf/ps)
  • lista nr 11: kolejki priorytetowe
    studia dzienne (pdf/ps)
    studia wieczorowe (pdf/ps)
  • lista nr 12: złączalne kolejki priorytetowe, zbiory rozłączne
    studia dzienne (pdf/ps)
    studia wieczorowe (pdf/ps)
  • lista nr 13: metoda "dziel i zwyciężaj"
    studia dzienne (pdf/ps)
    studia wieczorowe (pdf/ps)
  • lista nr 14: programowanie dynamiczne
    studia dzienne (pdf/ps)
    studia wieczorowe (pdf/ps)
  • lista nr 15: strategia zachłanna (pdf/ps)
laboratorium
  • zadanie nr 1: mnożenie długich liczb "po rosyjsku" (ps/pdf)
    termin nadsyłania rozwiązań: 25 listopada 2007 r.
  • zadanie nr 2: sortowanie leksykograficzne (ps/pdf)
    termin nadsyłania rozwiązań: 7 stycznia 2008 r.
  • zadanie nr 3: ciąg operacji słownikowych (ps/pdf)
    termin nadsyłania rozwiązań: 15 stycznia 2008 r.
  • zadanie nr 4: najdłuższy wspólny podciąg (ps/pdf)
    termin nadsyłania rozwiązań: 27 stycznia 2008 r.

powrót na początek strony

Rankingi

egzaminy
kolokwia
laboratoria
  • studia dzienne: ...
  • studia wieczorowe: ...
ćwiczenia

powrót na początek strony