Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Analiza algorytmów
Tok studiów:
2018/2019
Kod:
JIS-2-021-GK-s
Wydział:
Fizyki i Informatyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Grafika komputerowa i przetwarzanie obrazów
Kierunek:
Informatyka Stosowana
Semestr:
0
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Osoba odpowiedzialna:
dr hab. inż. Gawroński Przemysław (gawron@newton.ftj.agh.edu.pl)
Osoby prowadzące:
dr hab. inż. Gawroński Przemysław (gawron@newton.ftj.agh.edu.pl)
Krótka charakterystyka modułu

Doświadczalna analiza czasowej złożoności obliczeniowej algorytmów; grafowych, wyszukiwania wzorca, rozwiązujących problemy NP-zupełne, wykorzystujących metody Monte Carlo i Las Vegas.

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W001 Student zna metody praktycznej analizy złożoności obliczeniowej i poprawności algorytmów. IS2A_W03 Prezentacja,
Aktywność na zajęciach,
Udział w dyskusji,
Wykonanie projektu
M_W002 Student zna pojęcie NP-zupełności. IS2A_W03 Prezentacja,
Projekt,
Udział w dyskusji,
Wykonanie projektu
Umiejętności
M_U001 Student potrafi zaproponować i zaimplemementować  rozwiązanie problemu NP-zupełnego. IS2A_U01, IS2A_U04 Prezentacja,
Projekt,
Udział w dyskusji,
Wykonanie projektu
M_U002 Student ptrafi praktycznie zbadać złożonośc obliczeniowa problemu algorytmicznego. IS2A_U01 Prezentacja,
Projekt
Kompetencje społeczne
M_K001 Student potrafi w sposób przejrzysty zaprezentować wyniki analizy problemu algorytmicznego. IS2A_K03 Aktywność na zajęciach,
Prezentacja,
Wykonanie projektu,
Udział w dyskusji
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W001 Student zna metody praktycznej analizy złożoności obliczeniowej i poprawności algorytmów. - - - + - + - - - - -
M_W002 Student zna pojęcie NP-zupełności. - - - + - + - - - - -
Umiejętności
M_U001 Student potrafi zaproponować i zaimplemementować  rozwiązanie problemu NP-zupełnego. - - - + - + - - - - -
M_U002 Student ptrafi praktycznie zbadać złożonośc obliczeniowa problemu algorytmicznego. - - - + - + - - - - -
Kompetencje społeczne
M_K001 Student potrafi w sposób przejrzysty zaprezentować wyniki analizy problemu algorytmicznego. - - - + - + - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Ćwiczenia projektowe:

Studenci w dwuosobowych zespołach będą analizować i implementować rozwiązania dwóch wybranych problemów algorytmicznych, z których jeden będzie z grupy problemów NP-zupełnych.

Przykładowe zadania projektowe:

1. Problem wyszukiwanie wzorca: algorytm Knutha-Morrisa-Prata, automat skończony, algorytm Karpa-Rabina.

2. Algorytmy teorioliczbowe: system kryptograficzny RSA, algorytmy generacji liczb pierwszych, algorytmy rozkłady na czynniki pierwsze.

3. Algorytmy randomizowane: metoda Monte Carlo, metoda Las Vegas.

4. Algorytmy grafowe: algorytm Floyda-Warshalla, algorytm Johnsona, algorytm Forda-Fulkersona, algorytm Edmondsa-Karpa,

5. Programowanie liniowe, algorytm sympleks.

6. Problemy NP-zupełne: cykl Hamiltona, problem kliki, problem komiwojażera, problem kolorowania grafu, problemy podziału zbioru, problemy pokrycia, gry i układanki.

7. Algorytmy aproksymacyjne.

Efekty kształcenia:
- student potrafi zebrać informacje potrzebne do realizacji projektu.
- student potrafi zaimplementować rozwiązanie problemu algorytmicznego i zebrać dane do analizy złożoności obliczeniowej.
- student potrafi pracować w zespole dwuosobowym nad wykonaniem projektu.

Zajęcia seminaryjne:

W trakcie zajęć seminaryjnych studenci będą prezentować wyniki analizy wybranych dwóch problemów algorytmicznych zaimplementowanych w ramach zajęć projektowych.

Efekty kształcenia:
- student umie przygotować rozwiązanie wybranego problemu algorytmicznego.
- student potrafi przygotować i przedstawić wyniki analizy złożoności obliczeniowej danego problemu algorytmicznego.

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 78 godz
Punkty ECTS za moduł 3 ECTS
Udział w ćwiczeniach projektowych 30 godz
Udział w zajęciach seminaryjnych 15 godz
Wykonanie projektu 28 godz
Przygotowanie sprawozdania, pracy pisemnej, prezentacji, itp. 5 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

Ocena końcowa obliczana jest na podstawie wzoru:0.6 x ocena z projektu + 0.4 x ocena z seminarium.

Oceny ustalane będą zgodnie ze skalą ocen obowiązującą w regulaminie AGH, przyporządkowującą procent opanowania materiału konkretnej ocenie.

Wymagania wstępne i dodatkowe:

Znajomość podstawowych algorytmów i struktur danych, dobra znajomość jezyka C lub C++, Java.

Zalecana literatura i pomoce naukowe:

1. Jon Kleinberg, Éva Tardos, Algorithm Design, ISBN-10: 0321295358
2. Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Introduction to Algorithms, ISBN-10: 0262033844
3. Steven S. Skiena, The algorithm design Manual, ISBN 0-387-94860-0
4. Jeff Edmonds, How to Think About Algorithms, ISBN 9780521614108
5. Anany Levitin, Introduction to the Design and Analysis of Algorithms, ISBN 0132316811

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:
  • F. Hassanibesheli, L. Hedayatifar, P. Gawronski, M. Stojkow, D. Żuchowska-Skiba, Krzysztof Kułakowski, Gain and loss of esteem, direct reciprocity and Heider balance, Physica A, 268 (2017), 334
  • P. Gawroński, M. J. Krawczyk, K. Kułakowski, Emerging communities in networks -
    a flow of ties, Acta Phys. Pol. B, 46, (2015), 911.
  • P. Gawroński, M. Nawojczyk, and K. Kułakowski, Opinion formation in an open sys-
    tem and the spiral of silence, Acta Phys. Pol. A, 127, (2015), A-45.
  • P. Gawroński, K. Malarz, M. J. Krawczyk, J. Malinowski, A. Kupczak, W. Sikora, K.
    Kułakowski, J. Wąs, and J.W. Kantelhardt, Strategies in crowd and crowd structure,
    Acta Phys. Pol. A, 123, (2013), 522.
  • A. Jarynowski, P. Gawroński, K. Kułakowski, How the competitive altruism leads to
    bistable homogeneous states of cooperation or defection, Lecture Notes in Computer
    Science, 7204 (2012) 543.
  • P. Gawroński, K. Kułakowski, M. Kampf and J. W. Kantelhardt, Evacuation in the
    Social Force Model is not stationary, Acta Phys. Pol. A, 121, (2012), B-77.
  • P. Gawroński, K. Kułakowski, Crowd dynamics – being stuck, Comp. Phys. Comm., 9,
    (2011), 1924.
  • P. Gawroński, K. Saeed, K. Kułakowski, Early warning of cardiac problems in crowd,
    Lect. Notes Artif. Int., 6071, (2010), 220
  • K. Kułakowski, P. Gawroński, To cooperate or to defect? Altruism and reputation,
    Phys. A, 388, (2009), 3581
  • P. Gawroński and K. Kułakowski, A numerical trip to social psychology: long-living
    states of cognitive dissonance, Lect. Notes in Computer Science, 4490, (2007), 43
  • P. Gawroński and K. Kułakowski, Heider balance in human networks, Proceedings of
    8th Granada Seminar, Eds. P. Garrido, J. Marro and M. A. Munoz, AIP Conf. Proc.
    779, Melville, NY, (2005) 93
  • P. Gawroński, P. Gronek, K. Kułakowski, The Heider balance and social distance, Acta
    Phys. Pol. B., 36, (2005), 2549
  • K. Kułakowski, P. Gawroński, P. Gronek, The Heider balance – a continuous approach,
    Int. J. Mod. Phys. C, 16, (2005), 707
Informacje dodatkowe:

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

Nieobecność na zajęciach wymaga od studenta samodzielnego opanowania przerabianego na tych zajęciach materiału i jego zaliczenia w formie ustnej/pisemnej w wyznaczonym przez prowadzącego terminie. Student który bez usprawiedliwienia opuścił więcej niż 2 zajęcia może zostać pozbawiony, przez prowadzącego zajęcia, możliwości wyrównania zaległości.