Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Algorytmy i struktury danych
Tok studiów:
2019/2020
Kod:
IINF-1-204-n
Wydział:
Informatyki, Elektroniki i Telekomunikacji
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Informatyka
Semestr:
2
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma studiów:
Niestacjonarne
Strona www:
 
Prowadzący moduł:
dr inż. Gajęcki Marek (mag@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 Zna i rozumie podstawowe mechanizmy i techniki konstruowania algorytmów INF1A_W02 Egzamin
M_W002 Zna i rozumie podstawowe mechanizmy analizy algorytmów INF1A_W02 Egzamin
M_W003 Dysponuje wiedzą na temat złożonych struktur danych INF1A_W02 Egzamin
M_W004 Dysponuje wiedzą na podstawowych algorytmów INF1A_W02 Egzamin
Umiejętności: potrafi
M_U001 Potrafi rozwiązywać zadania algorytmiczne INF1A_U05 Kolokwium
M_U002 Potrafi stosować złożone struktury danych INF1A_U05 Kolokwium
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
32 16 16 0 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 Zna i rozumie podstawowe mechanizmy i techniki konstruowania algorytmów + - - - - - - - - - -
M_W002 Zna i rozumie podstawowe mechanizmy analizy algorytmów + - - - - - - - - - -
M_W003 Dysponuje wiedzą na temat złożonych struktur danych + - - - - - - - - - -
M_W004 Dysponuje wiedzą na podstawowych algorytmów + - - - - - - - - - -
Umiejętności
M_U001 Potrafi rozwiązywać zadania algorytmiczne - + - - - - - - - - -
M_U002 Potrafi stosować złożone struktury danych - + - - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 152 godz
Punkty ECTS za moduł 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 32 godz
przygotowanie projektu, prezentacji, pracy pisemnej, sprawozdania 40 godz
Samodzielne studiowanie tematyki zajęć 80 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 (16h):

1. Wprowadzenie do algorytmiki (2 godz.)
Analiza algorytmu. Złożoność obliczeniowa.

2. Algorytmy sortowania (6 godz.)
Podstawowe pojęcia. Klasyfikacja metod. Sortowania proste. Sortowania szybkie. Dolne ograniczenie złożoności sortowania. Sortowania liniowe. Mediany i statystyki pozycyjne.

3. Elementarne struktury danych (6 godz.)
Warstwa abstrakcji i warstwa implementacji. Elementarne struktury: tablica, lista odsyłaczowa, drzewa wskaźnikowe, stos, kolejka, kolejka priorytetowa, zbiór, zbiory rozłączne, kopiec, drzewa binarne, drzewa BST i ich warianty, lista z przeskokami, struktura słownikowa, B-drzewa.

5. Tablice z haszowaniem (2 godz.)
Funkcje mieszające. Metoda łańcuchowa rozwiązywania kolizji. Adresowanie otwarte i rozwiązywanie kolizji poprzez adresowanie liniowe, mieszanie wielokrotne. Reorganizacja tablic z haszowaniem.

6. Elementarne techniki algorytmiczne (6 godz.)
Metoda dziel i zwyciężaj. Algorytmy zachłanne. Programowanie dynamiczne.

7. Grafy (8 godz.)
Podstawowe definicje. Reprezentacja w pamięci. Grafy skierowane i nieskierowane. Przeszukiwania grafu w głąb i wszerz. Złożoność przeszukiwań. Algorytmy grafowe.

Ćwiczenia audytoryjne (16h):

1. Proste metody sortowania (3 godz.)
2. Sortowania szybkie i liniowe (3 godz.)
3. Elementarne struktury danych (6 godz.)
4. Tablice z haszowaniem (2 godz.)
5. Algorytmy zachłanne (3 godz.)
6. Programowanie dynamiczne (5 godz.)
7. Implementacja i przeszukiwanie grafów (2 godz.)
8. Algorytmy grafowe (6 godz.)

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 audytoryjne: Podczas zajęć audytoryjnych studenci na tablicy rozwiązują zadane wcześniej problemy. Prowadzący na bieżąco dokonuje stosowanych wyjaśnień i moderuje dyskusję z grupą nad danym problemem.
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 audytoryjne:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci przystępując do ćwiczeń są zobowiązani do przygotowania się w zakresie wskazanym każdorazowo przez prowadzącego (np. w formie zestawów zadań). Ocena pracy studenta może bazować na wypowiedziach ustnych lub pisemnych w formie kolokwium, co zgodnie z regulaminem studiów AGH przekłada się na ocenę końcową z tej formy zajęć.
Sposób obliczania oceny końcowej:

Ocena dla studentów, którzy otrzymali pozytywną ocenę z ćwiczeń © oraz egzaminu (E) w odpowiednich pierwszych terminach, ocena końcowa wynosi max((C+E)/2, 3.5). (Jeśli (C+E)/2 nie jest regulaminową oceną, to ocena zaokrąglana jest w strone korzystniejszą dla studenta).

Jeśli któraś z ocen (C lub E) została zdobyta w terminie późniejszym, to ocena końcowa wynosi nie więcej niż 3.0.

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 :

Znajomość matematyki (systemy pozycyjne, kombinatoryka, logarytmy, itp.)
Podstawowa znajomość programowania w C.

Zalecana literatura i pomoce naukowe:
  1. „Wprowadzenie do algorytmów” Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wydawnictwo Naukowe PWN, 2012.
  2. „Algorytmy” R. Sedgewick, K. Wayne, Helion 2012.
  3. „Algorytmy” S. Dasgupta, C. Papadimitriou, U. Vazirani, Wydawnictwa Naukowe PWN 2010.
Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

Nie podano dodatkowych publikacji

Informacje dodatkowe:

Brak