Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Zaawansowane alg. i struktury danych
Tok studiów:
2019/2020
Kod:
EINF-2-202-GK-s
Wydział:
Elektrotechniki, Automatyki, Informatyki i Inżynierii Biomedycznej
Poziom studiów:
Studia II stopnia
Specjalność:
Grafika komputerowa
Kierunek:
Informatyka
Semestr:
2
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma studiów:
Stacjonarne
Strona www:
 
Prowadzący moduł:
dr hab. Bielecki Andrzej (bielecki@agh.edu.pl)
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

Opis efektów uczenia się dla modułu zajęć
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Powiązania z KEU Sposób weryfikacji i oceny efektów uczenia się osiągniętych przez studenta w ramach poszczególnych form zajęć i dla całego modułu zajęć
Wiedza: zna i rozumie
M_W001 Student posiada uporządkowaną wiedzę dot. metod rozwiązywania problemu maksymalnego przepływu INF2A_W01, INF2A_W02 Aktywność na zajęciach,
Egzamin
M_W002 Student zna metody wyznaczania najliczniejszych skojarzeń w grafach dwudzielnych INF2A_W01, INF2A_W02 Aktywność na zajęciach,
Egzamin
M_W003 Student posiada uporządkowaną wiedzę dot. modelu i typów maszyny PRAM INF2A_W03 Egzamin
M_W004 Student posiada wiedzę dot. zastosowania algorytmów randomizacyjnych INF2A_W01, INF2A_W02 Aktywność na zajęciach,
Egzamin
Umiejętności: potrafi
M_U001 Student potrafi stosować algorytmy przetwarzania tekstu INF2A_U06 Aktywność na zajęciach
M_U002 Student potrafi stosować algorytmy geometryczne INF2A_U06 Aktywność na zajęciach
M_U003 Student potrafi stosować efektywne metody obliczania wartości mnożenia/dzielenia wielomianów, mnożenia macierzy INF2A_U06, INF2A_U05 Aktywność na zajęciach,
Egzamin
M_U004 Student potrafi obliczać szybką transformatę Fouriera INF2A_U06, INF2A_U05 Aktywność na zajęciach
Liczba godzin zajęć w ramach poszczególnych form zajęć:
SUMA (godz.)
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
42 28 0 14 0 0 0 0 0 0 0 0
Matryca kierunkowych efektów uczenia się w odniesieniu do form zajęć i sposobu zaliczenia, które pozwalają na ich uzyskanie
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Forma zajęć dydaktycznych
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Wiedza
M_W001 Student posiada uporządkowaną wiedzę dot. metod rozwiązywania problemu maksymalnego przepływu + - + - - - - - - - -
M_W002 Student zna metody wyznaczania najliczniejszych skojarzeń w grafach dwudzielnych + - + - - - - - - - -
M_W003 Student posiada uporządkowaną wiedzę dot. modelu i typów maszyny PRAM + - - - - - - - - - -
M_W004 Student posiada wiedzę dot. zastosowania algorytmów randomizacyjnych + - + - - - - - - - -
Umiejętności
M_U001 Student potrafi stosować algorytmy przetwarzania tekstu + - + - - - - - - - -
M_U002 Student potrafi stosować algorytmy geometryczne + - + - - - - - - - -
M_U003 Student potrafi stosować efektywne metody obliczania wartości mnożenia/dzielenia wielomianów, mnożenia macierzy + - + - - - - - - - -
M_U004 Student potrafi obliczać szybką transformatę Fouriera + - + - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 100 godz
Punkty ECTS za moduł 4 ECTS
Udział w zajęciach dydaktycznych/praktyka 42 godz
Przygotowanie do zajęć 19 godz
Samodzielne studiowanie tematyki zajęć 39 godz
Szczegółowe treści kształcenia w ramach poszczególnych form zajęć (szczegółowy program wykładów i pozostałych zajęć)
Wykład (28h):

1. (5 godz.) Zaawansowane algorytmy grafowe. Problemy ścieżkowe: algorytm Bellmana-Forda, problemy ścieżkowe i mnożenie macierzy, algorytm Floyda-Warshalla, algorytm Johnsona. Skojarzenia: skojarzenia w grafach dwudzielnych – algorytm Hopcrofta-Karpa, skojarzenia w grafach dowolnych – algorytm Edmondsa. Maksymalny przepływ: algorytm Forda-Fulkersona, algorytm Edmondsa-Karpa, algorytm Dinica.
2. (5 godz.) Algorytmy geometryczne: przynależność punktu do wielokąta, znajdowanie otoczki wypukłej, technika zamiatania i problem najmniej odległej pary punktów
3. (5 godz.) Algorytmy równoległe: abstrakcyjny model PRAM, sumy prefiksowe i sortowanie na PRAMie, algorytm jednoczesnych podstawień, równoległa kontrakcja drzew.
4. (4 godz.) Wielomiany i FFT: mnożenie wielomianów, dzielenie wielomianów, obliczanie wartości, interpolacja.
5. (5 godz.) Randomizacja: algorytmy Monte Carlo i Las Vegas, problem maksymalnego przekroju, problem długiej ścieżki.
6. (3 godz.) Hierarchiczne struktury danych w algorytmach ewolucyjnych. Algorytmy iteracyjne bazujące na tw. o zbieżności w grafice komputerowej.
7. (3 godz.) Dynamiczne struktury grafowe.

Ćwiczenia laboratoryjne (14h):

1. Algorytm Hopcrofta-Karpa, algorytm Edmondsa, algorytm Forda-Fulkersona, algorytm Edmondsa-Karpa, algorytm Dinica.
2. Przetwarzanie tekstu: algorytm Boyera – Moore’a, okres i prefikso-sufiks tekstu, algorytmy KMP i MP, kody prefiksowe i kompresja Huffmana.
3. Zastosowanie algorytmów geometrycznych: przynależność punktu do wielokąta, znajdowanie otoczki wypukłej, technika zamiatania, problem najmniej odległej pary punktów, diagramy Woronoja, triangulacja Delone
4. Szybka transformata Fouriera, mnożenie wielomianów, dzielenie wielomianów, obliczanie wartości, interpolacja.
5. Algorytmy Monte Carlo i Las Vegas, problem maksymalnego przekroju, problem długiej ścieżki.

Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Treści prezentowane na wykładzie są przekazywane w formie prezentacji multimedialnej w połączeniu z klasycznym wykładem tablicowym wzbogaconymi o pokazy odnoszące się do prezentowanych zagadnień.
  • Ćwiczenia laboratoryjne: W trakcie zajęć laboratoryjnych studenci samodzielnie rozwiązują zadany problem praktyczny, dobierając odpowiednie narzędzia. Prowadzący stymuluje grupę do refleksji nad problemem, tak by otrzymane wyniki miały wysoką wartość merytoryczną.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Zasady udziału w zajęciach:
  • Wykład:
    – Obecność obowiązkowa: Nie
    – Zasady udziału w zajęciach: Studenci uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci winni na bieżąco zadawać pytania i wyjaśniać wątpliwości. Rejestracja audiowizualna wykładu wymaga zgody prowadzącego.
  • Ćwiczenia laboratoryjne:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci wykonują ćwiczenia laboratoryjne zgodnie z materiałami udostępnionymi przez prowadzącego. Student jest zobowiązany do przygotowania się w przedmiocie wykonywanego ćwiczenia, co może zostać zweryfikowane kolokwium w formie ustnej lub pisemnej. Zaliczenie zajęć odbywa się na podstawie zaprezentowania rozwiązania postawionego problemu. Zaliczenie modułu jest możliwe po zaliczeniu wszystkich zajęć laboratoryjnych.
Sposób obliczania oceny końcowej:

Ćwiczenia:
Aby uzyskać pozytywną ocenę końcową niezbędne jest uzyskanie pozytywnej oceny z
zajęć laboratoryjnych, w której skład wchodzi:
1. procentowa ocena ćwiczeń realizowanych w trakcie tych zajęć (zob. niżej),
oraz.
2. procentowa ocena z kolokwiów, liczona jako ilość otrzymanych punktów w stosunku do maksymalnej możliwej.
Zakłada się, że pozycje 1 i 2 sumuja się do 100%.
Sposób liczenia oceny z zajęć laboratoryjnych:
A. Za każde z zadań realizowanych na ćwiczeniach student może otrzymać określoną liczbę punktów.
B. W danej grupie ćwiczeniowej student o maksymalnej liczbie zgromadzonych punktów (w skali całego semestru) otrzymuje 100% . Punktacja pozostałych studentów tej grupy jest liczona relatywnie do tej punktacji.
Sposób przeliczania oceny procentowej na ocenę zwykłą (tj. na skalę 2.0-5.0) odbywa się zgodnie z regulaminem studiów AGH

Egzamin:
Egzamin ma formę pisemną. Przy zakładanej maksymalnej możliwej ilości punktów N, którą można z niego uzyskać, liczony jest uzyskany procent punktów. Sposób przeliczania oceny procentowej na ocenę zwykłą (tj. na skalę 2.0-5.0) odbywa się zgodnie z regulaminem studiów AGH.
Ocena Końcowa:
Aby uzyskać pozytywną ocenę końcową niezbędne jest uzyskanie pozytywnej oceny z egzaminu oraz ćwiczeń laboratoryjnych.
Obliczamy średnią arytmetyczną z ocen zaliczenia uzyskanych we wszystkich terminach.
Wyznaczmy ocenę końcową na podstawie zależności:
if sr>4.75 then OK:=5.0 else
if sr>4.25 then OK:=4.5 else
if sr>3.75 then OK:=4.0 else
if sr>3.25 then OK:=3.5 else OK:=3

Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Wymagania wstępne i dodatkowe, z uwzględnieniem sekwencyjności modułów :

• Algorytmy i struktury danych
• Analiza matematyczna
• Algebra liniowa z geometrią analityczną

Zalecana literatura i pomoce naukowe:

1. Wprowadzenie do algorytmów, Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Wydawnictwa Naukowo – Techniczne, 2004.
2. Algorytmy i struktury danych, L. Banachowski, K. Diks, W. Rytter, Wydawnictwa Naukowo – Techniczne, 2006.
3. Randomized Algorithms, R. Motwani, P. Raghavan, Cambridge University Press, 1995.
4. Jewels of stringology, W. Rytter, M. Crochemore, World Scientific, 2003.

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

Nie podano dodatkowych publikacji

Informacje dodatkowe:

Korzystano z programu udostępnionego na http://wazniak.mimuw.edu.pl