SylabUZ

Wygeneruj PDF dla tej strony

Algorytmy i struktury danych 1 - opis przedmiotu

Informacje ogólne
Nazwa przedmiotu Algorytmy i struktury danych 1
Kod przedmiotu 11.3-WK-IDP-ASD1-W-S14_pNadGenYL8HR
Wydział Wydział Matematyki, Informatyki i Ekonometrii
Kierunek Inżynieria danych
Profil ogólnoakademicki
Rodzaj studiów pierwszego stopnia z tyt. inżyniera
Semestr rozpoczęcia semestr zimowy 2017/2018
Informacje o przedmiocie
Semestr 2
Liczba punktów ECTS do zdobycia 5
Typ przedmiotu obowiązkowy
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
Wykład 30 2 - - Egzamin
Laboratorium 30 2 - - Zaliczenie na ocenę

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

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 kształcenia i metody weryfikacji osiągania efektów kształcenia

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.

Obciążenie pracą

Obciążenie pracą Studia stacjonarne
(w godz.)
Studia niestacjonarne
(w godz.)
Godziny kontaktowe (udział w zajęciach; konsultacjach; egzaminie, itp.) 75 -
Samodzielna praca studenta (przygotowanie do: zajęć, kolokwium, egzaminu; studiowanie literatury przygotowanie: pracy pisemnej, projektu, prezentacji, raportu, wystąpienia; itp.) 50 -
Łącznie 125 -
Punkty ECTS Studia stacjonarne Studia niestacjonarne
Zajęcia z udziałem nauczyciela akademickiego 3 -
Zajęcia bez udziału nauczyciela akademickiego 2 -
Łącznie 5 -

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 (ostatnia modyfikacja: 09-04-2017 16:27)