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.
Zakres materiału
  • 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.

Terminarz

Zajęcia
  • wykład: wtorek 16-18 s.139
  • ćwiczenia+laboratorium: wtorek 18-20 s.103
Laboratoria
  • termin oddania zadania 1: niedziela 5 kwietnia 2009
  • termin oddania zadania 2: niedziela 3 maja 2009
  • termin oddania zadania 3: niedziela 31 maja 2009
  • termin oddania zadania 4: niedziela 21 czerwca 2009
Egzaminy
  • egzamin podstawowy (tercja 1): piątek 17 kwietnia 2009, godz.17-19 (semestr letni)
  • egzamin podstawowy (tercja 2): piątek 22 maja 2009, godz.17-19 (semestr letni)
  • egzamin podstawowy (tercja 3): piątek 19 czerwca 2009, godz.17-19 (semestr letni)
  • egzamin poprawkowy: wtorek 30 czerwca 2009, godz.17-21 (sesja egzaminacyjna)

Organizacja 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);
  • klasa zadań trudnych należących do zbioru NP (zadania decyzyjne i optymalizacyjne, klasy problemów P i NP, weryfikacja w czasie wielomianowym, redukowalność problemów, problemy NP-zupełne).

W trakcie semestru będą przeprowadzone trzy egzaminy częściowe sprawdzające wiadomości studentów z poszczególnych partii materiału. W czasie sesji zostanie jeszcze przeprowadzony egzamin uzupełniający i poprawkowy, sprawdzający wszystkie wiadomości przedstawione na wykładzie.

Uwaga! Punkty zdobyte z zaliczonych egzaminów częściowych będą wliczane do punktacji końcowej z egzaminu. Informacja o terminach egzaminów będzie ogłoszana na wykładzie (i na tej stronie) już na początku semestru.

Ćwiczenia + laboratorium

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

W ramach zajęć ćwiczeniowych będzie się dobywać wirtualne 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 i na testowaniu ich efektywności.

Uwaga! Punkty z laboratorium będą miały wpływ na ocenę z ćwiczeń. Nie zaliczone laboratorium implikuje niezaliczenie ćwiczeń. Ocena z ćwiczeń będzie miała wpływ na dodatkowe punkty wliczane do punktacji z egzaminu.

Zasady zaliczeń

Ćwiczenia + laboratorium
informacje ogólne

Na każde ćwiczenia będzie przygotowana osobna lista z zadaniami związana tematycznie z zagadnieniami omawianymi na wykładzie. 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 wypełnić i złożyć deklarację, które zadania z bieżącej listy rozwiązał i potrafi zaprezentować przy tablicy. Na podstawie deklaracji będę arbitralnie wyznaczał osobę prezentującą rozwiązanie zadania przy tablicy. Listy zadań będą przygotowywane na kilka dni przed zajęciami i udostępniane w internecie (na tej stronie).

W ramach wirtualnych laboratoriów trzeba będzie napisać w semestrze 4 programy, związane tematycznie z omawianymi na wykładzie 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ęć ćwiczeniowych
  • Po zakończeniu zajęć każdy student/studentka otrzymuje punkty za zadeklarowane zadania: w całości za zadania rozwiązane przy tablicy i połowę 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 wszystkich ćwiczeniach będą przeprowadzane 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.
  • Po każdych ćwiczeniach można wybrać sobie jedno zadanie z tych nierozwiązanych na zajęciach i wysłać mi jego opracowanie do końca tygodnia, w którym dana lista obowiązywała. Za opracowanie zadania będzie można otrzymać liczbę punktów przypisaną zadaniu.
  • Za nieusprawiedliwioną nieobecność student otrzymuje -5 punktów.
  • 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 skreśleniem zadania i -10 punktami.
szczegóły dotyczące zadań laboratoryjnych
  • 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 g++ 4.1.2 i uruchamiane pod kontrolą systemu operacyjnego Linux Ubuntu 7.04 na moim komputerze.
  • Programy, czyli pliki z kodem źródłowym, należy mi dostarczać tylko za pośrednictwem poczty eletronicznej przed upływem wyznaczonego terminu.
  • 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.
  • Każdy program zostanie uruchomiony dla kilku lub kilkunasu różnych zestawów danych. Oceniany program otrzyma liczbę punktów zależną od liczby poprawnie wykonanych testów. Dodatkowe punkty będą przyznawane za styl programowania: czytelność kodu, logiczny podział na procedury, itp.
  • 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ą zatrzymywane przez skrypt testujący.
  • Programy mają być napisane w sposób staranny i czytelny. Na początku powinien się znaleźć komentarz z imieniem i nazwiskiem oraz numerem indeksu autora; należy też krótko opisać zastosowany algorytm i wykorzystane struktury danych. 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 ćwiczeń i laboratorium

Na każdych zajęciach ćwiczeniowych będzie można zdobywać punkty za:

  • kartkówkę,
  • zadeklarowane zadania,
  • prezentację zadań przy tablicy,
  • pisemne opracowanie zadania nierozwiązanego na ćwiczeniach.

Za każde poprawnie zrobione zadanie laboratoryjne będzie można dostać do 20 punktów. Warunkiem koniecznym uzyskania zaliczenia z tego przedmiotu będzie oddanie co najmniej dwóch dobrze działających programów (ocenionych na co najmniej 10 punktów).

Oznaczmy przez S sumę punktów możliwych do uzyskania za pełne deklaracje zadań z wszystkich list plus 80 możliwych do zdobycia punktów za programy. Ocena zaliczeniowa zajęć 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ń i laboratorium będzie przeliczana na dodatkowe punkty wliczane do punktacji z egzaminu: liczba punktów z tych zajęc to trzykrotna wartość oceny minus 3 punkty (przyznana liczba punktów wyniesie więc 6...12).

Egzaminy
informacje ogólne

W ogólnym przypadku student ma prawo przystąpić do egzaminu dwukrotnie: pierwszy raz w trakcie semestru i sesji egzaminacyjnej (egzaminy częściowe i egzamin uzupełniający) i drugi raz w sesji poprawkowej (egzamin poprawkowy) gdy studentowi nie powiodło za pierwszym razem.

W trakcie semestru odbędą się 3 egzaminy częściowe. Punkty zdobyte na zaliczonych egzaminach częściowych będą wchodzić w skład punktacji końcowej z egzaminu. Udział studentów w tych egzaminach jest obowiązkowy.

W czasie sesji zostanie przeprowadzony egzamin uzupełniający dla osób, które z ważnych i udokumentowanych przyczyn nie mogły być obecne na którymś z egzaminów częściowych. Do egzaminu tego mogą przystąpić tylko te osoby, które mają zaliczone ćwiczenia + laboratorium. Egzamin uzupełniający będzie sprawdzał wszystkie wiadomości przedstawione na wykładzie.

Dla osób, którym się nie powiodło za pierwszym razem, będzie zorganizowany egzamin poprawkowy w sesji poprawkowej. Do egzaminu tego mogą przystąpić tylko te osoby, które mają zaliczone ćwiczenia + laboratorium. Egzamin poprawkowy będzie sprawdzał wszystkie wiadomości przedstawione na wykładzie.

szczegóły dotyczące egzaminów częściowych

Każde egzamin częściowy będzie się składał 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ć 6 punktów, a za poprawne rozwiązanie obu zadań z części zadaniowej 10 punktów (łącznie 16 punktów). Egzamin częściowy będzie zaliczony, gdy student otrzyma co najmniej 2 punkty z części testowej oraz co najmniej 6 punktów z obu części.

szczegóły dotyczące egzaminu uzupełniającego i poprawkowego

Egzamin będzie się składał z dwóch części: testowej (9 prostych pytań) i zadaniowej (3 zadania). Za udzielenie poprawnych odpowiedzi do wszystkich pytań z części testowej będzie można dostać 18 punktów, a za poprawne rozwiązanie trzech zadań z części zadaniowej 30 punktów (łącznie 48 punktów). Egzamin jest zdany, jeśli student otrzyma co najmniej 6 punktów z części testowej oraz co najmniej 18 punktów z obu części.

oceny z egzaminu

Ocena końcowa z egzaminu będzie wyliczona na podstawie oceny z ćwiczeń i laboratorium oraz punktów zdobytych na egzaminach częściowych (albo na egzaminie uzupełniającym lub poprawkowym):

punkty ocena
<24 2
24... 3
30... 3+
36... 4
42... 4+
48...60 5

Warunkiem koniecznym zdania egzaminu końcowego jest zaliczenie ćwiczeń i laboratorium.

Notatki

wykład
  • [3.03.2009] 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;
    • wydajność algorytmów;
    • złożoność obliczeniowa: w każdym przypadku, w najgorszym i w średnim.

  • [10.03.2009] sortowanie, dolna granica na sortowanie:

    • definicja problemu sortowania;
    • elementarne metody sortowania (bąbelkowe, przez zamianę, przez wstawianie, przez wyszukiwanie);
    • drzewa decyzyjne i dolna granica dla problemu sortowania.

  • [17.03.2009] sortowanie w czasie liniowym:

    • sortowanie przez zliczanie;
    • sortowanie kubełkowe;
    • sortowanie leksykograficzne.

  • [24.03.2009] scalanie i podział:

    • definicja problemu scalania;
    • scalanie z wykorzystaniem zewnętrznego bufora pomocniczego;
    • sortowanie przez scalanie;
    • sortowanie zewnętrzne;
    • definicja problemu podziału;
    • algorytmy podziału (algorytm Lomuta);
    • sortowanie szybkie (przez podział).

  • [31.03.2009] wybór k-tego elementu:

    • definicja problemu wyboru;
    • jednoczesne znajdowanie minimum i maksimum;
    • algorytm Hoare'a;
    • algorytm magicznych piątek.

  • [7.04.2009] haszowanie:

    • zbiór dynamiczny;
    • slownik i operacje słownikowe;
    • idea haszowania;
    • adresowanie bezpośrednie;
    • tablice z haszowaniem i kolizje;
    • dobre funkcje haszujące;
    • rozwiązywanie kolizji metodą łańcuchową;
    • adresowanie otwarte: metoda liniowa, kwadratowa i podwójnego haszowania.

  • [21.04.2009] słowniki i drzewa BST:

    • slownik i operacje słownikowe;
    • drzewa BST (binarnych poszukiwań);
    • losowe drzewa BST;
    • drzewa AVL;
    • drzewa RBT (czerwono-czarne).

  • [28.04.2009] słowniki zewnętrzne:

    • drzewa SPLAY (samoorganizujące się);
    • B-drzewa i 2-3-4-drzewa.

  • [5.05.2009] kolejki priorytetowe:

    • kolejka priorytetowa i operacje kolejkowe;
    • listowa implementacja kolejek priorytetowych;
    • implementacja kolejek priorytetowych na drzewach zrównoważonych;
    • kopiec jako drzewo binarne zupełne z porządkiem kopcowym;
    • tablicowa implementacja kopca;
    • sortowanie z wykorzystaniem kopca.

  • [12.05.2009] złączalne kolejki priorytetowe:

    • złączalne kolejki priorytetowe;
    • drzewa dwumianowe;
    • kopce dwumianowe.

  • [12.05.2009] 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.

  • [26.05.2009] metoda "dziel i zwyciężaj" (divide and conquer):

    • 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: sortowanie przez scalanie (merge-sort), sortowanie przez podział (quick-sort) i wyszukiwanie binarne (binary search);
    • mnożenie długich liczb;
    • mnożenie macierzy metodą Strassena;
    • obliczanie optymalnej wartości progowej (threshold).

  • [2.06.2009] programowanie dynamiczne (dynamic programming):

    • rozwiązywanie problemów metodą programowania dynamicznego;
    • własność optymalnej podstruktury;
    • własność wspólnych podproblemów;
    • zastosowanie metody programowania dynamicznego w obliczeniach: liczba Fibonacciego i symbol Newtona;
    • stokrotki (przejście przez tablicę z wagami);
    • najdłuższy wspólny podciąg;
    • spamiętywanie (memoization).

  • [9.06.2009] strategia zachłanna (greedy approach):

    • rozwiązywanie problemów metodą zachłanną;
    • własność optymalnej podstruktury;
    • własność wyboru zachłannego;
    • problem wydawania reszty;
    • ciągły problem plecakowy;
    • kody Huffmana.

  • [16.06.2009] powtórka materiału przed egzaminem:

    • metoda "dziel i zwyciężaj";
    • programowanie dynamiczne;
    • strategia zachłanna.

Listy zadań

ćwiczenia
  • lista nr 1 (10 marca): efektywność algorytmów (ps/pdf)
  • lista nr 2 (17 marca): sortowanie (ps/pdf)
  • lista nr 3 (24 marca): sortowanie w czasie liniowym (ps/pdf)
  • lista nr 4 (31 marca): scalanie i podział (ps/pdf)
  • lista nr 5 (7 kwietnia): wybór k-tego elementu (ps/pdf)
  • lista nr 6 (21 kwietnia): haszowanie (ps/pdf)
  • lista nr 7 (28 kwietnia): słowniki i drzewa BST (ps/pdf)
  • lista nr 8 (5 maja): słowniki zewnętrzne (ps/pdf)
  • lista nr 9 (19 maja): kolejki priorytetowe (ps/pdf)
  • lista nr 10 (26 maja): zbiory rozłączne (ps/pdf)
  • lista nr 11 (2 czerwca): metoda "dziel i zwyciężaj" (ps/pdf)
  • lista nr 12 (9 czerwca): programowanie dynamiczne (ps/pdf)
  • lista nr 13 (16 czerwca): strategia zachłanna (ps/pdf)
  • lista nr 14 (23 czerwca): metoda "dziel i zwyciężaj", strategia zachłanna, strategia zachłanna (ps/pdf)
laboratoria
  • zadanie nr 1 (31 marca): szybkie potęgowanie (ps/pdf)
  • zadanie nr 2 (28 kwietnia): sortowanie zewnętrzne (ps/pdf)
  • zadanie nr 3 (26 maja): zrównoważone drzewo BST (ps/pdf)
  • zadanie nr 4 (16 czerwca): najdłuższy podciąg rosnący (ps/pdf)

Rankingi

Ogłoszenia

25.06.2009
Wystawiłem już oceny z ćwiczeń i laboratorium oraz z egzaminu. O zaliczenie ćwiczeń jeszcze można powalczyć zadaniami dodatkowymi. Czekam też na ostatnie programy z laboratorium. Dodatkowo obniżyłem próg na zaliczenie egzaminu do 19 punktów.
24.06.2009
Poprawiłem punktację w końcowym zestawieniu o 13:35 (poprzednio wkradły się tam jakieś błędne dane) egzaminacyjnym - wyniki trochę się zmieniły, ostatecznie egzamin zdało 7 osób, ale zbiory tych osób są różne!
Przypominam też, że do oceny końcowej z egzaminu wliczają się dodatkowe punkty z ćwiczeń i laboratorium (tego zestawienia jeszcze nie ma).
24.06.2009
Niektórym osobom brakuje kilku punktów do zaliczenia ćwiczeń. Można te punkty uzyskać wysyłając mi pisemne rozwiązania zadań z listy 14. Z listy tej można rozwiązać pisemnie zadania 3-8 i 10.
24.06.2009
Egzamin uzupełniający, który odbędzie się we wtorek 30 czerwca 2009, będzie przebiegał w tradycyjny sposób: o 17 rozpocznie się część testowa (9 pytań) a o 18:minut-kilka część zadaniowa (3 zadania). Osoby, które mają zaliczoną część testową (zebrały w sumie co najmniej 6 punktów ze wszystkich tercji) nie muszą w niej uczestniczyć.
24.06.2009
Postanowiłem obniżyć próg na zaliczenie egzaminu do 13 punktów!!! Dodatkowo zsumowałem punkty z wszystkich tercji egzaminu (bez względu na to, czy tercja została zaliczona czy nie). Tym samym egzamin zaliczyło 7 studentów (ale uwaga, aby uzyskać wpis z egzaminu trzeba najpierw zaliczyć ćwiczenia i laboratorium). Gratuluję szczęśliwcom a pozostałym przypominam o następnym terminie egzaminu: wtorek, 30 czerwca 2009.
19.06.2009
Termin egzaminu uzupełniającego został zmieniony i ostatecznie odbędzie się we wtorek 30 czerwca 2009 w godzinach 17-21 w sali 119.
16.06.2009
Dodatkowe ćwiczenia odbędą się w najbliższy wtorek 23 czerwca o 16:15. Listę zadań opublikuję dopiero w sobotę - znajdą się na niej zadania dotyczące metody dziel i zwyciężaj, programowania dynamicznego i strategii zachłannej.
16.06.2009
Trzeci egzamin częściowy rozpocznie się w piątek 19 czerwca o godzinie 17:15 najpewniej w s.119.
Na egzaminie tym będzie obowiązywał następujący materiał: haszowanie, metoda dziel i zwyciężaj, programowanie dynamiczne i strategia zachłanna.
9.06.2009
Z listy 12 można rozwiązać pisemnie zadanie 6 albo 7.
2.06.2009
Z listy 11 można rozwiązać pisemnie zadanie 5 albo 6.
28.05.2009
Przedłużam termin oddania zadania 4 na laboratorium do niedzieli 21 czerwca 2009.
27.05.2009
Jest już opublikowane czwarte zadanie laboratoryjne do zaprogramowania.
27.05.2009
Są już wyniki drugiej tercji egzaminu. Omówienie zadań po najbliższych ćwiczeniach.
26.05.2009
Z listy 10 można rozwiązać pisemnie zadanie 5.
22.05.2009
To już chyba ostatnia zmiana na liście 10.
22.05.2009
Przedłużam termin oddania zadania 3 na laboratorium do niedzieli 31 maja 2009.
21.05.2009
Dopisałem jeszcze jedno zadanie do listy 10. Lista ta będzie rozwiązywana w najbliższy wtorek 26 maja 2009.
21.05.2009
Drugi egzamin częściowy rozpocznie się w piątek 22 maja w s.119 o godzinie 17:15.
19.05.2009
Z listy 9 można rozwiązać pisemnie zadanie 5, 7 albo 8.
2.05.2009
Dzisiaj ćwiczenia nie odbyły się. Za to w przyszłym tygodniu będą tylko ćwiczenia (i 2 krótsze niż zazwyczaj listy zadań) bez wykładu. Starujemy o 17, aby wszyscy mogli punktualnie dojechać na klasówkę.
5.05.2009
Z listy 8 można rozwiązać pisemnie zadanie 3, 4 albo 7.
5.03.2009
Jest już opublikowane trzecie zadanie laboratoryjne do zaprogramowania.
2.05.2009
Oceniłem juz pierwsze zadanie z laboratorium. Link do wyników jest powyżej. Zadanie drugie (jak do tej pory) wysłali mi dopiero 3 studenci...
Przypominam, że za każde poprawnie zrobione zadanie laboratoryjne będzie można dostać do 20 punktów, a warunkiem koniecznym uzyskania zaliczenia będzie oddanie co najmniej dwóch dobrze działających programów (ocenionych na co najmniej 10 punktów).
28.04.2009
Przedłużam termin oddania zadania 2 na laboratorium do niedzieli 3 maja 2009.
28.04.2009
Z listy 7 można rozwiązać pisemnie zadanie 5, 7 albo 8.
21.04.2009
Na ostatnich ćwiczeniach sporo czasu poświęciliśmy na omówienie zadań z egzaminu, dlatego z listy 6 można rozwiązać pisemnie zadanie 2, 3, 4, 5 albo 6.
19.04.2009
Są już wyniki pierwszej tercji egzaminu. Omówienie zadań po najbliższych ćwiczeniach.
15.04.2009
Pierwszy egzamin częściowy rozpocznie się w piątek 17 kwietnia w s.119 o godzinie 17:15.
7.04.2009
Z listy 5 można rozwiązać pisemnie zadanie 2 albo 4.
4.04.2009
Jest już opublikowane drugie zadanie laboratoryjne do zaprogramowania.
31.03.2009
Z listy 4 można rozwiązać pisemnie zadanie 2.
31.03.2009
Przedłużam termin oddania zadania 1 na laboratorium do niedzieli 5 kwietnia 2009.
24.03.2009
Z listy 3 można rozwiązać pisemnie zadanie 4 albo 5.
17.03.2009
Z listy 2 można rozwiązać pisemnie zadanie 4 albo 5.
17.03.2009
Z listy 1 można jeszcze rozwiązać pisemnie zadanie 3, 5, 6 albo 7.
17.03.2009
Dodałem nowy punkt do zasad zaliczania ćwiczeń: można wybrać sobie jedno zadanie z tych niezrobionych na zajęciach i wysłać mi rozwiązanie do końca tygodnia, w którym dana lista obowiązywała. Zdecydowałem się na to, ze względu na małą liczbę deklaracji - może to będzie jakieś rozwiązanie problemu dla nieśmiałych i zachęta dla niezdecydowanych...
14.03.2009
Wyznaczyłem już terminy egzaminów częściowych (wszystkie odbędą się w piątek). Proszę zapozać się z datami i zarezerwować sobie czas.
14.03.2009
Zaktualizowałem zasady zaliczenia przedmiotu. Na ćwiczeniach pozostaje system deklaracji. Egzamin będzie się składał z 3 egzaminów częściowych (wydaje się, że łatwiej będzie zdać ten egzamin po kawałku).
5.03.2009
Jest już opublikowane pierwsze zadanie laboratoryjne do zaprogramowania.
5.03.2009
Przepisywaniem ocen z ćwiczeń/laboratorium z poprzednich lat zajmuje się prodziekan d/s studenckich Marek Piotrów. Studenci, którzy chcą w ten sposób zaliczyć zajęcia z Algorytmów i Struktur Danych, powinni załatwić tę sprawę na początku semestru.
1.02.2009
W tym miejscu będą się pojawiać ogłoszenia dotyczące organizacyji zajęć oraz terminów kolokwiów i egzaminów.

powrót na początek strony