Module also offered within study programmes:
General information:
Name:
Algorytmy i struktury danych
Course of study:
2015/2016
Code:
BIT-1-201-s
Faculty of:
Geology, Geophysics and Environmental Protection
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
Course homepage:
 
Responsible teacher:
dr Bielecka Marzena (bielecka@agh.edu.pl)
Academic teachers:
dr Bielecka Marzena (bielecka@agh.edu.pl)
Module summary

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 posiada umiejętność współpracy i posiada zdolność do samokształcenia IT1A_K03, IT1A_K01 Project
Skills
M_U001 Student potrafi zaprojektować prosty algorytm wykorzystując różne struktury danych. IT1A_U13, IT1A_U15 Test,
Project
M_U002 Student potrafi rozwiązywać szeroką klasę równań rekurencyjnych. IT1A_U01, IT1A_U16 Test
M_U003 Student potrafi oszacować złożoność obliczeniową różnych algorytmów i zbadać ich poprawność semantyczną. IT1A_U16, IT1A_U10 Test
Knowledge
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 Test
M_W002 Student zna podstawowe algorytmy sortowania i algorytmy grafowe. IT1A_W06, IT1A_W11 Test,
Execution of laboratory classes
M_W003 Student dobiera odpowiednie struktur danych dla podstawowych algorytmów IT1A_W09, IT1A_W11 Test,
Project
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 posiada umiejętność współpracy i posiada zdolność do samokształcenia - + - - - - - - - - -
Skills
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ą. + + - - - - - - - - -
Knowledge
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 + + - - - - - - - - -
Module content
Lectures:

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.

Auditorium classes:

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.

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 82 h
Module ECTS credits 3 ECTS
Participation in lectures 28 h
Realization of independently performed tasks 20 h
Participation in auditorium classes 14 h
Preparation for classes 20 h
Additional information
Method of calculating the final grade:

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

Prerequisites and additional requirements:

Prerequisites and additional requirements not specified

Recommended literature and teaching resources:

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

Scientific publications of module course instructors related to the topic of the module:

Additional scientific publications not specified

Additional information:

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