Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Algorytmy i struktury danych
Tok studiów:
2018/2019
Kod:
JIS-1-203-s
Wydział:
Fizyki i Informatyki Stosowanej
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Informatyka Stosowana
Semestr:
2
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

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.

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 podstawowe algorytmy i struktury danych. IS1A_W03, IS1A_W02 Aktywność na zajęciach,
Udział w dyskusji,
Egzamin
M_W002 Student zna i rozumie metody analizy czasowej złożoności obliczeniowej i poprawności algorytmów. IS1A_W03, IS1A_W02 Aktywność na zajęciach,
Udział w dyskusji,
Egzamin
Umiejętności
M_U001 Student potrafi wykorzystać podstawowe metody konstrukcji algorytmów do rozwiązywania praktycznych problemów programistycznych. IS1A_U06, IS1A_U01, IS1A_U04 Aktywność na zajęciach,
Kolokwium,
Wykonanie ćwiczeń,
Egzamin
M_U002 Student potrafi określić złożoność obliczeniową algorytmów iteracyjnych i rekurencyjnych. IS1A_U06, IS1A_U05, IS1A_U01 Aktywność na zajęciach,
Kolokwium,
Wykonanie ćwiczeń,
Egzamin
Kompetencje społeczne
M_K001 Student potrafi w sposób przejrzysty zaprezentować rozwiązanie problemu algorytmicznego. IS1A_K01 Aktywność na zajęciach,
Udział w dyskusji,
Wykonanie ćwiczeń,
Egzamin
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 podstawowe algorytmy i struktury danych. + - - - - - - - - - -
M_W002 Student zna i rozumie metody analizy czasowej złożoności obliczeniowej i poprawności algorytmów. + - - - - - - - - - -
Umiejętności
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. + + - - - - - - - - -
Kompetencje społeczne
M_K001 Student potrafi w sposób przejrzysty zaprezentować rozwiązanie problemu algorytmicznego. - + - - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:
  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.

Ćwiczenia audytoryjne:
  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,

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 150 godz
Punkty ECTS za moduł 6 ECTS
Udział w wykładach 30 godz
Samodzielne studiowanie tematyki zajęć 22 godz
Udział w ćwiczeniach audytoryjnych 30 godz
Przygotowanie do zajęć 66 godz
Egzamin lub kolokwium zaliczeniowe 2 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

1. 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.

2. W semestrze odbędzie się sześć 15 minutowych kolokwiów z materiału uprzednio przerobionego na ćwiczeniach i wykładach.

3. Ocena z ćwiczeń obliczana jest jako średnia ważona ocen z aktywności studentów na zajęciach (A) i kolokwiów (K): C = 0.4 x A + 0.6 x (K1+K2+K3+K4+K5+K6)/6

4. 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.

Wymagania wstępne i dodatkowe:

Nie podano wymagań wstępnych lub dodatkowych.

Zalecana literatura i pomoce naukowe:
  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
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:

Ćwiczenia audytoryjne:
Nieobecność na jednych zajęciach obowiązkowych wymaga od studenta samodzielnego opanowania przerabianego na tych zajęciach materiału. Nieobecność na więcej niż jednych zajęciach wymaga od studenta samodzielnego opanowania przerabianego na tych zajęciach materiału i jego zaliczenia w formie i terminie wyznaczonym przez prowadzącego, lecz nie później niż w ostatnim tygodniu trwania zajęć.

Student, który bez usprawiedliwienia opuścił więcej niż dwa obowiązkowe zajęcia i jego
cząstkowe wyniki w nauce były negatywne może nie zaliczyć zajęć obowiązkowych. Należy pamiętać, że warunkiem przystąpienie do egzaminu jest wcześniejsze uzyskanie zaliczenia z zajęć obowiązkowych.
Obecność na wykładzie: zgodnie z Regulaminem Studiów AGH.

Zasady zaliczania ćwiczeń audytoryjnych:
Podstawowym terminem uzyskania zaliczenia jest koniec zajęć w danym semestrze.
W przypadku braku zaliczenia w terminie podstawowym Student może uzyskać je poprawiając oceny z dwóch kolokwiów z materiału uzgodnionego z prowadzącym.