algorytmy i struktury danych

Celem zajęć jest zapoznanie studentów z podstawowymi technikami konstrukcji i analizy algorytmów oraz doboru odpowiednich dla danego zagadnienia struktur danych.

wymagane przygotowanie
  • Umiejętność programowania w języku C/C++.
  • Podstawowa wiedza z matematyki dyskretnej.
  • Znajomość podstawowych struktur danych (tablice, listy, drzewa, grafy).
literatura

Literatura podstawowa:

  • T.H.Cormen, C.E.Leiserson, R.L.Rivest: Wprowadzenie do algorytmów. WNT, Warszawa 1997.
  • L.Banachowski, K.Diks, W.Rytter: Algorytmy i struktury danych. WNT, Warszawa 1996.
  • R.Neapolitan, K.Naimipour: Podstawy algorytmów z przykładami w C++. Wydawnictwo Helion, Gliwice 2004.

Literatura uzupełniająca:

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

powrót na początek strony

Ogłoszenia

20.02.2007 (egzamin)
Oceny z egzaminu (i ćwiczeń) będę wpisywał w czwartek (22 lutego) o 12:15. Można również zostawić indeks na półce koło portierni.
10.02.2007 (egzamin)
Osoby, które uzyskały zaliczenie z ćwiczeń i laboratorium w poprzednim roku (ewentualnie wcześniej i mają te oceny przepisane przez dziekana), i które przystępują do egzaminu bez zaliczonego co najmniej jednego kolokwium muszą uzyskać w sumie 39 punktów (do punktów z egzaminu należy dodać punkty za ocenę z ćwiczeń ×2 i za ocenę z laboratorium ×1).
6.02.2007 (egzamin)
Każdy, kto zaliczył część testową (minimum 8 punktów) ale nie zdał egzaminu, nie musi pisać testu w terminie poprawkowym bo już go zaliczył (punkty z części testowej zostaną automatycznie przepisane), ale może go poprawiać (również na mniejszą liczbę punktów, włącznie z "oblaniem").
28.01.2007 (egzamin)
Uwaga, abolicja! Wybrani studenci, którzy uzyskali wystarczająco dobre (chociaż nie na tyle aby się zakwalifikować od razu) wyniki z kolokwiów zostaną dopuszczeni do egraminu:
  • 186783 A.J.
  • 186833 M.S.
  • 186895 A.B.
  • 186838 M.S.
  • 186855 T.W.
  • 186910 Ł.S.
  • 186779 S.G.
Warunki abolicji zostaną im przedstawione indywidualnie.
28.01.2007 (egzamin)
Studenci, którzy uzyskali zaliczenie ćwiczeń i laboratorium z Algorytmów i Struktur Danych w ubiegłym roku lub wcześniej mogą przystąpić do egzaminu bez zaliczonych kolokwiów.
16.01.2007 (laboratorium)
Zostało opublikowane dodatkowe piąte zadanie na laboratorium. Termin jego realizacji upływa z dniem 28 stycznia 2007 r.
14.01.2007 (kolokwium)
Został zmianiony podany wcześniej termin trzeciego kolokwium. Na studiach dziennych odbędzie się ono 23 stycznia a na wieczorowych 24 stycznia w czasie repetytorium.
14.01.2007 (kolokwium)
Trzecie kolokwium obejmuje materiał dotyczący konstruowania algorytmów metodą "dziel i zwyciężaj", przy pomocy programowania dynamicznego i z wykorzystaniem techniki zachłannej.
11.01.2007 (egzamin)
Zostały ustalone terminy egzaminów dla studentów dziennych i wieczorowych.
Licencjat dzienny:
  • egzamin podstawowy rozpocznie się w czwartek 1 lutego 2007 r. o godzinie 10:00 w Sali Wielkiej Wschodniej nr 25;
  • egzamin poprawkowy rozpocznie się w poniedziałek 12 lutego 2007 r. o godzinie 10:00 w Sali Wielkiej Wschodniej nr 25.
Licencjat wieczorowy:
  • egzamin podstawowy rozpocznie się w czwartek 1 lutego 2007 r. o godzinie 16:15 w Sali Wielkiej Wschodniej nr 25;
  • egzamin poprawkowy rozpocznie się w poniedziałek 12 lutego 2007 r. o godzinie 16:15 w Sali Wielkiej Wschodniej nr 25.
Egzamin uzupełniający:
Dla tych osób, które z ważnych przyczyn (poświadczonych na przykład zwolnieniem lekarskim) nie będą obecne na egzaminie w terminie podstawowym będzie zorganizowany egzamin uzupełniający (jednocześnie dla studentów dziennych i wieczorowych), który rozpocznie się w piątek 9 lutego 2007 r. o godzinie 16:15 w sali 103.
Uwaga! Oprócz wyżej wymienionych nie będzie żadnych dodatkowych egzaminów.
11.01.2007 (kolokwium)
Zadanie pierwsze na ostatnim kolokwium było oceniane w skali 0-10 punktów i oceny te zostały potem podzielone przez 2 (przeskalowanie do 0-5 punktów za to zadanie).
3.01.2007 (laboratorium)
Zostało opublikowane czwarte zadanie na laboratorium. Termin jego realizacji upływa z dniem 21 stycznia 2007 r.
27.12.2006 (kolokwium)
Trzecie kolokwium odbędzie się w połowie stycznia w czasie repetytorium:
dla studentów dziennych w dniu 16 stycznia 2007 r,
dla studentów wieczorowych w dniu 17 stycznia 2007 r.
Kolokwium obejmuje materiał dotyczący konstruowania algorytmów metodą "dziel i zwyciężaj", przy pomocy programowania dynamicznego i z wykorzystaniem techniki zachłannej.
12.12.2006 (laboratorium)
Termin realizacji zadania trzeciego został przesunięty o tydzień i ostatecznie upływa z dniem 23 grudnia 2006 r.
6.12.2006 (kolokwium)
Kolejny raz (ale ostatni) został zmianiony podany wcześniej termin drugiego kolokwium na studiach dziennych. Odbędzie się ono w czasie repetytorium w dniu 19 grudnia 2006 r.
27.11.2006 (laboratorium)
Zostało opublikowane trzecie zadanie na laboratorium. Termin jego realizacji upływa z dniem 17 grudnia 2006 r.
24.11.2006 (kolokwium)
Uległ zmianie podany wcześniej termin drugiego kolokwium na studiach wieczorowych. Odbędzie się ono w czasie repetytorium w dniu 13 grudnia 2006 r.
10.11.2006 (laboratorium)
Zostało opublikowane drugie zadanie na laboratorium. Termin jego realizacji upływa z dniem 26 listopada 2006 r.
10.11.2006 (laboratorium)
W semestrze trzeba będzie zaprogramować 4 zadania laboratoryjne. Postanowiłem jednak umieścić 5 zadań, przez wzgląd na osoby, którym z jakichś powodów "powinęla się noga" na pierwszym zadaniu (bądź w przyszłości coś im się nie uda), aby mogły nadrobić zaległości punktowe.
6.11.2006 (laboratorium)
Na stronie Łukasza Piwowara znajdują się rankingi dotyczące pracowni. Znajdziecie tam także kilka cennych wskazówek dotyczących przesyłanych przez Was rozwiązań.
Co się tyczy programów to należy je wysyłać do sprawdzaczki poprzez przeglądarkę internetową (a nie e-mailem na moją zapchaną skrzynkę).
27.10.2006 (laboratorium)
Łukasz Piwowar dołoży wszelkich starań aby w najbliższy poniedziałek (30 listopada 2006r.) zaczęła działać sprawdzaczka. Gdyby sprawdzaczki nie udało się uruchomić do wtorku włącznie, to wtedy przedłużę termin nadsyłania rozwiązań.
18.10.2006 (kolokwium)
Pierwsze kolokwium odbędzie się na początku listopada w czasie repetytorium:
dla studentów dziennych w dniu 7 listopada 2006 r,
dla studentów wieczorowych w dniu 8 listopada 2006 r.
18.10.2006 (laboratorium)
Zostało opublikowane pierwsze zadanie na laboratorium. Termin jego realizacji upływa z dniem 5 listopada 2006 r.

powrót na początek strony

Terminarz

dzienne studia licencjackie

zajęcia
kolokwia
  • kolokwium 1: wtorek 7 listopada 2006 r, godz.14-16, s.119
  • kolokwium 2: wtorek 19 grudnia 2006 r, godz.14-16, s.119
  • kolokwium 3: wtorek 23 stycznia 2007 r, godz.14-16, s.119
egzaminy
  • podstawowy: czwartek 1 lutego 2007 r, godz.10-14, s.25
  • uzupełniający: piątek 9 lutego 2006 r, godz.16-20, s.103
  • poprawkowy: poniedziałek 12 lutego 2007 r, godz.10-14, s.25

wieczorowe studia licencjackie

zajęcia
  • wykład: poniedziałek 16-18 s.103 (P.Rzechonek)
  • repetytorium: środa 20-22 s.103 (A.Jeż)
  • ćwiczenia: poniedziałek 18-20 s.103 (P.Rzechonek)
kolokwia
  • kolokwium 1: wtorek 8 listopada 2006 r, godz.20-22 s.119
  • kolokwium 2: wtorek 13 grudnia 2006 r, godz.20-22 s.119
  • kolokwium 3: wtorek 24 stycznia 2007 r, godz.20-22 s.119
egzaminy
  • podstawowy: czwartek 1 lutego 2007 r, godz.16-20, s.25
  • uzupełniający: piątek 9 lutego 2006 r, godz.16-20, s.103
  • poprawkowy: poniedziałek 12 lutego 2007 r, godz.16-20, s.25

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);
  • prezentacja wybranych zagadnień obliczeniowych (algorytmy grafowe, algorytmy tekstowe, geometria obliczeniowa, zagadnienia numeryczne i teorioliczbowe).
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 3/4 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 3.3.4 i uruchamiane pod kontrolą systemu operacyjnego Linux.
  • 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 oraz co najmniej jedno kolokwium. 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 punktów 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
  • 2/5.10.2006 - złożoność obliczeniowa:
    • 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 przypadku najgorszym, najlepszym i średnim;
    • przykład: wyszukiwanie zadanej wartości w nieuporządkowanej tablicy.
  • 9/12.10.2006 - sortowanie, scalanie, podział (ps/pdf):
    • definicja podstawowych problemów porządkowych
    • elementarne metody sortowania
    • sortowanie Shella
    • algorytmy scalania (scalanie tradycyjne, scalanie w miejscu Kronroda)
    • sortowanie poprzez scalanie
    • algorytmy podziału (algorytm Lomuta, algorytm Sedgewicka)
    • sortowanie szybkie (przez podział)
  • 16/19.10.2006 - mediana, sortowanie zewnętrzne:
    • jednoczesne znajdowanie minimum i maksimum
    • algorytm Hoare'a
    • algorytm magicznych piątek
    • sortowanie zewnętrzne
  • 23/26.10.2006 - sortowanie liniowe, drzewa decyzyjne:
    • sortowanie w czasie liniowym (przez zliczanie, kubełkowe i pozycyjne)
    • dolna granica na problem sortowania (drzewa decyzyjne)
    • koszt zamortyzowany (metoda kosztu sumarycznego, księgowania i potencjału)
  • 30.10/2.11.2006 - tablice dynamiczne:
    • tablice dynamiczne i ich parametry
    • analiza kosztu zamortyzowanego ciągu operacji na tablicy dynamicznej
  • 6/9.11.2006 - haszowanie:
    • zbiór dynamiczny
    • slownik i operacje słownikowe
    • słownik statyczny
    • adresowanie bezpośrednie
    • tablice z haszowaniem
    • dobre funkcje haszujące i 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
  • 13/16.11.2006 - drzewa BST:
    • drzewa BST
    • losowe drzewa BST
    • drzewa SPLAY
  • 20/23.11.2006 - drzewa zrównoważone:
    • drzewa AVL
    • B-drzewa
    • drzewa pozycyjne RST i TRIE
  • 27/30.11.2006 - kolejki priorytetowe:
    • kolejka priorytetowa i operacje kolejkowe
    • listowa implementacja kolejek priorytetowych
    • kopiec i jego implementacja tablicowa
    • sortowanie z wykorzystaniem kolejki priorytetowej
    • kolejki minimaksowe
    • złączalne kolejki priorytetowe
    • kopce dwumianowe
  • 4/7.12.2006 - zbiory rozłączne:
    • 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
  • 11/14.12.2006 - metoda "dziel i zwyciężaj" (divide and conquer):
    • rozwiązywanie problemów metodą "dziel i zwyciężaj"
    • własność podstruktury
    • uniwersalne twierdzenie o rekurencji
    • metoda redukcji
    • zastosowanie metody "dziel i zwyciężaj" podczas sortowania: merge-sort, quick-sort i stooge-sort
    • mnożenie długich liczb
    • mnożenie macierzy metodą Strassena
    • znajdowanie pary najbliższych punktów na płaszczyźnie
  • 18/21.12.2006 - 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
    • zastosowanie metody programowania dynamicznego w obliczeniach: liczby Fibonacciego i symbole Newtona
    • stokrotki (przejście przez tablicę z wagami)
    • najdłuższy wspólny podciąg
    • optymalne mnożenie macierzy
    • optymalne drzewa BST
  • 4/8.01.2007 - strategia zachłana (greedy approach):
    • rozwiązywanie problemów metodą zachłanną
    • własność optymalnej podstruktury
    • własność wyboru zachłannego
    • wydawanie reszty
    • kody Huffmana
    • ciągły problem plecakowy
    • problem wyboru zajęć
  • 11/15.01.2007 - problemy NP-zupełne (NP-complete problems):
    • algorytmy wielomianowe, pseudowielomianowe i ponadwielomianowe
    • klasyfikacja problemów ze względu na ich trudność
    • wielomianowe redukcje
    • problemy optymalizacyjne i odpowiadające im problemy decyzyjne
    • algorytmy niedeterministyczne i weryfikacja w czasie wielomianowym
    • zbiory problemów P i NP
    • zbiór problemów NP-zupełnych
    • przynależność problemu do zbioru problemów NP-zupełnych
    • problem CIRCUIT-SAT
    • problem SAT
    • problem 3-CNF
  • 18/22.01.2007 - algorytmy aproksymacyjne (approximation algorithms):
    • aproksymowanie zadań optymalizacyjnych
    • współczynnik aproksymacji
    • problem pokrycia wierzchołkowego VERTEX-COVER
    • problem komiwojażera TSP z nierównością trójkąta
  • 25/29.01.2007 - algorytmy aproksymacyjne (approximation algorithms):
    • ogólny problem komiwojażera TSP
    • problem pokrycia zbioru SET-COVER
repetytorium (studia dzienne)

Repetytorium prowadzi P.Kanarek.

repetytorium (studia wieczorowe)

Repetytorium prowadzi A.Jeż.

powrót na początek strony

Listy zadań

ćwiczenia
  • lista rozruchowa: złożoność obliczeniowa
    studia dzienne i wieczorowe (ps/pdf)
  • lista nr 1: efektywność algorytmów
    studia dzienne (ps/pdf)
    studia wieczorowe (ps/pdf)
  • lista nr 2: sortowanie
    studia dzienne (ps/pdf)
    studia wieczorowe (ps/pdf)
  • lista nr 3: sortowanie i wybór
    studia dzienne (ps/pdf)
    studia wieczorowe (ps/pdf)
  • lista nr 4: sortowanie liniowe i drzewa decyzyjne
    studia dzienne (ps/pdf)
    studia wieczorowe (ps/pdf)
  • lista nr 5: koszt zamortyzowany i tablice dynamiczne
    studia dzienne (ps/pdf)
    studia wieczorowe (ps/pdf)
  • lista nr 6: tablice z haszowaniem
    studia dzienne (ps/pdf)
    studia wieczorowe (ps/pdf)
  • lista nr 7: drzewa BST
    studia dzienne (ps/pdf)
    studia wieczorowe (ps/pdf)
  • lista nr 8: drzewa zrównoważone
    studia dzienne (ps/pdf)
    studia wieczorowe (ps/pdf)
  • lista nr 9: kolejki priorytetowe
    studia dzienne (ps/pdf)
    studia wieczorowe (ps/pdf)
  • lista nr 10: zbiory rozłączne
    studia dzienne (ps/pdf)
    studia wieczorowe (ps/pdf)
  • lista nr 11: metoda "dziel i zwyciężaj"
    studia dzienne (ps/pdf)
    studia wieczorowe (ps/pdf)
  • lista nr 12: programowanie dynamiczne
    studia dzienne (ps/pdf)
    studia wieczorowe (ps/pdf)
  • lista nr 13: strategia zachłanna
    studia dzienne (ps/pdf)
    studia wieczorowe (ps/pdf)
  • lista zadań: problemy NP-zupełne (ps/pdf)
  • lista zadań: algorytmy aproksymacyjne (ps/pdf)
laboratorium
  • zadanie nr 1: mnożenie "po rosyjsku"
    studia dzienne i wieczorowe (ps/pdf)
    termin nadsyłania rozwiązań: 5 listopada 2006 r.
  • zadanie nr 2: sortowanie zewnętrzne
    studia dzienne i wieczorowe (ps/pdf)
    termin nadsyłania rozwiązań: 26 listopada 2006 r.
  • zadanie nr 3: drzewo AVL
    studia dzienne i wieczorowe (ps/pdf)
    termin nadsyłania rozwiązań: 23 grudnia 2006 r.
  • zadanie nr 4: najdłuższy wspólny podciąg
    studia dzienne i wieczorowe (ps/pdf)
    termin nadsyłania rozwiązań: 21 stycznia 2007 r.
  • zadanie nr 5: odległość edycyjna
    studia dzienne i wieczorowe (ps/pdf)
    termin nadsyłania rozwiązań: 28 stycznia 2007 r.

powrót na początek strony

Rankingi

egzaminy
kolokwia
laboratoria
ćwiczenia

powrót na początek strony