Semestr zimowy 2010/11
Semestr zimowy 2011/12
Semestr zimowy 2012/13
Semestr zimowy 2013/14
Semestr zimowy 2014/15
Algorytmy i struktury danych MAT2305
Treści programowe:
Sortowanie:
(kubełkowe, heapsort, przez wstawianie, przez scalanie, quicksort),
Elementarne struktury danych:
(stosy i kolejki,
listy,
drzewa: binarnych poszukiwań, 2-3 drzewa,
haszowanie),
Algorytmy algebry:
(algorytm Knutha-Morrisa-Pratta,
mnożenie ciągu macierzy
algorytm Strassena,
mnożenie wielomianów - szybka transformata Fouriera),
Algorytmy grafowe
(reprezentacja grafu,
przeszukiwanie wszerz,
przeszukiwanie w głąb,
minimalne drzewa rozpinające),
Najkrótsze ścieżki w grafach (z wagami)
(algorytmy:
Forda-Bellmana,
Dijkstry,
Warshalla-Floyda),
Sieci przepływu
(maksymalizacja przepływu metodą Forda-Fulkersona,
skojarzenia w grafach dwudzielnych,
maksymalne selektory),
Problemy NP-trudne,
Problemy o złożoności większej niż wielomianowa,
Efekty kształcenia:
Zapoznanie studenta z podstawowymi metod analizy
i projektowania efektywnych algorytmów z użyciem odpowiednio dobranych struktur danych.
Koordynatorzy przedmiotu
W cyklu 2014Z: | W cyklu 2013Z: | W cyklu 2010Z: | W cyklu 2011Z: |
Kryteria oceniania
OCENA Z ĆWICZEŃ
Ocena z przedmiotu zostanie wystawiona na podstawie wyników dwóch sprawdzianów (I za max. 10 pkt., II za max. 20 pkt.) oraz zadań dodatkowych, kartkówek i aktywności studentów na zajęciach. Sprawdzian I weryfikuje wiedzę i umiejętności studentów dot. efektu kształcenia EK1. Sprawdzian II weryfikuje wiedzę i umiejętności studentów dot. efektów kształcenia EK2, EK3. Efekt kształcenia EK8 jest weryfikowany podczas omawiania zadań na ćwiczeniach oraz na podstawie zadań dodatkowych.
Warunkiem koniecznym uzyskania oceny pozytywnej jest zdobycie co najmniej 15 pkt. w semestrze, w tym co najmniej 3 pkt. z pierwszego sprawdzianu i co najmniej 8 pkt. z drugiego sprawdzianu. Oceny będą wystawione wg. następującej skali punktowej:
28-30 - bdb, 25-27 - db+, 22-24 - db, 19-21 - dst+, 15-18 - dst, 0-14 - ndst
OCENA Z PRACOWNI SPECJALISTYCZNEJ
Zaliczenie odbywa się na podstawie zdobytych punktów za implementację programów i punktów za odpowiedź ustną w danym temacie.
1) Optymalizacja rozwiązań algorytmicznych pod względem złożoności czasowej ( implementacja 4 pkt+ odpowiedź ustna 3pkt)
2) wykorzystanie techniki dziel i zwyciężaj (implementacja 4 pkt+ odpowiedź ustna 3pkt)
3) wykorzystanie techniki programowania zachłannego i dynamicznego (implementacja 4pkt+ odpowiedź ustna 4pkt)
4) Algorytmy grafowe (implementacja 4pkt+ odpowiedź ustna 3pkt)
5)Implementacja problemów trudnobliczeniowych za pomocą algorytmów przybliżonych (implementacja 4pkt+ odpowiedź ustna 3pkt)
Żeby zaliczyć pracownię należy mieć powyżej 16 punktów w tym co najmniej 5 pkt za odpowiedź i 3 pkt za zadanie z algorytmów przybliżonych. Oceny są wystawione wg. skali: 0-16 pkt- ndst, 17-20 pkt- dst, 21-24 pkt- dst+, 25-28 pkt- dobry, 29-32 pkt- dobry+, 33-36 pkt- b.dobry.
OCENA Z WYKŁADU
Ocena z wykładu zostanie wystawiona na podstawie egzaminu pisemnego. Prowadzący może zwolnić z pisania egzaminu studentów, którzy wykazali się znajomością efektów kształcenia EK1-EK3 zaliczając ćwiczenia i wykonując zadania dodatkowe. Oceny z egzaminu będą wystawione wg. następującej skali punktowej:
19-20 - bdb, 17-18 - db+, 15-16 - db, 13-14 - dst+, 10-12 - dst, 0-9 - ndst
Literatura
a) podstawowa:
Aho A.V., Hopcroft J.E. UllmanJ.D.: Projektowanie
i analiza algorytmów komputerowych, PWN,
Warszawa 1982
Cormen T.H., Leiserson C.E., Rivest R.I., Stein C.:
Wprowadzenie do algorytmów, WNT,
Warszawa 2005
Lipski W.: Kombinatoryka dla programistów, WNT,
Warszawa 1988
b) uzupełniająca: