Algorytmy i złożoność
Informacje ogólne
Kod przedmiotu: | CII3NP11CI-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
|
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. Struktury dynamiczne: drzewa binarne, stosy, kolejki, listy, kopiec, struktury słownikowy, drzewa AVL, drzewa czerwono-czarne, 3. 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. 4. Algorytmy wyszukiwania: liniowego, liniowego z wartownikiem, binarnego (logarytmicznego), złożoność algorytmów wyszukiwania. 5. Algorytmy działania na grafach: • reprezentacja grafów: macierz sąsiedztwa, macierz incydencji, listy sąsiedztwa, listy krawędzi, • 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, 6. 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, Laboratoria: 1. Projektowanie programów z zastosowaniem określonych klas algorytmów (omawianych na wykładzie). 2. Projektowanie programów dla eksperymentalnego szacowania złożoności obliczeniowej wybranych algorytmów sortowania 3. Projektowanie struktur danych dynamicznych, algorytmów i programów dla algorytmów (zadań modelowych) prezentowanych na wykładach (z obszaru zastosowań grafów). 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 |
zobacz plan zajęć |
Typ zajęć: |
Ćwiczenia, 20 godzin
Wykład, 20 godzin
|
|
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, |
|
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 |
zobacz plan zajęć |
Typ zajęć: |
Ćwiczenia, 20 godzin
Wykład, 20 godzin
|
|
Koordynatorzy: | Leszek Jung | |
Prowadzący grup: | Leszek Jung | |
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 |
Właścicielem praw autorskich jest Akademia Finansów i Biznesu Vistula.