Module also offered within study programmes:
General information:
Name:
Algorithms and Data Processing
Course of study:
2018/2019
Code:
JIS-1-203-s
Faculty of:
Physics and Applied Computer Science
Study level:
First-cycle studies
Specialty:
-
Field of study:
Applied Computer Science
Semester:
2
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Responsible teacher:
dr hab. inż. Gawroński Przemysław (gawron@newton.ftj.agh.edu.pl)
Academic teachers:
dr hab. inż. Gawroński Przemysław (gawron@newton.ftj.agh.edu.pl)
Module summary

Praktyczna prezentacja podstawowych algorytmów i struktur danych z uwzględnieniem wybranych metod analizy czasowej złożoności obliczeniowej i poprawności algorytmów.

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence
M_K001 Student potrafi w sposób przejrzysty zaprezentować rozwiązanie problemu algorytmicznego. IS1A_K01 Activity during classes,
Participation in a discussion,
Execution of exercises,
Examination
Skills
M_U001 Student potrafi wykorzystać podstawowe metody konstrukcji algorytmów do rozwiązywania praktycznych problemów programistycznych. IS1A_U06, IS1A_U01, IS1A_U04 Activity during classes,
Test,
Execution of exercises,
Examination
M_U002 Student potrafi określić złożoność obliczeniową algorytmów iteracyjnych i rekurencyjnych. IS1A_U06, IS1A_U05, IS1A_U01 Activity during classes,
Test,
Execution of exercises,
Examination
Knowledge
M_W001 Student zna podstawowe algorytmy i struktury danych. IS1A_W03, IS1A_W02 Activity during classes,
Participation in a discussion,
Examination
M_W002 Student zna i rozumie metody analizy czasowej złożoności obliczeniowej i poprawności algorytmów. IS1A_W03, IS1A_W02 Activity during classes,
Participation in a discussion,
Examination
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Others
E-learning
Social competence
M_K001 Student potrafi w sposób przejrzysty zaprezentować rozwiązanie problemu algorytmicznego. - + - - - - - - - - -
Skills
M_U001 Student potrafi wykorzystać podstawowe metody konstrukcji algorytmów do rozwiązywania praktycznych problemów programistycznych. + + - - - - - - - - -
M_U002 Student potrafi określić złożoność obliczeniową algorytmów iteracyjnych i rekurencyjnych. + + - - - - - - - - -
Knowledge
M_W001 Student zna podstawowe algorytmy i struktury danych. + - - - - - - - - - -
M_W002 Student zna i rozumie metody analizy czasowej złożoności obliczeniowej i poprawności algorytmów. + - - - - - - - - - -
Module content
Lectures:
  1. Wprowadzenie do analizy algorytmów

    Czasowa złożoność obliczeniowa, notacja asymptotyczna, niezmiennik pętli, iteracja, rekurencja, drzewa rekursji, twierdzenie o rekurencji uniwersalnej.

  2. Przegląd i analiza algorytmów sortowania

    Sortowanie przez wstawianie, sortowanie przez scalanie, sortowanie przez kopcowanie, sortowanie szybkie, sortowanie przez zliczanie.

  3. Przegląd i analiza podstawowych metod konstrukcji algorytmów

    Metoda dziel i zwyciężaj, programowanie dynamicznie, algorytmy zachłanne, algorytmy z powrotami.

  4. Abstrakcyjne typy danych

    Tablica, tablica z haszowaniem, lista, kolejka, stos, kopiec, drzewo, drzewo poszukiwań binarnych, drzewo czerwono- czarne.

  5. Przegląd i analiza podstawowych algorytmów grafowych

    Reprezentacja grafów, przeszukiwanie wszerz, przeszukiwanie w głąb, minimalne drzewo rozpinające, algorytmy Kruskala i Prima, najkrótsze ścieżki z jednym źródłem algorytm Bellmana-Forda, algorytm Dijkstry.

Auditorium classes:
  1. Wprowadzenie do analizy algorytmów

    - student potrafi użyć notacji asymptotycznej do określenia złożoności obliczeniowej algorytmów iteracyjnych i rekurencyjnych,
    - student potrafi określić niezmiennik pętli algorytmu,
    - student potrafi stworzyć drzewo rekursji dla wywołań algorytmu rekurencyjnego,
    - student potrafi zastosować twierdzenie o rekurencji uniwersalnej do określenia czasowej złożoności obliczeniowej algorytmu rekurencyjnego,

  2. Przegląd i analiza algorytmów sortowania

    - student potrafi zapisać w pseudokodzie podstawowe algorytmy sortowania,
    - student potrafi określić złożoność obliczeniową podstawowych algorytmów sortowania.
    - student potrafi korzystając z niezmiennika pętli udowodnić poprawność podstawowych algorytmów sortowania,

  3. Przegląd i analiza podstawowych metod konstrukcji algorytmów

    - student potrafi skonstruować algorytm wykorzystując metodę dziel i zwyciężaj,
    - student potrafi skonstruować algorytm wykorzystując metodę algorytmy z powrotami,
    - student potrafi poprawić złożoność obliczeniową wybranych algorytmów przez wykorzystanie programowania dynamicznego lub algorytmów zachłannych,
    - student potrafi skonstruować iteracyjną postać prostych algorytmów rekurencyjnych,

  4. Abstrakcyjne typy danych

    - student potrafi wykorzystać do rozwiązywania zadań algorytmicznych podstawowe abstrakcyjne struktury danych,
    - student potrafi wykorzystać w konstrukcji algorytmów kolejkę priorytetową,
    - student potrafi utworzyć zrównoważone drzewo poszukiwań binarnych,

  5. Przegląd i analiza podstawowych algorytmów grafowych

    - student potrafi utworzyć macierzową i listową reprezentację grafu skierowanego i niekierowanego.
    - student potrafi dokonać przeszukiwanie grafu wszerz oraz w głąb,
    - student potrafi dla danego grafu utworzyć minimalne drzewo rozpinające,
    - student potrafi dla danego grafu wyszukać najkrótsze ścieżki z jednym źródłem,

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 150 h
Module ECTS credits 6 ECTS
Participation in lectures 30 h
Realization of independently performed tasks 22 h
Participation in auditorium classes 30 h
Preparation for classes 66 h
Examination or Final test 2 h
Additional information
Method of calculating the final grade:

Ocena końcowa obliczana jest jako średnia ważona ocen z egzaminu (E) i z ćwiczeń audytoryjnych ©:
OK = 0.5 x E + 0.5 x C.

Ocena z ćwiczeń obliczana jest jako średnia ważona ocen z aktywności studentów na zajęciach (A) i z dwóch kolokwiów (K):
OK = 0.4 x A + 0.6 x K

Ocena z ćwiczeń rachunkowych ustalana będzie zgodnie ze skalą ocen obowiązującą w regulaminie AGH, przyporządkowującą procent opanowania materiału konkretnej ocenie.

Prerequisites and additional requirements:

Prerequisites and additional requirements not specified

Recommended literature and teaching resources:
  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wprowadzenie do algorytmów, ISBN 83-204-3149-2
  2. Richard Neapolitan, Kumarss Naimipour, Podstawy algorytmów z przykładami w C++, ISBN 83-7361-429-X
  3. Kyle Loudon, Algorytmy w C, ISBN 83-7197–912-6
  4. Richard Johnsonbaugh, Marcus Schaefer, Algorithms, ISBN 0-13-122853-6
  5. Steven S. Skiena, The algorithm design Manual, ISBN 0-387-94860-0
Scientific publications of module course instructors related to the topic of the module:
  • 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
Additional information:

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

ćwiczenia audytoryjnych: Nieobecność na jednych ćwiczeniach zajęciach wymaga od studenta samodzielnego opanowania przerabianego na tych zajęciach materiału. Nieobecność na więcej niż jednych ćwiczeniach wymaga od studenta samodzielnego opanowania przerabianego na tych zajęciach materiału i jego zaliczenia w formie pisemnej w wyznaczonym przez prowadzącego terminie lecz nie później jak w ostatnim tygodniu trwania zajęć. Student który bez usprawiedliwienia opuścił więcej niż dwa ćwiczenia i jego cząstkowe wyniki w nauce były negatywne może zostać pozbawiony, przez prowadzącego zajęcia, możliwości wyrównania zaległości.
Obecność na wykładzie: zgodnie z Regulaminem Studiów AGH.

Zasady zaliczania zajęć:

ćwiczenia audytoryjne: Podstawowym terminem uzyskania zaliczenia jest koniec zajęć w danym semestrze. Student może dwukrotnie przystąpić do poprawkowego zaliczania.
Student który bez usprawiedliwienia opuścił więcej niż dwa zajęcia i jego cząstkowe wyniki w nauce były negatywne może zostać pozbawiony, przez prowadzącego zajęcia, możliwości poprawkowego zaliczania zajęć. Od takiej decyzji prowadzącego zajęcia student może się odwołać do prowadzącego przedmiot (moduł) lub Dziekana.

Warunkiem przystąpienie do egzaminu jest wcześniejsze uzyskanie zaliczenia z ćwiczeń laboratoryjnych.