1. SylabUZ
2. Faculty of Mathematics, Computer Science and Econometrics
3. winter term 2021/2022
4. Data Engineering - First-cycle studies leading to Engineer's degree
5. Algorithms and Data Structures 1

Generate PDF for this page

Algorithms and Data Structures 1 - course description

Aim of the course

Zdobycie przez studentów wiedzy i umiejętności w zakresie analizy algorytmów. Zapoznanie studentów z podstawowymi algorytmami przydatnymi w rozwiązywaniu problemów przetwarzania danych oraz sposobami ich implementacji w wybranych językach programowania.

Prerequisites

Save changes

Student powinien zaliczyć kurs: Podstawy logiki i analizy ilościowej, Podstawy programowania.

Scope

Wykład

1. Wprowadzenie: algorytmy, złożoność obliczeniowa i pamięciowa algorytmów, semantyczna poprawność algorytmu.
2. Asymptotyka: rzędy wielkości funkcji.
3. Algorytmy wyszukiwania: wyszukiwanie liniowe, binarne, interpolacyjne.
4. Podstawowe algorytmy sortowania: sortowanie przez prostą zamianę, sortowanie przez proste wstawianie, sortowanie przez proste wybieranie, sortowanie szybkie.
5. Podstawowe struktury danych: zmienne statyczne, tablice, rekordy, struktury dla macierzy trójkątnych i macierzy rzadkich, zmienne dynamiczne i dynamiczne struktury listowe.
6. Metody projektowania efektywnych algorytmów: rekurencja, zasada „dziel i zwyciężaj”, algorytmy zachłanne, programowanie dynamiczne.
7. Reprezentacje komputerowe grafów. 
8. Struktury danych dla zadań operujących na zbiorach: wektor charakterystyczny, haszowanie, drzewa poszukiwań binarnych.
9. Tekstowe struktury danych i algorytmy wyszukiwania wzorca. 
10. Algorytmy sortowania wewnętrznego i zewnętrznego. Algorytm szybkiej selekcji.
11. Szacowanie sum, rozwiązywanie równań rekurencyjnych.
12. Badanie poprawności algorytmów. Wyznaczanie złożoności obliczeniowej.
13. Rozwiązywanie problemów algorytmicznych.

Laboratorium

1. Tworzenie własnej biblioteki zwierającej podstawowe algorytmy na liczbach oraz algorytmy operujące na tablicach (generowanie, wstawianie i usuwanie elementów, przesuwanie cykliczne elementów tablicy).
2. Algorytmy wyszukiwania.
3. Algorytmy sortowania i selekcji.
4. Elementy programowania obiektowego. 
5. Wskaźniki i dynamiczne struktury danych.
6. Struktury danych dla zadań operujących na zbiorach.
7. Algorytmy tekstowe.  Programowanie operacji na plikach.

Teaching methods

Wykład: wykład problemowy.

Laboratorium: ćwiczenia laboratoryjne w pracowni komputerowej – analiza wybranych algorytmów, badanie ich złożoności obliczeniowej i poprawności semantycznej oraz przykłady ich zastosowania w zadaniach praktycznych.

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

Udział w zajęciach jest obowiązkowy.

Wykład. Egzamin pisemny weryfikujący efekty kształcenia w zakresie wiedzy i umiejętności.

Laboratorium. Ocena końcowa  jest wystawiana na podstawie punktów uzyskanych na zajęciach. Punkty uzyskuje się za: napisane na zajęciach sprawdziany, zrealizowane zadania implementacyjne, aktywność na zajęciach.

Na ocenę z przedmiotu składa się ocena z laboratorium (50%) oraz ocena z egzaminu (50%). Warunkiem przystąpienia do egzaminu jest pozytywna ocena z laboratorium. Warunkiem zaliczenia przedmiotu jest pozytywna ocena z egzaminu.

Recommended reading

1.        Aho A., Hopcroft J.E., Ullman J.D., : Projektowanie i analiza  algorytmów komputerowych, PWN, Warszawa 1983.  

2.        Aho A., Hopcroft J.E., Ullman J.D. : Data structures and algorithms.

3.        Banachowski L., Diks K.,  Rytter W., Algorytmy i struktury danych, WNT, W-wa 1996.

4.        Cormen T.H., Leiserson C.E., Rivest R.L., Wprowadzenie do algorytmów, WNT, W-wa 1997.

5.        Grębosz J. : Symfonia C++, Edition 2000, Kraków 2010.

6.        Kingsley-Hughes A. : Programowanie od podstaw, Helion, Gliwice 2005.

7.        Wirth N. : Algorithms and Data Structured, 1985.

Further reading

1.      Knuth D. : Sztuka programowania, t. 1-3, WNT, Warszawa 2001.

2.      Błażewicz  J. : Złożoność obliczeniowa    problemów  kombinatorycznych, WNT, Warszawa 1988.

3.      P. Wróblewski: Algorytmy, struktury danych i techniki programowania, wyd. II popr., Helion, 2001.

4.      Bloch J. : Java. Efektywne programowanie, Helion, Gliwice 2009.

Notes

Modified by dr Alina Szelecka (last modification: 05-05-2021 13:03)