Akademia Finansów i Biznesu Vistula - Centralny System Uwierzytelniania
Strona główna

Algorytmy i złożoność

Informacje ogólne

Kod przedmiotu: CII3SP11CI-Z17
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Algorytmy i złożoność
Jednostka: Akademia Finansów i Biznesu Vistula
Grupy:
Punkty ECTS i inne: 7.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.
Język prowadzenia: polski
Skrócony opis:

1) Dostarczenie studentom podstawowej wiedzy z zakresu:

• analizy algorytmów i struktur danych,

• technik stosowanych przy określanie złożoności obliczeniowej algorytmów

• znajomości podstawowych algorytmów dla różnych obszarów zastosowań,

2) Ukształtowanie podstawowych umiejętności w zakresie:

• szacowania złożoności obliczeniowej algorytmów (czasowej i pamięciowej) w odniesieniu do statycznych i dynamicznych struktur danych,

• konstruowania i stosowania algorytmów w takich obszarach jak: sortowanie, wyszukiwanie, metody numeryczne, działanie na tekstach, zastosowania grafów,

• umiejętności zaprojektowania aplikacji (w języku CSharp) dla pomiaru (eksperymentalnego) złożoności obliczeniowej algorytmu i przedstawienie wyników w formie tabelarycznej i w formie wykresu (funkcji rozmiaru zadania),

3) Utwierdzenie studentów w potrzebie systematycznego rozwijania swoich umiejętności w zakresie analizy złożoności obliczeniowej algorytmów.

Pełny opis:

Wykłady:

1. Wprowadzenie do analizy algorytmów:

• analiza algorytmu: poprawność, złożoność obliczeniowa, rozmiar zadania,

• podstawowe techniki konstruowania algorytmów: dziel i zwyciężaj(divide and conquer), algorytm nawrotu (backtracking algorithm), algorytm sita (sito Eratostenesa), algorytmy zachłanne (greedy algorithms),

• rząd złożoności obliczeniowej algorytmu, stosowane notacje: notacja O, notacja Ω, notacja Θ.

o szacowanie złożoności algorytmów dla podstawowych zadań arytmetycznych i logicznych.

2. Algorytmy sortowania

• klasyfikacja metod sortowania i ich charakterystyka,

• szacowanie złożoności obliczeniowej wybranych algorytmów sortowania:

• metodą prostego wybierania (SelectSort),

• metoda prostego wstawiania (InsertionSort),

• szybkie sortowanie (QuickSort),

• sortowanie metoda scalania (MergeSort),

• proste kolejki priorytetowe: kopce binarne

• sortowanie przez kopcowanie (HeapSort),

• sortowanie metodą Shella,

• sortowanie pozycyjne.

3. Algorytmy działania na grafach:

• reprezentacja grafów: macierz sąsiedztwa, macierz incydencji, listy sąsiedztwa ( krawędzi),

• reprezentacja grafów, przeszukiwanie wszerz, w głąb, sortowanie topologiczne, minimalne drzewa rozpinające, najkrótsze ścieżki, maksymalny przepływ

• deklarowanie metod działania na grafach: najkrótsza ścieżka w grafach (algorytm Dijkstry, algorytmu Bellmana-Forda, ), wyznaczanie minimalnego drzewa rozpinającego grafu (algorytm Kruskala, algorytm Dijkstry, Floyda- Warshalla, . . .),

• złożoność obliczeniowa algorytmów działania na grafach,

4. Algorytmy wyszukiwania: liniowego, liniowego z wartownikiem, binarnego (logarytmicznego), złożoność problemu wyszukiwania.

5. Złożone typy danych:

• tablice: jednowymiarowe, wielowymiarowe, postrzępione,

deklarowanie złożonych typów danych (na przykładzie typu danych Complex - Liczby zespolone): deklarowanie właściwości, przeciążanie operatorów: +, -, *, / (dla działań na wartościach typu Complex), nadpisywanie metod Equals i GetHashCode, deklaracja operatorów jawnych (explicit) i niejawnych (implicit) działania na wartościach zespolonych.

• struktury dynamiczne: drzewa binarne, stosy, kolejki, listy, kopiec, struktury słownikowy, drzewa AVL, drzewa czerwono-czarne,

6. Algorytmy działania na macierzach:

• deklarowanie macierzy,

• deklarowanie metod działania na macierzach: dodawanie, odejmowanie, mnożenie, dzielenie,

• złożoność obliczeniowa algorytmów działania na macierzach,

• przeciążanie operatorów arytmetycznych dla działania na macierzach,

• metody rozszerzające (dodawanie nowych metod do istniejących klas bez zmiany ich definicji)

7. Algorytmy i tablice z haszowaniem (funkcje mieszające, metoda łańcuchowa rozwiązywania kolizji, adresowanie otwarte i rozwiązywanie kolizji, mieszanie wielokrotne, reorganizacja tablic z haszowaniem).

8. Algorytmy wyszukiwanie wzorca:

• algorytm "naiwny",

• algorytm Knutha, Morrisa i Prata,

• algorytm Boyera i Moore'a,

• algorytm Rabina i Karpa,

• złożoność problemu wyszukiwania wzorca w tekście,

9. Algorytmy animacji komputerowych z zastosowaniem rachunku macierzowego:

a) współrzędne jednorodne i ich zastosowanie w przekształceniach 2D,

b) przekształcenia w geometrii 2D: przesunięcia, obroty, skalowanie, przekrzywienia,

c) animacje komputerowe,

d) zapis przekształceń w rachunku macierzowym,

e) standardowe metody transformacji: TranslateTransform, ScaleTransform, RotateTransform, SkewTransform , MatrixTransform, TransformGroup,

Laboratoria:

1. Szacowanie złożoności obliczeniowej dla zadanych algorytmów: działania na macierzach, działania na grafach, sortowania, wyszukiwania i laszowania w tablicach, wyszukiwanie wzorców tekstowych w tekstach.

2. Projektowanie programów dla eksperymentalnego szacowania złożoności obliczeniowej wybranych algorytmów.

3. Projektowanie struktur danych, algorytmów i programów dla problemów modelowych prezentowanych na wykładach. Analiza złożoności obliczeniowej opracowanych rozwiązań algorytmicznych.

Literatura:

0. Leszek Jung, Materiały z wykładów udostępniane w formie elektronicznej.

1. Cormen T.H., Leiserson Ch.E., Rivest R.L., Stein C., Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, 2012

2. R. Sedgewick, K. Wayne, „Algorytmy”, Helion 2012.

Efekty uczenia się:

WIEDZA:

1) Zna podstawowe struktury danych (tablice, listy, drzewa, stosy, kolejki, kopce, . . . ) oraz algorytmy działania na nich,

2) Zna pojęcie złożoność obliczeniowej algorytmu i potrafi korzystać ze źródeł literaturowych oraz poszukiwać własnych,

3) Zna podstawowe techniki szacowania złożoności obliczeniowej algorytmów sekwencyjnych, iteracyjnych i rekurencyjnych.

UMIEJĘTNOŚCI:

1) Potrafi dobrać i zastosować struktury danych oraz dobrać algorytmy do rozwiązywania zadania algorytmicznego oraz oszacować złożoność obliczeniową przyjętego rozwiązania,

2) Potrafi zaimplementować złożone i dynamiczne struktury danych oraz algorytmy działania na nich w wybranym języku programowania (CSharp),

3) Potrafi zaimplementować programy eksperymentalne dla pomiaru złożoności obliczeniowej algorytmów (tworzenie wykresu kosztu czasowego algorytmu funkcji rozmiaru zadania).

KOMPETENCJE SPOŁECZNE:

1) Potrafi zdekomponować problem na fragmenty, których realizacja prowadzi do zespołowego (lub indywidualnego) rozwiązania postawionego zadania,

2) Rozumie konieczność ciągłego uaktualniania swojej wiedzy w zakresie algorytmów, właściwości języka programowania, wykorzystywanych Frameworków, technik programowania i testowania programów zorientowanych obiektowo (w języku CSharp).

Metody i kryteria oceniania:

• indywidualne zadania projektowe ( 2 zadania projektowe w CSharp:

• projekt i implementacja programu dla wyszukiwania dróg w grafie,

• projekt i implementacja programu dla eksperymentalnego szacowania złożoności obliczeniowej wybranych algorytmów sortowania,

• prezentacja wykonanych projektów prowadzącemu zajęcia

• pisemny sprawdzian wiedzy (2 sprawdziany)

Sposób obliczania oceny końcowej:

1. Ocena końcowa obliczana jest jako 0.3*ocena z egzaminu + 0.5*ocena z projektów indywidualnych (zadań domowych) + 0.2*ocena z laboratoriów,

2. Przy obliczaniu oceny końcowej, nieusprawiedliwiona nieobecność na egzaminie, kolokwiach i zaliczeniach traktowana jest jako ocena niedostateczna.

Wymagania ogólne:

Zgodnie z Regulaminem Studiów AfiBV podstawowym terminem uzyskania zaliczenia jest ostatni dzień zajęć w danym semestrze. Termin zaliczenia poprawkowego:

• tryb i warunki ustala prowadzący zajęcia,

• nie może być późniejszy niż ostatni termin sesji poprawkowej.

Zajęcia w cyklu "Semestr zimowy 2017/2018" (zakończony)

Okres: 2017-10-01 - 2018-02-15
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Leszek Jung
Prowadzący grup: Leszek Jung, Bartosz Połok
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin/zaliczenie na ocenę/zal w skali zal-std2
Ćwiczenia - Egzamin/zaliczenie na ocenę/zal w skali zal-std2
Wykład - Egzamin/zaliczenie na ocenę/zal w skali zal-std2
Rodzaj przedmiotu:

obowiązkowe

Skrócony opis:

1) Dostarczenie studentom podstawowej wiedzy z zakresu:

• analizy algorytmów i struktur danych,

• technik stosowanych przy określanie złożoności obliczeniowej algorytmów

• znajomości podstawowych algorytmów dla różnych obszarów zastosowań,

2) Ukształtowanie podstawowych umiejętności w zakresie:

• szacowania złożoności obliczeniowej algorytmów (czasowej i pamięciowej) w odniesieniu do statycznych i dynamicznych struktur danych,

• konstruowania i stosowania algorytmów w takich obszarach jak: sortowanie, wyszukiwanie, metody numeryczne, działanie na tekstach, zastosowania grafów,

• umiejętności zaprojektowania aplikacji (w języku CSharp) dla pomiaru (eksperymentalnego) złożoności obliczeniowej algorytmu i przedstawienie wyników w formie tabelarycznej i w formie wykresu (funkcji rozmiaru zadania),

3) Utwierdzenie studentów w potrzebie systematycznego rozwijania swoich umiejętności w zakresie analizy złożoności obliczeniowej algorytmów.

Pełny opis:

Wykłady:

1. Wprowadzenie do analizy algorytmów:

• analiza algorytmu: poprawność, złożoność obliczeniowa, rozmiar zadania,

• podstawowe techniki konstruowania algorytmów: dziel i zwyciężaj(divide and conquer), algorytm nawrotu (backtracking algorithm), algorytm sita (sito Eratostenesa), algorytmy zachłanne (greedy algorithms),

• rząd złożoności obliczeniowej algorytmu, stosowane notacje: notacja O, notacja Ω, notacja Θ.

o szacowanie złożoności algorytmów dla podstawowych zadań arytmetycznych i logicznych.

2. Złożone typy danych:

• tablice: jednowymiarowe, wielowymiarowe, postrzępione,

deklarowanie złożonych typów danych (na przykładzie typu danych Complex - Liczby zespolone): deklarowanie właściwości, przeciążanie operatorów: +, -, *, / (dla działań na wartościach typu Complex), nadpisywanie metod Equals i GetHashCode, deklaracja operatorów jawnych (explicit) i niejawnych (implicit) działania na wartościach zespolonych.

• struktury dynamiczne: drzewa binarne, stosy, kolejki, listy, kopiec, struktury słownikowy, drzewa AVL, drzewa czerwono-czarne,

• grafy.

3. Algorytmy działania na tablicach:

• deklarowanie macierzy,

• deklarowanie metod działania na macierzach: dodawanie, odejmowanie, mnożenie, dzielenie,

• złożoność obliczeniowa algorytmów działania na macierzach,

• przeciążanie operatorów arytmetycznych dla działania na macierzach,

• metody rozszerzające (dodawanie nowych metod do istniejących klas bez zmiany ich definicji)

4. Algorytmy animacji komputerowych z zastosowaniem rachunku macierzowego:

a) współrzędne jednorodne i ich zastosowanie w przekształceniach 2D,

b) przekształcenia w geometrii 2D: przesunięcia, obroty, skalowanie, przekrzywienia,

c) animacje komputerowe,

d) zapis przekształceń w rachunku macierzowym,

e) standardowe metody transformacji: TranslateTransform, ScaleTransform, RotateTransform, SkewTransform , MatrixTransform, TransformGroup,

6. Algorytmy działania na grafach:

• reprezentacja grafów: macierz sąsiedztwa, macierz incydencji, listy sąsiedztwa ( krawędzi),

• reprezentacja grafów, przeszukiwanie wszerz, w głąb, sortowanie topologiczne, minimalne drzewa rozpinające, najkrótsze ścieżki, maksymalny przepływ

• deklarowanie metod działania na grafach: najkrótsza ścieżka w grafach (algorytm Dijkstry, algorytmu Bellmana-Forda, ), wyznaczanie minimalnego drzewa rozpinającego grafu (algorytm Kruskala, algorytm Dijkstry, Floyda- Warshalla, . . .),

• złożoność obliczeniowa algorytmów działania na grafach,

7. Algorytmy sortowania

• klasyfikacja metod sortowania i ich charakterystyka,

• szacowanie złożoności obliczeniowej wybranych algorytmów sortowania:

• metodą prostego wybierania (SelectSort),

• metoda prostego wstawiania (InsertionSort),

• szybkie sortowanie (QuickSort),

• sortowanie metoda scalania (MergeSort),

• proste kolejki priorytetowe: kopce binarne

• sortowanie przez kopcowanie (HeapSort),

• sortowanie metodą Shella,

• sortowanie pozycyjne.

8. Algorytmy wyszukiwania: liniowego, liniowego z wartownikiem, binarnego (logarytmicznego), złożoność problemu wyszukiwania.

9. Algorytmy i tablice z haszowaniem (funkcje mieszające, metoda łańcuchowa rozwiązywania kolizji, adresowanie otwarte i rozwiązywanie kolizji, mieszanie wielokrotne, reorganizacja tablic z haszowaniem).

10. Algorytmy wyszukiwanie wzorca:

• algorytm "naiwny",

• algorytm Knutha, Morrisa i Prata,

• algorytm Boyera i Moore'a,

• algorytm Rabina i Karpa,

• złożoność problemu wyszukiwania wzorca w tekście.

Literatura:

0. Leszek Jung, Materiały z wykładów udostępniane w formie elektronicznej.

1. Cormen T.H., Leiserson Ch.E., Rivest R.L., Stein C., Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, 2012

2. R. Sedgewick, K. Wayne, „Algorytmy”, Helion 2012.

Zajęcia w cyklu "Semestr zimowy 2018/2019" (zakończony)

Okres: 2018-10-01 - 2019-02-01
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Artur Wiliński
Prowadzący grup: Sławomir Matusiak, Artur Wiliński
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin/zaliczenie na ocenę/zal w skali zal-std2
Ćwiczenia - Egzamin/zaliczenie na ocenę/zal w skali zal-std2
Wykład - Egzamin/zaliczenie na ocenę/zal w skali zal-std2
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Akademia Finansów i Biznesu Vistula.
ul. Stokłosy 3
02-787 Warszawa
tel: +48 22 45 72 300 https://vistula.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.0.0-1 (2023-09-06)