1. SylabUZ
2. Wydział Matematyki, Informatyki i Ekonometrii
3. semestr zimowy 2016/2017
4. Inżynieria danych - pierwszego stopnia
5. Algorytmy i struktury danych 1

Wygeneruj PDF dla tej strony

Algorytmy i struktury danych 1 - opis przedmiotu

Cel przedmiotu

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.

Wymagania wstępne

Zapisz zmiany

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

Zakres tematyczny

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.

Metody kształcenia

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.

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

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

Warunki zaliczenia

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.

Literatura podstawowa

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.

Literatura uzupełniająca

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.

Uwagi

Zmodyfikowane przez dr Robert Dylewski, prof. UZ (ostatnia modyfikacja: 05-10-2016 20:58)