ogloszenia | terminy | przygotowanie | literatura | opis zajęć | oceny | rankingi
zadania na ćwiczenia | programy na laboratorium | zagadnienia na repetytorium | notatki do wykładów

Ogłoszenia

Dzisiaj jest piątek, 26 kwietnia 2024 roku.
Godzina wejścia na tę stronę to 12:26.
Jesteś 10467 osobą odwiedzającą tę stronę od 22 lutego 2006 roku, a także:
      196 osobą w bieżącym roku,
      34 osobą w obecnym miesiącu,
      1 osobą w dzisiejszym dniu.

  • (27 lutego 2006) Są już ostateczne wyniki z egzaminu poprawkowego.
    Oceny do indeksów będę wpisywał jutro (środa 28 lutego 2006) o godzinie 11:15-12:00.
  • (22 lutego 2006) Zostały sprawdzone i ocenione pytania z części testowej egzaminu poprawkowego - wyniki są trochę lepsze niż w terminie podstawowym.
  • (10 lutego 2006) Przypominam: egzamin poprawkowy z Algorytmów i Struktur Danych rozpocznie się w sobotę 18 lutego 2006 o godzinie 9:00 w sali 31 (przewidywany czas zakończenia egzaminu to godzina 14:00).
    Osoby, które zaliczyły część testową na egzaminie w terminie podstawowym nie muszą pisać jej w terminie poprawkowym (chociaż mogą), a zdobyte wtedy punkty zostaną im przepisane (część zadaniowa rozpocznie się około 10:30).
  • (10 lutego 2006) Studenci i studentka, którzy zdali egzamin: proszę dostarczyć mi indeksy w celu uzyskania zasłużonych wpisów (można poprzez półkę obok dziekanatu).
  • (10 lutego 2006) Ostateczne wyniki z egzaminu podstawowego są już zamieszczone w rankingach. Rezulaty raczej mizerne: 35% osób przeszło przez test, a 11% ostatecznie zdało egzamin.
    Uwaga: obniżyłem kryteria dotyczące ocen końcowych (jednak progi zaliczeniowe na samym egzaminie pozostaną bez zmian).
  • (6 lutego 2006) Zostały sprawdzone i ocenione pytania z części testowej egzaminu podstawowego: 12 osób zaliczyło ten etap.
    Chciałbym wszystkich zainteresowanych zaprosić na spotkanie poświęcone omówieniu zadań z tego egzaminu w czwartek 9 lutego 2006 o 14:00 do sali 33.
  • (23 stycznia 2006) Została nieznacznie zmodyfikowana treść zadania 6 z listy 15. Do zadania tego dopisałem też wskazówkę.
  • (19 stycznia 2006) Egzamin podstawowy z Algorytmów i Struktur Danych rozpocznie się w czwartek 2 lutego 2006 o godzinie 9:00 w sali 31 (przewidywany czas zakończenia egzaminu to godzina 14:00). Dla osób, które z ważnych przyczyn (choroba, zdarzenie losowe, itp) nie będą mogły przystąpić do egzaminu 2 lutego, będzie zorganizowany egzamin uzupełniający w terminie 9 lutego 2006 (proszę mnie wcześniej powiadomić o przystąpieniu do egzaminu w trybie uzupełniającym oraz o przyczynach nieobecności w terminie podstawowym).
    Natomiast termin egzaminu poprawkowego musiał zostać zmieniony, więc odbędzie się on w sobotę 18 lutego 2006 (rozpoczęcie o godzinie 9:00 w sali 31).
  • (10 stycznia 2006) Zostały opublikowane tematy czwartego projektu programistycznego na laboratorium. Proszę zapoznać się z treściami zadań na pracownię. Proszę również wyliczyć sobie numer przypisanego Wam zadania na podstawie numeru indeksu.
    Wyniki z trzeciego projektu programistycznego powinny pojawić się jeszcze przed sesją.
  • (28 grudnia 2005) Trzecie kolokwium z Algorytmów i Struktur Danych odbędzie się w środę 18 stycznia 2005 roku w godzinach 12-14 w salach 40 i 34 (zamiast repetytorium).
  • (22 grudnia 2005) Wyniki z drugiego projektu programistycznego niestety nie pojawią się przed Świętami (przyczyny techniczne).
    Po Nowym Roku czeka nas jeszcze sporo pracy, więc proszę wykorzystać obecną przerwę na odpoczynek i spotkania z rodziną i przyjaciółmi. Życzę wszystkim radosnych i spokojnych świąt i powodzenia w nadchodzącym 2006 roku.
  • (11 grudnia 2005) Zostały opublikowane tematy trzeciego projektu programistycznego na laboratorium. Proszę zapoznać się z treściami zadań na pracownię. Proszę również wyliczyć sobie numer przypisanego Wam zadania na podstawie numeru indeksu.
    Wyniki z drugiego projektu programistycznego być może pojawią się jeszcze przed Świętami.
  • (2 grudnia 2005) Drugie kolokwium z Algorytmów i Struktur Danych odbędzie się w środę 21 grudnia 2005 roku w godzinach 12-14 w salach 40 i 34 (zamiast repetytorium).
  • (28 listopada 2005) Lista zadań nr 9 została opublikowana dość późno, ale za to zadania są łatwe i wysoko punktowane.
  • (18 listopada 2005) Lista zadań nr 8 została połączona z listą nr 7 (dopisałem kilka nowych zadań). Na ćwiczeniach w poszczególnych grupach należy deklarować zadania nie zrobione na ostatnich zajęciach i nowe.
  • (10 listopada 2005) Wyniki z pierwszego projektu programistycznego na laboratorium znajdują się już na stronie Jana Otopa.
  • (7 listopada 2005) Zostały opublikowane tematy drugiego projektu programistycznego na laboratorium. Proszę zapoznać się z treściami zadań na pracownię. Proszę również wyliczyć sobie numer przypisanego Wam zadania na podstawie numeru indeksu.
  • (5 listopada 2005) Został uaktualniony ranking w mojej grupie. Ja się spodziewałem takich wyników, a Wy?
  • (3 listopada 2005) Termin nadsyłania zadań na laboratorium (zadania, czyli pliki źródłowe, proszę wysyłać pocztą elektroniczną do Jana Otopa) został przedłużony o jeszcze jeden dzień, czyli do piątku 4 listopada 2005 roku do godziny 23:59.
  • (29 października 2005) Pierwsze kolokwium z Algorytmów i Struktur Danych odbędzie się w środę 16 litopada 2005 roku w godzinach 12-14 w salach 40 i 34 (zamiast repetytorium).
  • (10 października 2005) Został zmieniony termin laboratorium u Jana Otopa na czwartek 13-14. Wiem, że termin ten może kolidować z niektórymi Waszymi zajęciami, ale pracownia i tak jest wirtualna. Programy należy wysyłać pocztą elektroniczną do Jana Otopa (on będzie sprawdzał programy).
    Gdyby trzeba było się skonsultować w sprawie dotyczącej zadania na laboratorium (ze mną albo z Janem Otopem), to można się będzie umówić w dowolnym innym terminie (pasującym obu osobom: studentowi/studentce i prowadzącemu).
  • (10 października 2005) Został opublikowany temat pierwszego projektu programistycznego na laboratorium. Proszę zapoznać się z treścią zadania na pracownię. Zadanie jest wspólne dla wszystkich uczestników zajęć.
    Osoby zainteresowane zaliczeniem pracowni, których nie ma na liście w~systemie zapisów, proszę o wyjaśnienie tej sprawy w dziekanacie.

Terminy

Zajęcia

  • wykład: wtorek 14-17 s.40 (P.Rzechonek)
  • repetytorium: środa 12-14 s.32 (T.Jurdzinski)
  • laboratorium:
    wtorek 17-18 (P.Rzechonek)
    czwartek 13-14 (J.Otop)
  • ćwiczenia:
    środa 10-12 s.33 (T.Jurdzinski)
    czwartek 8-10 s.34 (P.Kanarek)
    czwartek 12-14 s.33 (P.Rzechonek)

Kolokwia

  • kolokwium 1: początek 16 listopada 2005, środa 12-14 s.40+34
  • kolokwium 2: początek 21 grudnia 2005, środa 12-14 s.40+34
  • kolokwium 3: początek 18 stycznia 2006, środa 12-14 s.40+34

Egzaminy

  • egzamin podstawowy: 2 lutego 2006, czwartek 9-14 s.31
  • egzamin uzupełniający: 9 lutego 2006, czwartek 9-14 s.31
  • egzamin poprawkowy: 18 lutego 2006, sobota 9-14 s.31

Wymagane przygotowanie studentów

  • Znajomość języka programowania C/C++.
  • Znajomość podstawowych struktur danych (tablice, listy, drzewa, grafy), operacji na tych strukturach oraz ich implementacji w języku C/C++ (z wykorzystaniem rekurencji).

Literatura

Literatura podstawowa

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

Literatura uzupełniająca

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

Opis zajęć

Wykład

Tematyka wykładu będzie obejmowała następujące zagadnienia z dziedziny algorytmiki:
  • metody konstruowania i analizy algorytmów;
  • dowodzenie dolnych granic dla podstawowych problemów obliczeniowych;
  • selekcja, sortowanie, scalanie wybór;
  • zaawansowane struktury danych (kolejki priorytetowe, słowniki dynamiczne, słowniki statyczne, zbiory rozłączne);
  • prezentacja wybranych zagadnień obliczeniowych (algorytmy grafowe, algorytmy tekstowe, geometria obliczeniowa, obliczenia numeryczne i teorioliczbowe).
Uwaga: Informacja o ostatecznym terminie egzaminów będzie podana 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 algorytmy pod kątem ich złożoności obliczeniowej;
  • analizowane struktury danych i operacje na tych strukturach;
  • prezentowane rozwiązania wybranych zadań.
Uwaga: W czasie repetytorium będą zorganizowane trzy kolokwia. Z każdego kolokwium będzie można dostać do 8 punktów, czyli łącznie 24 punkty. Informacja o terminie kolokwium będzie podana na wykładzie (i na tej stronie) co najmniej tydzień wcześniej.

Laboratorium

Laboratorium jest praktycznym wykorzystaniem wiedzy zdobytej na wykładzie. Ćwiczenia laboratoryjne będą polegały na pisaniu programów rozwiązujących określone problemy, implementowaniu zaawansowanych struktur danych, testowaniu ich efektywności oraz na sporządzaniu sprawozdań z przeprowadzonych eksperymentów.

Uwaga: Za zaliczenie laboratorium będzie można dostać od 4 (za ocenę dostateczną) do 8 punktów (za ocenę bardzo dobrą).

Ć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: Za zaliczenie ćwiczeń będzie można dostać od 8 (za ocenę dostateczną) do 16 punktów (za ocenę bardzo dobrą).

Oceny końcowe

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 (12 prostych pytań) i zadaniowej (4 zadania). Za udzielenie poprawnych odpowiedzi do wszystkich pytań z części testowej będzie można dostać 12 punktów, a za poprawne rozwiązanie wszystkich zadań z części zadaniowej 20 punktów (łącznie 32 punkty). Egzamin uznaje się za zdany po zdobyciu łacznie z obu części co najmniej 12 punktów, w tym minimum 6 za test.

Ocena z egzaminu

Na pozytywną ocenę końcową mogą liczyć tylko te osoby, które zdały egzamin. Ocena końcowa z przedmiotu 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
<26 2
27... 3
36... 3+
45... 4
54... 4+
63...80 5

Kolokwia

Informacje ogólne

W czasie semestru odbędą się trzy kolokwia. Udział studentów w kolokwiach jest obowiązkowy. Punkty uzyskane z kolokwiów wliczają się do punktacji z egzaminu.

Szczegóły dotyczące kolokwium

Każde kolokwium będzie się składało z dwóch części: testowej (6 prostych pytań) i zadaniowej (2 zadania). Za udzielenie poprawnych odpowiedzi do wszystkich pytań z części testowej będzie można dostać 3 punkty, a za poprawne rozwiązanie obu zadań z części zadaniowej 5 punktów (łącznie 8 punktów).

Oceny z kolokwiów

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

Zasady zaliczania laboratorium

Informacje ogólne

W ramach pracowni będą do napisania cztery programy, związane tematycznie z omawianymi na wykładzie/repetytorium technikami konstrukcji algorytmów, strukturami danych i wybranymi problemami obliczeniowymi. Tematy projektów programistycznych będą podzielone tematycznie na cztery listy z zadaniami. Z każdą listą będzie związany termin jej realizacji. Projekty programistyczne zostaną przydzielone w sposób losowy każdemu studentowi/studentce - po jednym zadaniu z każdej listy. Informacja o przydziale zadań podana będzie na wykładzie (i na tej stronie) co najmniej trzy tygodnie wcześniej.

Szczegóły dotyczące programów

  • Programy należy oddawać w postaci źródłowej przed wyznaczonym terminem jego realizacji. Należy to uczynić za pośrednictwem poczty elektronicznej, wysyłając pliki źródłowe do Jana Otopa na adres jotop@ii.uni.wroc.pl z dopiskiem w tytule ASD labolatorium X zadanie Y.
  • 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.
  • 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 (jeśli w ogóle jest to potrzebne w ostatecznej wersji programu).
  • 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źć sprawozdanie (w postaci komentarza), w którym, oprócz imienia, nazwiska i numeru indeksu autora, znajdzie się wyczerpująca odpowiedź na postawione pytania.
  • Programy mają być napisane z myślą o efektywności (powinny być testowane na dużych danych).
  • Za każdy poprawny program będzie można dostać do 8 puntów.

Ocena z laboratorium

W semestrze będzie można zdobyć łącznie 32 punkty. Ocena na zaliczenie laboratorium będzie następująco zależeć od zdobytych na zajęciach punktów:
punkty ocena
<13 2
13... 3
16... 3+
19... 4
22... 4+
25...32 5

Zasady zaliczania ćwiczeń

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, 3 lub 4) zależna od stopnia ich trudności. Przed rozpoczęciem zajęć każdy student/studentka 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 zrobione przy tablicy i 3/4 za zadania niezaprezentowane. Dodatkowe punkty otrzymują studenci/studentki 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, opisane są poniżej). Prezentacje rozwiązań mają być dobrze przygotowane, w przeciwnym razie student/studentka 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 (za 1 lub 2 punkty) albo dowolne zadanie z listy wcześniejszej (zadania 4-punktowe tylko w przypadku, gdy zostały rozwiązane przy tablicy). 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ć 12 punktów.
  • Za nieusprawiedliwioną nieobecność student/studentka otrzymuje minus połowę punktów możliwych do uzyskania za pełną deklarację zadań z bieżącej listy.
  • Za niepowodzenie przy tablicy (student/studentka miał dobry pomysł na rozwiązanie zadania, ale pomylił sie w obliczeniach lub zrobił inny drobny błąd) będzie studentowi/studentce skreślone dane zadanie z deklaracji.
  • Wykryte oszustwo, czyli nieznajomość rozwiązania pomimo deklaracji, będzie karane:
    • przy pierwszym wykroczeniu: -6 punktów karnych i skreślenie tego zadania z bieżącej deklaracji;
    • przy drugim wykroczeniu: -12 punktów karnych i skreślenie wszystkich nie zrobionych jeszcze zadań z bieżącej deklaracji;
    • przy trzecim i kolejnym wykroczeniu: -18 punktów karnych i skreśleniem nie zrobionych jeszcze 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. Ocena na zaliczenie ćwiczeń będzie następująco zależeć od zdobytych na zajęciach 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

Rankingi

Wyniki z ćwiczeń:

Wyniki z laboratoriów:

Wyniki z kolokwiów:

Wyniki z egzaminów:

Zadania na ćwiczenia

  • Lista 1: (ps / pdf) szacowanie złożoności obliczeniowej
  • Lista 2: (ps / pdf) złożoność obliczeniowa algorytmów
  • Lista 3: (ps / pdf) metoda redukcji
  • Lista 4: (ps / pdf) metoda "dziel i zwyciężaj"
  • Lista 5: (ps / pdf) programowanie dynamiczne
  • Lista 6: (ps / pdf) programowanie dynamiczne
  • Lista 7, 8: (ps / pdf) technika zachłanna
  • Lista 9: (ps / pdf) podział, scalanie, wybór
  • Lista 10: (ps / pdf) sortowanie
  • Lista 11: (ps / pdf) kolejki priorytetowe
  • Lista 12: (ps / pdf) złączalne kolejki priorytetowe
  • Lista 13: (ps / pdf) tablice dynamiczne i zbiory rozłączne
  • Lista 14: (ps / pdf) drzewa BST
  • Lista 15: (ps / pdf) drzewa zrównoważone

Programy na laboratorium

  • Lista 1 (3 lisopada 2005): (ps / pdf) grafy.
    Na liście jest jedno zadanie, wspólne dla wszytkich studentów.
  • Lista 2 (1 grudnia 2005): (ps / pdf) techniki programowania.
    Na liście są trzy zadania ponumerowane 1, 2 i 3 (=0). Zadania te są przypisane do studentów na podstawie numerów posiadanych przez nich indeksów: reszta z dzielenia numeru indeksu przez 3 oznacza, że studentowi przypisano zadanie o tym właśnie numerze. Jeśli numer indeksu dzieli się bez reszty, to taka osoba programuje zadanie 3-cie, jeśli reszta z dzielenia wynosi 1, to osoba taka programuje zadanie 1-sze, a jeśli wynosi 2, to zadanie 2-gie.
  • Lista 3 (5 stycznia 2006): (ps / pdf) sortowanie.
    Na liście są dwa zadania ponumerowane 1 i 2 (=0). Zadania te są przypisane do studentów na podstawie numerów posiadanych przez nich indeksów: reszta z dzielenia numeru indeksu przez 2 oznacza, że studentowi przypisano zadanie o tym właśnie numerze. Jeśli numer indeksu jest parzysty, to taka osoba programuje zadanie 2-gie, a jeśli jest nieparzysty, to zadanie 1-sze.
  • Lista 4 (26 stycznia 2006): (ps / pdf) struktury danych.
    Na liście są trzy zadania ponumerowane 1, 2 i 3 (=0). Zadania te są przypisane do studentów na podstawie numerów posiadanych przez nich indeksów: reszta z dzielenia numeru indeksu przez 3 oznacza, że studentowi przypisano zadanie o tym właśnie numerze. Jeśli numer indeksu dzieli się bez reszty, to taka osoba programuje zadanie 3-cie, jeśli reszta z dzielenia wynosi 1, to osoba taka programuje zadanie 1-sze, a jeśli wynosi 2, to zadanie 2-gie.

Zagadnienia na repetytorium

  • Lista 1: (ps / pdf) szacowanie złożoności obliczeniowej.
  • Lista 2: (ps / pdf) złożoność obliczeniowa algorytmów.
  • Lista 3: (ps / pdf) metoda redukcji.
  • Lista 4: (ps / pdf) metoda "dziel i zwyciężaj".
  • Lista 5: (ps / pdf) programowanie dynamiczne.
  • Lista 6: (ps / pdf) programowanie dynamiczne.
  • Kolokwium 1 (16.11.2005): techniki rozwiązywania problemów (metoda redukcji, metoda "dziel i zwyciężaj", programowanie dynamiczne, technika zachłanna).
  • Lista 7: (ps / pdf) technika zachłanna.
  • Kolokwium 1 (30.11.2005): omówienie zadań.
  • Kolokwium 2 (21.12.2005): porządkowanie danych (sortowanie, scalanie, podział, wyszukiwanie).
  • Kolokwium 2 (4.01.2006): omówienie zadań.
  • Kolokwium 3 (18.01.2006): struktury danych (kolejki priorytetowe, złączalne kolejki priorytetowe, zbiory rozłączne, słowniki, słowniki statyczne).
  • Kolokwium 3 (25.01.2006): omówienie zadań.

Notatki do wykładów

  • Wykład 1 (4.10.2005): problemy, algorytmy, programy i ich złożoność.
    • Problem - zadanie; algorytm - rozwiązanie; program - implementacja (problem sortowania i algorytm bąbelkowy).
    • Złożoność obliczeniowa (czasowa, pamięciowa).
    • Złożoność optymistyczna, pesymistyczna i średnia/oczekiwana (znajdowanie pozycji w tablicy nieuporządkowanej z elementem o zadanej wartości).
    • Ograniczenie dolne na złożonośc problemu (mnożenie macierzy) i górne na złożoność algorytmu (mnożenie długich liczb "po rosyjsku").
    • Wydajność algorytmów (obliczanie liczb Fibonacciego rekurencyjnie, iteracyjnie i metodą macierzową).
  • Wykład 2 (11.10.2005): metoda redukcji.
    • Metoda naiwna (przeglądanie całego zbioru możliwych rozwiązań).
    • Podstawy strategii redukcji (własność redukcji do podproblemu).
    • Znajdowanie maksimum w nieuporządkowanej tablicy.
    • Dolna granica na złożonośc czasową problem znajdowania maksimum w nieuporządkowanej tablicy (graf relacji).
    • Wyszukiwanie binarne w uporządkowanej tablicy.
    • Statystyki pozycyjne (algorytm Hoare'a).
  • Wykład 3 (18.10.2005): metoda "dziel i zwyciężaj".
    • Podstawy strategii "dziel i zwyciężaj" (własność niezależnych podproblemów).
    • Uniwersalne twierdzenie o rekurencji.
    • Jednoczesne znajdowanie minimum i maksimum.
    • Dolna granica na złożonośc czasową problemu jednoczesnego znajdowania minimum i maksimum (gra z adwersarzem).
    • Mnożenie długich liczb.
  • Wykład 4 (25.10.2005): programowanie dynamiczne.
    • Podstawy strategii dynamicznej (własność optymalnych podstruktur i własność wspólnych podproblemów).
    • Obliczanie współczynnika dwumianowego.
    • Najdłuższy wspólny podciąg (LCS).
    • Optymalne mnożenie macierzy (MCM).
  • Wykład 5 (8.11.2005): technika zachłanna.
    • Podstawy strategii zachłannej (własność optymalnej podstruktury i własność wyboru zachłannego).
    • Problem wydawania reszty.
    • Dyskretny i ciągły problem plecakowy.
    • Binarne kody prefiksowe i kodowanie Huffmana.
  • Wykład 6 (22.11.2005): scalanie, selekcja, wybór.
    • ...
  • Wykład 7 (29.11.2005): sortowanie.
    • Dolna granica na złożoność czasową problemu sortowania, w którym korzysta się tylko z porównywania elementów (technika z drzewami decyzyjnymi).
    • Charakterystyka danych podlegających sortowaniu (krótkie liczby, duże rekordy z polem kluczowym), miejsca ich przechowywania (tablica w wewnętrznej pamięci opereacyjnej, plik w zewnętrznej pamięci dyskowej) i samych algorytmów sortujących (sortowanie w miejscu, sortowanie stabilne).
    • Metody sortowania zmniejszające w każdym kroku o 1 liczbę inwersji w sortowanym ciągu: sortowanie bąbelkowe (bubble-sort), sortowanie koktajlowe (cocktail-sort / shaker-sort / ripple-sort / shuttle-sort), sortowanie przez wstawianie (insertion-sort).
    • Sortowanie przez wybór (selection-sort).
    • Sortowanie szybkie (qiuck-sort).
    • Sortowanie przez scalanie (merge-sort).
    • Sortowanie zewnętrzne z trzema plikami (external-sort).
    • Szybkie metody sortowania wykorzystujące informacje o wartościach sortowanych elementów: sortowanie przez zliczanie (counting-sort), sortowanie kubełkowe (bucket-sort), sortowanie pozycyjne/leksykograficzne (radix-sort).
  • Wykład 8 (6.12.2005): kolejki priorytetowe.
    • Kopiec.
    • Sortowanie kopcowe (heap-sort).
  • Wykład 9 (13.12.2005): złączalne kolejki priorytetowe.
    • Drzewa dwumianowe.
    • Kopiec dwumianowy (binomial-heap).
    • Liczenie kosztu zamortyzowanego (metody sumowania, księgowania i potencjału).
  • Wykład 10 (20.12.2005): zbiory rozłączne.
    • Tablice dynamiczne.
    • Zbiory rozłączne i problem Union-Find (reprezentacja listowa i drzewiasta zbiorów rozłącznych).
  • Wykład 11 (3.01.2006): słowniki i BST.
    • Drzewa BST.
    • Losowe drzewa BST.
  • Wykład 12 (10.01.2006): zrównoważone BST.
    • Drzewa AVL.
    • Drzewa R-B.
    • Drzewa SPLAY.
  • Wykład 13 (17.01.2006): słowniki zewnętrzne.
    • B-drzewa i 2-3-4-drzewa.
    • Pozycyjne drzewa poszukiwań: RST, TRIE, PATRICIA.
  • Wykład 14 (24.01.2006): haszowanie.
    • Adresowanie bezpośrednie.
    • Tablice z haszowaniem.
    • Funkcje haszujące.
    • Haszowanie uniwersalne.
  • Wykład 15 (31.01.2006): haszowanie.
    • Rozwiązywanie kolizji metodą łańcuchową.
    • Adresowanie otwarte i rozwiązywanie kolizji metodami: liniową, kwadratową, podwójnego haszowania.
    • Analiza oczekiwanych czasów działania operacji słownikowych na tablicy z haszowaniem.