Algorytmy i struktury danych - 2015

Matematyka stosowana

Czwartek18⁵⁵ - 20²⁵ C-13/0.31 wykład

Poniedziałek 7³⁰ - 9⁰⁰ D-1/317.4 laboratorium

Poniedziałek 18⁵⁵ - 20²⁵ D-1/317.4 laboratorium

Środa 18⁵⁵ - 20²⁵ D-1/317.4 laboratorium

Czwartek 7³⁰ - 9⁰⁰ D-1/317.4 laboratorium

Czwartek 9¹⁵ - 11⁰⁰ D-1/317.4 laboratorium

Piątek 15¹⁵ - 17⁰⁰ D-1/317.4 laboratorium

Piątek 17⁰⁵ - 18⁴⁵ D-1/317.4 laboratorium

Wyniki kolokwium

Literatura

1. Jon Kleinberg, Eva Tardos: Algorithm Design.
2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. (wydane również przez WNT i PWN)
3. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani: Algorithms. (wydane również przez PWN)
4. Bruce Eckel: Thinking in C++. Helion, 2009

Listy zadań na laboratorium

• Lista na laboratorium nr 1
• Lista na laboratorium nr 2
• Lista na laboratorium nr 3
• Lista na laboratorium nr 4 (na ocenę)
• Lista na laboratorium nr 5
• Lista na laboratoria nr 6 i 7 (na ocenę)
• Lista na laboratorium nr 8
• Lista na laboratoria nr 9 i 10 (na ocenę)
• Lista na laboratoria nr 11 i 12 (na ocenę)
• Lista na laboratoria nr 13 i 14 (na ocenę)

Tematy wykładów (w przybliżeniu)

1. Godziny rektorskie. (1-10-2015)
2. Wprowadzenie. Podstawowe struktury. (8-10-2015)
   [Notacja asymptotyczna. Tablica, stos, kolejka i kolejka priorytetowa (listy jedno i dwukierunkowe, kopiec).]
3. Grafy. (15-10-2015)
   [Definicja grafów. Przykładowe zastosowania. Przeglądanie wszerz i wgłąb. Porządek topologiczny i składowe silnie spójne.]
4. Algorytmy zachłanne. (22-10-2015)
   [Przydział odcinków czasowych. Najkrótsza ścieżka w grafie - algorytm Dijkstry. Minimalne drzewo rozpinające - algorytm Kruskala i algorytm Prima. Struktura Union-Find.]
5. Algorytmy „dziel i rządź”. (29-10-2015)
   [Mergesort, znalezienie otoczki wypukłej, mnożenie liczb całkowitych. Równania rekurencyjne. Twierdzenie o rekurencji uniwersalnej. Dolna granica złożoności problemu sortowania.]
6. Programowanie dynamiczne. (5-11-2015)
   [Przydział odcinków czasowych z wagami. Najkrótsze scieżki w grafie z ujemnymi wagami. Ogólna charakterystyka algorytmów dynamicznych.]
7. Przepływy w sieciach. (19-11-2015)
   [Algorytm Forda-Fulkersona. Modyfikacja Edmondsa-Karpa. Maksymalne skojarzenie w grafie dwudzielnym. Rozłączne ścieżki w grafie.]
8. Rozszerzenia problemu maksymalnego przepływu. (26-11-2015)
   [Rozszerzenie o wielu dostawców i konsumentów, minimalny przepływ przez krawędź. Ścieżki rozłączne wierzchołkowo.]
9. Analiza kosztu zamortyzowanego. (3-12-2015)
   [Licznik binarny: koszt pesymistyczny, koszt sumaryczny, metoda księgowania i metoda potencjału. Tablice dynamiczne.]
10. Klasa NP i niepodatność obliczeniowa. (10-12-2015)
    [Problemy maksymalnego zbioru niezależnego, minimalnego pokrycia wierzchołkowego, pokrycia zbiorami, SAT i 3SAT. Redukcja wielomianowa. Definicja klasy NP i problemy NP-zupełne.]
11. NP i co-NP. PSPACE. (17-12-2015)
    [Inne problemy NP-zupełne i co-NP-zupełne. Problemy PSPACE-zupełne: QSAT i Gry dwuosobowe.]
12. Algorytmy aproksymacyjne. (22-12-2015)
    [Aproksymacja przydziału zadań na maszyny. Aproksymacja pokrycia wierzchołkowego. Nieaproksymowalność ogólnego TSP. Schemat aproksymacyjny dla problemu plecakowego.]
13. Optymalizacja liniowa. (7-01-2016)
14. Kolokwium zaliczeniowe. (14-01-2016) [Przykładowe zadania na kolokwium - nie uwzględnia całego możliwego materiału z wykładu]
15. Podsumowanie wykładu. (21-01-2016)

Zasady zaliczenia kursu

Ocena z laboratorium bierze pod uwagę umiejętności nabyte w trakcie kursu oraz terminowość oddawania zadań. Zadania powinny być samodzielnie rozwiązane i zaimplementowane przez studenta. Listy dzielą się na dwie kategorie: na zaliczenie i na ocenę - średnia z ocen tych drugich list jest podstawą zaliczenia laboratorium. Za listę oddaną w terminie uważa się listę oddaną na zajęciach na które jest przeznaczona lub na następnych zajęciach. Każdy tydzień spóźnienia każdej listy obniża końcową ocenę z laboratorium o 0,2. Aby zaliczyć laboratorium wszystkie listy muszą być zaliczone.

Kolokwium przeprowadzane jest na ostatnim wykładzie - ocena z niego jest składową oceny z kursu.

Ocena z kursu jest sumą ważoną: 50% oceny z laboratorium i 50% oceny z kolokwium, zaokrągloną do najbliższej oceny (2.75-3.25 - 3, 3.25-3.75 - 3.5, itd.).