Algorytmy i struktury danych 2019

Czwartek 1315 - 1500 TP C-13/1.30 wykład

Piątek 915 - 1100 C-13/1.30 wykład

Wtorek 915 - 1100 C-7/303 ćwiczenia

Wtorek 1115 - 1300 C-7/303 ćwiczenia

Czwartek 730 - 900 C-7/303 ćwiczenia

Czwartek 915 - 1100 C-7/303 ćwiczenia (dr inż. P.Syga)

Czwartek 1115 - 1300 C-7/303 ćwiczenia (dr inż. P.Syga)

Poniedziałek 730 - 1900 TN/TP D-1/317.2 laboratorium (mgr inż. P.Stopyra)

Poniedziałek 1315 - 1500 TN/TP D-1/317.2 laboratorium (mgr inż. I.Hradovich)

Poniedziałek 1515 - 1655 TN/TP D-1/317.2 laboratorium (mgr inż. I.Hradovich)

Środa 730 - 900 TN/TP D-1/317.2 laboratorium (mgr inż. M.Hradovich)

Środa 915 - 1100 TN/TP D-1/317.2 laboratorium (mgr inż. M.Hradovich)

Terminy egzaminów: 28 czerwca, 1515 - 1730, A-1/322, oraz 4 lipca, 915 - 1130, A-1/322.

Wyniki egzaminu (Osoby które zdały ale chciałyby poprawić ocenę proszone są o powiadominie wykładowcy o tym emailem do środy rano).

Wyniki drugiego egzaminu.

Literatura

  1. S. Dasgupta, C. Papadimitriou, U. Vazirani: Algorytmy. WN PWN, Warszawa 2011 (ISBN 9788301162788)
  2. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest: Wprowadzenie do algorytmów. WNT, Warszawa 1997 (ISBN 83-204-2144-6)
  3. J. Kleinberg, E. Tardos: Algorithm Design. (ISBN: 9780321295354)

Listy zadań na ćwiczenia

Listy zadań na laboratorium

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

  1. Wykład organizacyjny (1 godzina). (28-02-2019)
    []
  2. Wprowadzenie. (1-03-2019)
    [Notacja asymptotyczna. Tablica, stos, kolejka i kolejka priorytetowa (listy jedno i dwukierunkowe, kopiec). Reprezentacje grafów.]
  3. Algorytmy dziel i rządź. (7-03-2019)
    [Ogólna strategia algorytmów dziel i rządź. Przykłady: mnożenie liczb, binary search, sortowanie przez scalanie, ...]
  4. Algorytmy dziel i rządź. (8-03-2019)
    [Główne twierdzenie o rekursji. Szukanie k-tej statystyki. Quicksort. Dolna granica na sortowanie przez porównanie. Otoczka wypukła.]
  5. Grafy nieskierowane. (15-03-2019)
    [Przeszukiwanie w głąb. Spójne składowe. Przeszukiwanie wszerz. Najkrótsze ścieżki. Graf z wagami krawędzi. Algorytm Dijkstra'y. Implementacja modyfikowalnej kolejki priorytetowej.]
  6. Grafy skierowane. (21-03-2019)
    [Przeszukiwanie w głąb z porządkiem odwiedzania. DAG i porządek topologiczny. Składowe silnie spójne. Algorytm Bellman-Ford.]
  7. Algorytmy zachłanne. (22-03-2019)
    [Minimalne drzewo rozpinające. Union-Find. Kody Huffmana.]
  8. Programowanie dynamiczne. (29-03-2019)
    [Najdłuższy rosnący podciąg. Problem plecakowy. Mnożenie macierzy. Najkrótsze ścieżki w grafie.]
  9. Słowniki - wyszukiwanie informacji. (4-04-2019)
    [Słownik definicja. Drzewa binarne. Tablice. Tablice haszowane.]
  10. Zrównoważone drzewa. (5-04-2019)
    [Drzewa czerwono-czarne. B-drzewa.]
  11. Koszt zamortyzowany. (12-04-2019)
    [Metody kosztu sumarycznego, księgowania i potencjału. Tablice dynamiczne.]
  12. Koszt zamortyzowany. (15-04-2019)
    [Kopiec dwumianowy. Kopiec Fibonacciego.]
  13. Koszt zamortyzowany. (16-04-2019)
    [Samoorganizujące się drzewa binarne (splay).]
  14. Przepływy i skojarzenia. (25-04-2019)
    [Algorytm Forda-Fulkersona. Algorytm Edmondsa-Karpa. Skojarzenie w grafie dwudzielnym.]
  15. Przepływy i skojarzenia. (26-04-2019)
    [Modyfikacje przepływów. Skojarzenia w dowolnym grafie.]
  16. Programowanie liniowe. (10-05-2019)
    [Przykłady programów liniowych. Terminologia, postacie kanoniczna, standardowa i dopełnieniowa. Programowanie całkowitoliczbowe na przykładzie problemu plecakowego.]
  17. Problemy niepodatne. (16-05-2019)
    [Problemy decyzyjne. Problemy wielomianowo weryfikowalne - klasa NP. NP-trudność i NP-zupełność. Redukcje między problemami.]
  18. Problemy niepodatne. (17-05-2019)
    [Przykłady redukcji - problemy 3SAT, cykl Hamiltona, komiwojażer, zbiór niezależny, klika, pokrycie wierzchołkowe, pakowanie zbiorów, pokrycie zbiorami. Silna NP-zupełność. Programowanie całkowitoliczbowe.]
  19. Algorytmy aproksymacyjne. (24-05-2019)
    [Definicja algorytmu aproksymacyjnego. 1/2 i 1/3-aproksymacja dla MAKESPAN. 1/2-aproksymacja pokrycia wierzchołkowego. 1/2-aproksymacja problemu MAX-CUT.]
  20. Algorytmy aproksymacyjne. (30-05-2019)
    [1/2 i 1/3-aproksymacja euklidesowego problemu komiwojażera. Pełny aproksymacyjny schemat wielomianowy dla problemu plecakowego.]
  21. Sieci sortujące. (31-05-2019)
    []
  22. Podsumowanie wykładu. (7-06-2019)
    []
  23. Podsumowanie wykładu. (14-06-2019)
    []

Zasady zaliczenia grupy kursów

Zaliczenie ćwiczeń

  1. Zasadniczym celem ćwiczeń jest ułatwienie studentom samodzielnej pracy nad opanowaniem materiału w czasie całego semestru. Ocena z ćwiczeń jest oceną jakości i intensywności pracy studenta w czasie semestru.
  2. Wykładowca ogłasza z odpowiednim wyprzedzeniem listy zadań do samodzielnego rozwiązania przed zajęciami. Na ćwiczeniach studenci prezentują rozwiązania zadań. W trakcie rozwiązywania wyjaśniane są wątpliwości dotyczące rozwiązania oraz przedstawiane alternatywne rozwiązania.
  3. Podstawą do wystawienia oceny są wyniki krótkich sprawdzianów. Sprawdziany będą polegały na rozwiązaniu jednego zadania i punktowane od 0 do 5. Materiałem obowiązującym na sprawdzianie są tematy przerobione na trzech poprzednich ćwiczeniach. Sprawdziany przeprowadzane są bez uprzedniej zapowiedzi. Nieobecność na sprawdzianie daje 0. Jeden, najsłabszy sprawdzian studenta w semestrze zostanie anulowany.
  4. Decyzję odnośnie wyboru zadań do rozwiązania podejmuje prowadzący.
  5. Podstawą do obliczenia punktów z ćwiczeń jest średnia punktów ze sprawdzianów. Średnia może być podwyższona przez prowadzącego w zależności od aktywności studenta na ćwiczeniach.
  6. Punktacja nie podlega poprawianiu po zakończeniu zajęć. Średnia punktów z ćwiczeń nie może przekroczyć 7.

Zaliczenie laboratorium

  1. Na laboratoriach studenci powinni oddawać implementacje list przygotowanych do kursu.
  2. Oddawane rozwiązania powinny być samodzielnie napisane.
  3. Każda lista ma swoją wagę od 1 do 3. Za każdą listę można dostać od 0 do 5 punktów.
  4. Listy powinny być oddane na zajęciach wymienionych na liście. Oddanie na następnych zajęciach powoduje stratę połowy punktów jakie przyznano za rozwiązanie listy. Oddanie na kolejnych zajęciach powoduje przyznanie 0 punktów.
  5. Do zaliczenia laboratorium konieczne jest oddanie rozwiązań wszystkich list.
  6. Podstawą do obliczenia punktów z laboratorium jest średnia ważona punktów z list.

Zaliczenie wykładu

  1. Zdanie egzaminu jest warunkiem koniecznym zaliczenia kursu.
  2. Egzamin odbędzie się w sesji egzaminacyjnej (stosuje się do niego zasady egzaminu z regulaminu studiów). W przypadku pisania egzaminu w dwóch terminach za ocenę przyjmuję się ocenę z drugiego terminu (nadpisanie oceny).
  3. Na egzaminie jedyną dopuszczalną pomocą naukową jest kartka formatu a4 podpisana w ten sposób aby z odległości 2 metrów dało się ustalić jej właściciela. Oprócz tego student nie ma prawa mieć żadnych innych kartek, książek i innych pomocy. Kartki z treścią zadań i miejscem na rozwiązania oraz brudnopisy dostarcza wykładowca.

Ocena końcowa grupy kursów

Ocena końcowa (egzamin) liczona jest według wzoru 0.25*PC+0.25*PL+0.5*E i zaokrąglana w górę do najbliższej oceny (2.5 zaokrągla się jednak do 2.0).
[PC - średnia punktów z ćwiczeń, PL - średnia punktów z laboratorium, E - ocena z egzaminu.]

Counter Valid XHTML 1.1! Valid CSS!

Maciej.Gebala@pwr.edu.pl