Algorytmy i struktury danych - 2014

Matematyka stosowana

Czwartek 7³⁰ - 9⁰⁰ A-1/204 wykład

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

Poniedziałek 18⁵⁵ - 20³⁵ D-1/317.2 laboratorium

Czwartek 13¹⁵ - 15⁰⁰ D-1/317.4 laboratorium

Czwartek 18⁵⁵ - 20³⁵ D-1/317.2 laboratorium

Czwartek 18⁵⁵ - 20³⁵ D-1/317.4 laboratorium

Piątek 15¹⁵ - 16⁵⁵ D-1/317.3 laboratorium

Wyniki kolokwium

Literatura

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. (wydane również przez WNT i PWN)
2. Jon Kleinberg, Eva Tardos: Algorithm Design.
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 (na tydzień od 13 do 17 października)
• Lista na laboratorium nr 3 (na tydzień od 20 do 24 października)
• Lista na laboratorium nr 4 (na tydzień od 27 do 31 października)
• Lista na laboratorium nr 5 (na tydzień od 3 do 7 listopada) - poprawiona 7.11
• Lista na laboratorium nr 6 (na tygodnie od 10 do 21 listopada)
• Lista na laboratorium nr 7 (na tydzień od 24 do 28 listopada)
• Lista na laboratorium nr 8 (na tygodnie od 1 do 12 grudnia)
• Lista na laboratorium nr 9 (na tydodnie od 15 grudnia do 9 stycznia)
• Lista na laboratorium nr 10 (na tydodnie od 12 do 23 stycznia)

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

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

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. Do zaliczenia kursu konieczna jest pozytywna ocena z kolokwium.

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