algorytmy i struktury danych

Na wykładzie prezentowanych jest wiele różnorodych problemów obliczeniowych oraz skutecznych i efektywnych metod ich rozwiązywania. 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.

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

Literatura podstawowa:

  • T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein: Wprowadzenie do algorytmów. WNT, Warszawa 2004.
  • A.V.Aho, J.E.Hopcroft, J.D.Ullman: Projektowanie i analiza algorytmów. Helion, Gliwice 2003.
  • L.Banachowski, K.Diks, W.Rytter: Algorytmy i struktury danych. WNT, Warszawa 1996.
  • J.Kleinberg, E.Tardos: Algorithm design. Addison-Wesley, 2005.
  • G.Brassard, P.Bratley: Algorithmics - theory & practice. Prentice Hall, 1993.

Literatura uzupełniająca:

  • D.C.Kozen: The Design and analysis of algorithms. Springer-Verlag, 1992.
  • R.Neapolitan, K.Naimipour: Podstawy algorytmów z przykładami w C++. Helion, Gliwice 2004.
  • R.Sedgewick: Algorytmy w C++. RM, Warszawa 1999.
  • 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.

Terminarz

  • wykład: środa 10-12 s.25 i czwartek 10-12 s.25 (K.Loryś)
  • repetytorium: wtorek 14-16 s.25 (P.Rzechonek)
  • laboratorium: wtorek 9-11 (M.Bieńkowski)
  • ćwiczenia: środa 12-14 (T.Jurdziński s.103, P.Kanarek s.139, K.Loryś s.141, J.Łopuszański s.5, R.Nowak s.105, P.Rzechonek s.4, P.Zalewski s.140)

Repetytorium

2.03.2010: złożoność obliczeniowa
Złożoność obliczeniowa. Szacowanie złożoności pamięciowej i czasowej. Podstawowe struktury danych: tablice, listy, drzewa, grafy.
9.03.2010: złożoność obliczeniowa
Koszt jednorody i logarytmiczny. Asymptotyczna równość funkcji przy szacowaniu złożoności; porównywanie złożoności i wartość progowa (threshold). Procedury rekurencyjne na drzewach BST.
16.03.2010: strategia zachłanna
Własność wyboru zachłannego. Ogólny schemat działania algorytmu zachłannego. Wydawanie reszty. Minimalne drzewo rozpinające dla grafu - algorytm Prima i algorytm Kruskala. Ścieżka Hamiltona w grafie gęstym.
23.03.2010: metoda "dziel i zwyciężaj"
Własność optymalnej podstruktury. Ogólny schemat działania algorytmu "dziel i zwyciężaj". Uniwersalne twierdzenie o rekurencji. Wyszukiwanie binarne. Sortowanie przez scalanie. Mnożenie długich liczb. Sieć permutacyjna Benesa-Waksmana.
30.03.2010: programowanie dynamiczne
Własność wspólnych podproblemów. Ogólny schemat działania algorytmu dynamicznego. Funkcja Fibonacciego. Współczynnik dwumianowy. Najdłuższy wspólny podciąg. Optymalne mnożenie macierzy.
13.04.2010: zadania laboratoryjne
Omówienie zadań A i B na laboratorium.
20.04.2010: słowniki i kolejki priorytetowe
Drzewa AVL. Kopce minimaksowe.
27.04.2010: dolne granice
Drzewa decyzyjne. Sorting, merging, selecting. Liniowe drzewa decyzyjne. Element uniqueness.
4.05.2010: dolne granice c.d.
Gra z adwersarzem. Maksimum i vice-maksimum.
11.05.2010: redukcje problemów
Klasy problemów P, NP i NP-C. Redukcje problemów. Dowodzenie przynależności problemu do klasy NP-C za pomocą redukcji. Problem kliki. Problem pokrycia wierzchołkowego.
18.05.2010: zadania z egzaminu
Omówienie zadań z pierwszego egzaminu połówkowego.
25.05.2010: analiza zamortyzowana
Metoda kosztu sumarycznego. Metoda księgowania. Metoda potencjału.
1.06.2010: analiza zamortyzowana c.d.
Kopiec dwumianowy w wersji leniwej. Kopiec Fibonacciego.
8.06.2010: szybka transformata Fouriera
FFT.
15.06.2010: (zajęcia odwołane)
Będą przeniesione na przyszły tydzień (termin do uzgodnienia).
22.06.2010: mnożenie macierzy, union-find (zajęcia dodatkowe)
Mnożenie macierzy metodą czterech Rosjan. Algorytm Strassena. Drzewiaste struktury danych dla zbiorów rozłącznych.

Ćwiczenia

Notatki do wykładu, listy z zadaniami, zasady organizacji ćwiczeń i oceniania znajdują się na stronie wykładu.

Listy zadań
Ranking

Ranking z ćwiczeń dla studentów ze wszystkich grup a w szczególności z mojej (PRz).

Ogłoszenia

24.06.2010
Oceny na zaliczenie ćwiczeń w mojej grupie będę wpisywać we wtorek 29.06.2010 w trakcie egzaminu albo zaraz po nim.
21.06.2010
Można oglądnąć swoje rozwiązanie zadania 1 z częci II egzaminu połówkowego w czasie moich konsultacji.
21.06.2010
Zaległe repetytorium będziemy odrabiać w tradycyjnym terminie (czyli we wtorek o 14-16) w dniu 22.06.2010.
20.06.2010
Dodatkowe ćwiczenia z AiSD odbędą się w poniedziałek 21.06.2010 w godzinach 16-18. Obecność obowiązkowa!
15.06.2010
Dzisiejsze repetytorium, ostatnie już w tym semestrze, nie odbędzie się. Bardzo Państwa przepraszam za tę zmianę dokonaną w ostatniej chwili. Zajęcia te będą przeniesione na przyszły tydzień. Ich nowy termin, wypadający na początku sesji, ogłoszę wkrótce na tej stronie. Proszę o nadsyłanie propozycji terminów i tematyki tych ostatnich zajęć.
14.04.2010
I-sza tercja egzaminu NIE odbędzie się w sobotę 17 kwietnia jak to wcześniej planowano.
1.03.2010
W tym miejscu będą się pojawiać ogłoszenia organizacyjne dotyczące mojej grupy ćwiczeniowej oraz repetytorium.

powrót na początek strony