Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Algorytmy i struktury danych
Tok studiów:
2015/2016
Kod:
BIT-1-201-s
Wydział:
Geologii, Geofizyki i Ochrony Środowiska
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
Strona www:
 
Osoba odpowiedzialna:
dr Bielecka Marzena (bielecka@agh.edu.pl)
Osoby prowadzące:
dr Bielecka Marzena (bielecka@agh.edu.pl)
Krótka charakterystyka modułu

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 rozumie znaczenie złożoności czasowej i pamięciowej oraz ma podstawową wiedzę dotyczącą poprawności semantycznej algorytmów. IT1A_W04, IT1A_W16 Kolokwium
M_W002 Student zna podstawowe algorytmy sortowania i algorytmy grafowe. IT1A_W06, IT1A_W11 Kolokwium,
Wykonanie ćwiczeń laboratoryjnych
M_W003 Student dobiera odpowiednie struktur danych dla podstawowych algorytmów IT1A_W09, IT1A_W11 Kolokwium,
Projekt
Umiejętności
M_U001 Student potrafi zaprojektować prosty algorytm wykorzystując różne struktury danych. IT1A_U13, IT1A_U15 Kolokwium,
Projekt
M_U002 Student potrafi rozwiązywać szeroką klasę równań rekurencyjnych. IT1A_U01, IT1A_U16 Kolokwium
M_U003 Student potrafi oszacować złożoność obliczeniową różnych algorytmów i zbadać ich poprawność semantyczną. IT1A_U16, IT1A_U10 Kolokwium
Kompetencje społeczne
M_K001 Student posiada umiejętność współpracy i posiada zdolność do samokształcenia IT1A_K03, IT1A_K01 Projekt
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 rozumie znaczenie złożoności czasowej i pamięciowej oraz ma podstawową wiedzę dotyczącą poprawności semantycznej algorytmów. + + - - - - - - - - -
M_W002 Student zna podstawowe algorytmy sortowania i algorytmy grafowe. + + - - - - - - - - -
M_W003 Student dobiera odpowiednie struktur danych dla podstawowych algorytmów + + - - - - - - - - -
Umiejętności
M_U001 Student potrafi zaprojektować prosty algorytm wykorzystując różne struktury danych. + + - - - - - - - - -
M_U002 Student potrafi rozwiązywać szeroką klasę równań rekurencyjnych. + + - - - - - - - - -
M_U003 Student potrafi oszacować złożoność obliczeniową różnych algorytmów i zbadać ich poprawność semantyczną. + + - - - - - - - - -
Kompetencje społeczne
M_K001 Student posiada umiejętność współpracy i posiada zdolność do samokształcenia - + - - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:

1. Analiza algorytmu. Rekurencja. Twierdzenie o zamianie procedury rekurencyjnej na iteracyjną.
2. Klasyfikacja struktur danych. Dynamiczne struktury danych takie jak listy jednokierunkowe, cykliczne, dwukierunkowe. Abstrakcyjne struktury danych.
3. Poprawność semantyczna algorytmu.
4. Złożoność obliczeniowa-podstawowe definicje. Klasy złożoności obliczeniowej. Rozwiązywanie równań rekurencyjnych metodą zmiany zmiennych.
5. Metody rozwiązywania równań rekurencyjnych. Twierdzenie o rekursji uniwersalnej.
6. Analiza algorytmów sortowania (sortowania proste, quicksort, mergesort, wyznaczanie k-tego elementu w ciągu). Sortowania liniowe. Ograniczenie dolne złożoności obliczeniowej dla sortowania przez porównanie.
7. Grafy – metody implementacji. Przeszukiwanie grafów w głąb, wszerz. Sortowanie topologiczne. Algorytm Dijkstry i Primy.
8. Znajdowanie w grafie cyklu Eulera i Hamiltona. Algorytmy przybliżone.
9. Drzewa binarne, BST, AVL i kopce. Sortowanie przez kopcowanie.
10. Mieszanie. Problem wyboru funkcji mieszającej. Struktury danych stosowane do rozwiązywania problemu kolizji.
11. Algorytmy geometryczne.

Ćwiczenia audytoryjne:

1. Analiza algorytmu. Rekurencja. Twierdzenie o zamianie procedury rekurencyjnej na iteracyjną.
2. Klasyfikacja struktur danych. Dynamiczne struktury danych takie jak listy jednokierunkowe, cykliczne, dwukierunkowe. Abstrakcyjne struktury danych.
3. Poprawność semantyczna algorytmu.
4. Złożoność obliczeniowa-podstawowe definicje. Klasy złożoności obliczeniowej. Rozwiązywanie równań rekurencyjnych metodą zmiany zmiennych.
5. Metody rozwiązywania równań rekurencyjnych. Twierdzenie o rekursji uniwersalnej.
6. Analiza algorytmów sortowania (sortowania proste, quicksort, mergesort, wyznaczanie k-tego elementu w ciągu). Sortowania liniowe. Ograniczenie dolne złożoności obliczeniowej dla sortowania przez porównanie.
7. Grafy – metody implementacji. Przeszukiwanie grafów w głąb, wszerz. Sortowanie topologiczne. Algorytm Dijkstry i Primy.
8. Znajdowanie w grafie cyklu Eulera i Hamiltona. Algorytmy przybliżone.
9. Drzewa binarne, BST, AVL i kopce. Sortowanie przez kopcowanie.
10. Mieszanie. Problem wyboru funkcji mieszającej. Struktury danych stosowane do rozwiązywania problemu kolizji.
11. Algorytmy geometryczne.

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 82 godz
Punkty ECTS za moduł 3 ECTS
Udział w wykładach 28 godz
Samodzielne studiowanie tematyki zajęć 20 godz
Udział w ćwiczeniach audytoryjnych 14 godz
Przygotowanie do zajęć 20 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

Ocena końcowa = 50% oceny z testu + 50% oceny z ćwiczeń
(lub Ocena końcowa odpowiada ocenie z zaliczenia)

Wymagania wstępne i dodatkowe:

Nie podano wymagań wstępnych lub dodatkowych.

Zalecana literatura i pomoce naukowe:

L. Banachowski, K. Diks, W.Rytter „Algorytmy i struktury danych”
T.H. Cormen „Wprowadzenie do algorytmów”
N.Wirth, Algorytmy + Struktury Danych = Programy
Aho, Ullman, Wykłady z Informatyki z przykładami w języku C

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

Nie podano dodatkowych publikacji

Informacje dodatkowe:

Rowiązywanie trudniejszych problemów nie jest obowiązkowe (wymagają dodatkowego nakładu czasu i ponadprogramowej wiedzy). Studenci, którzy się podejmują ich rozwiązania, otrzymują dodatkowe punkty

udział „teoretycznych” punktów ECTS: 4