SylabUZ

Wygeneruj PDF dla tej strony

Algorytmy i struktury danych - opis przedmiotu

Informacje ogólne
Nazwa przedmiotu Algorytmy i struktury danych
Kod przedmiotu 11.3-WK-MATP-ASD-L-S14_pNadGenGC85Q
Wydział Wydział Matematyki, Informatyki i Ekonometrii
Kierunek Mathematics
Profil ogólnoakademicki
Rodzaj studiów pierwszego stopnia z tyt. licencjata
Semestr rozpoczęcia semestr zimowy 2018/2019
Informacje o przedmiocie
Semestr 5
Liczba punktów ECTS do zdobycia 5
Typ przedmiotu obieralny
Język nauczania polski
Sylabus opracował
  • dr Florian Fabiś
Formy zajęć
Forma zajęć Liczba godzin w semestrze (stacjonarne) Liczba godzin w tygodniu (stacjonarne) Liczba godzin w semestrze (niestacjonarne) Liczba godzin w tygodniu (niestacjonarne) Forma zaliczenia
Laboratorium 30 2 - - Zaliczenie na ocenę
Wykład 30 2 - - Egzamin

Cel przedmiotu

The knowledge and skills in basics of analysis of algorithms. The knowledge of and ability to implement sorting and selection algorithms, searching algorithms and elementary graph algorithms. The knowledge of NP-completeness problem and its practical aspects.

Wymagania wstępne

Gaining of basic competences in analysis and linear algebra. Advanced computer operating skills. Skills in computer structured programming.

Zakres tematyczny

Lecture

1. Algorithms. Computational complexity of algorithms. Correctness of algorithms. Asymptotics. (4 h)

2. Techniques of constructing effective algorithms: divide and conquer , greedy methods, dynamic programming. (2 h)

3. Algorithms of sorting and searching. (4 h)

4. Data structures for dictionaries: characteristic vector, binary search trees, hashing. External searching - B-trees. The union problem for disjoint sets and its applications. (6 h)

5. Graph algorithms: computer representations of graphs, graph searching, minimum spanning trees, shortest paths in graphs, flows in networks. (4 h)

6. Text algorithms: pattern matching, suffix trees. (4 h)

7. Computational geometry: point localization, convex hull, sweeping. (4 h)

8. NP-completeness: the classes P, NP and NP-complete.

 

Laboratory
1. Determination of the computational complexity of algorithms. (4 h)
2. Testing of the correctness of algorithms. (4 h)
3. Algorithms of sorting and searching. (4 h)
4. Data structures for dictionaries. (6 h)
5. Graph algorithms. (6 h)
6. Text and computational geometry algorithms. (6 h)

Metody kształcenia

Lecture: problem lecture.
Laboratory: laboratory exercises in computer lab – implementation and testing of selected algorithms.
Each student is supposed to realize four projects during the semester. Each project will consist in implementation of the selected algorithm to solve a concrete practical task, writing a program for it, testing it and presenting a documentation in accordance with the assigned specification. On two out of the four projects the students will work in 2-3 person groups. Furthermore the students will write on classes programs implementing other algorithms.

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu Symbole efektów Metody weryfikacji Forma zajęć

Warunki zaliczenia

Lecture. Written examination verifying the education outcome in area of knowledge and skills.
Laboratory. Final grade is granted based on number of points received during studies. Points are received for written tests, active participation in classes and completed project.
Final course grade consists of laboratory classes’ grade (50%) and examination grade (50%). Positive grade from laboratory classes is the necessary condition for participation in examination. The positive grade from examination is the necessary condition for course completion.

Literatura podstawowa

1. Aho A., Hopcroft J.E., Ullman J.D., : Projektowanie i analiza algorytmów komputerowych, PWN, Warszawa 1983.
2. Banachowski L., Diks K., Rytter W., Algorytmy i struktury danych, WNT, W-wa 1996.
3. Cormen T.H., Leiserson C.E., Rivest R.L., Wprowadzenie do algorytmów, WNT, Warszawa 1997.

Literatura uzupełniająca

1. Aho A., Hopcroft J.E., Ullman J.D., : The Design and Analysis of Computer Algorithms.
2. Aho A., Hopcroft J.E., Ullman J.D., : Data structures and algorithms
3. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest: Introduction to Algorithms, 2001, MIT Press.
4. Knuth D. E. : The Art of Computer Programming.
5. N. Wirth: Algorithms and Data Structured, 1985.
6. Błażewicz J. : Złożoność obliczeniowa problemów kombinatorycznych, WNT, Warszawa 1988.
7. P. Wróblewski: Algorytmy, struktury danych i techniki programowania, wyd. II popr., Helion, 2001.

Uwagi


Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 07-07-2018 11:51)