Algorytmy i złożoność
Informacje ogólne
Kod przedmiotu: | CII4SP001CI |
Kod Erasmus / ISCED: |
(brak danych)
/
(0613) Tworzenie i analiza oprogramowania i aplikacji
|
Nazwa przedmiotu: | Algorytmy i złożoność |
Jednostka: | Kierunek-Informatyka |
Grupy: |
Informatyka 4 sem. PL ST |
Punkty ECTS i inne: |
4.00
LUB
5.00
(zmienne w czasie)
|
Język prowadzenia: | polski |
Rodzaj przedmiotu: | obowiązkowe |
Tryb prowadzenia: | zdalnie |
Założenia (lista przedmiotów): | Introduction to Database CII1SE02 |
Założenia (opisowo): | Umiejętność programowania zorientowanego obiektowo w języku C#, podstawową wiedze z zakresu matematyki dyskretnej |
Skrócony opis: |
Dostarczenie studentom podstawowej wiedzy i umiejętności praktycznych z zakresu: • szacowania złożoności obliczeniowej algorytmów (czasowej i pamięciowej) w odniesieniu do statycznych i dynamicznych struktur danych, • projektowania programów dla pomiaru (eksperymentalnego) złożoności obliczeniowej algorytmu i przedstawienie wyników w formie tabelarycznej i graficznej (wykresu)(funkcji rozmiaru zadania), • analizy właściwości podstawowych struktur danych (struktury, tablice, drzewa, kopce, stosy, kolejki, . . .), • metody projektowania algorytmów: dziel i zwyciężaj(divide and conquer), programowanie dynamiczne (dynamic programming), zasada optymalności Bellmana, algorytm nawrotu (backtracking algorithm), algorytm sita (sito Eratostenesa), algorytmy zachłanne (greedy algorithms), • znajomości podstawowych algorytmów dla różnych obszarów zastosowań (sortowania, wyszukiwania, działania na grafach, działania na tekstach, . . .), |
Pełny opis: |
Wykład: 1) Analiza algorytmów i struktur danych: • analiza algorytmu: poprawność, złożoność obliczeniowa, rozmiar zadania, • charakterystyka podstawowych technik(metod) konstruowania algorytmów: dziel i zwyciężaj(divide and conquer), programowanie dynamiczne (dynamic programming), zasada optymalności Bellmana, algorytmy z nawrotami/powrotami (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, o twierdzenie o rekurencji uniwersalnej. 2. Algorytmy zachłanne (greedy algorithms: dobór struktur danych, przykłady algorytmów, 3. Algorytmy rekurencyjne (recursive algorithm): • algorytm Euklidesa, silnii, wyznaczania wyrazów ciągu Fibonacciego, potęgowanie, wieżą Hanoi, • szacowanie złożoności obliczeniowej algorytmów rekurencyjnych, 4. 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. 5. Algorytmy wyszukiwania (w kolekcjach danych): • liniowe, • liniowe z wartownikiem, • binarne (logarytmiczne), • złożoność algorytmów wyszukiwania. 6. Algorytmy sita (sieve algorithm): sito Eratostenesa, Sito Atkina-Bernsteina, 7. Dynamiczne struktury danych: • struktury: drzewa binarne, stosy, kolejki, listy, kopce, słowniki, struktury słownikowy, drzewa AVL, drzewa czerwono-czarne, . . . ., • algorytmy działania na dynamicznych strukturach danych, • szacowanie złożoności obliczeniowej algorytmów działania na dynamicznych strukturach danych, 8. 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, 9. 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, 10. Algorytmy programowania dynamicznego (dynamic programming): symbol Newtona, wyznaczanie wartości n-tego wyrazu ciągu Fibonacciego, wypłata w bankomacie, wyznaczanie trasy, 11. Algorytmy z nawrotami (backtracking algorithm); wyjście z labiryntu, rozmieszczenia 8 hetmanów na szachownicy. Laboratoria: 1. Projektowanie programu zastosowaniem algorytmu zachłannego do obsługi ): obsługa bankomatu oraz automatów vendingowych, 2. Projektowanie programów narzędziowych dla wizualizacji tabelarycznej i graficznej eksperymentalnego szacowania złożoności obliczeniowej wybranych algorytmów (omawianych na wykładzie): sortowania, wyszukiwania, działania na grafach. 3. Projektowanie programów z zastosowaniem struktur dynamicznych: stosy, kolejki, drzewa binarne, kopce, listy. Analiza złożoności obliczeniowej opracowanych rozwiązań algorytmicznych. 4. Projektowanie programów wyszukiwania wzorców tekstowych według algorytmów (omawianych na wykładzie): Knutha, Morrisa i Prata, Boyera i Moore'a, Rabina i Karpa. 5. Projektowanie programów z zastosowaniem algorytmów programowania dynamicznego (dynamic programming), 6. Projektowanie programów z zastosowaniem algorytmów nawrotu (backtracking algorithm). |
Literatura: |
1. Slajdy wykładowcy udostępniane studentom na platformie PLATON AFiBV, 2. Cormen T.H., Leiserson Ch.E., Rivest R.L., Stein C., Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, 2012, 3. 2. M. Sysło, Algorytmy, Helion 2016, 4. M. Jamro, Struktury danych i algorytmy w języku C#, Helion 2019 5. https://javastart.pl/baza-wiedzy/algorytmy 6) Jacek Wojciechowski, Krzysztof Pieńkosz, Grafy i sieci, Hellion 2017. 7) Karin R. Saoub, Graph Theory: An Introduction to Proofs, Algorithms, and Applications. Wydawca Chapman and Hall/CRC; 2021. 8) Gosnell Denise , Broecheler Matthias, Dane grafowe w praktyce. Jak technologie grafowe ułatwiają rozwiązywanie złożonych problemów, Hellion 2021 |
Efekty uczenia się: |
1. Ma uporządkowaną wiedzę w zakresie metod projektowania algorytmów oraz technik szacowania ich złożoności obliczeniowej algorytmów sekwencyjnych, iteracyjnych i rekurencyjnych, 2. Ma uporządkowaną wiedzę w zakresie podstawowe struktury danych (tablice, listy, drzewa, stosy, kolejki, kopce, kolejki, grafy, . . . ) , 3. Potrafi dobrać i zastosować odpowiednie struktury danych i algorytmy do rozwiązywania zadania algorytmicznego, korzystając (w miarę potrzeby) z literatury źródłowej, 4. Potrafi zaimplementować programy eksperymentalne dla pomiaru złożoności obliczeniowej algorytmów (tworzenie wykresu kosztu czasowego algorytmu funkcji rozmiaru zadania), 5. Potrafi zaprezentować i uzasadnić zasadność przyjętego rozwiązania zadania w zakresie dobranych struktur danych i algorytmów. |
Metody i kryteria oceniania: |
Wykład: Dla zaliczenia wykładu (przedmiotu) studenci wykonują indywidualne zadania projektowe (3 zadania projektowe): • projekt i implementacja programu obsługi Bankomatu i Automatu vendingowego (algorytm zachłanny i dynamiczny) • projekt i implementacja programu umożliwiającego eksperymentalne szacowanie złożoności obliczeniowej (czasowej i pamięciowej) wybranych algorytmów sortowania (różne algorytmy sortowania), • projekt i implementacja programu wyszukiwania dróg w grafie (szacowanie złożoności obliczeniowej (czasowej i pamięciowej) wybranych algorytmów,_ 2) • opracowanie dokumentacji projektowej i użytkowej dla programów realizowanych na zającach laboratoryjnych, 3) zaliczenie 3 pisemnych (projektowych) sprawdzianów wiedzy na wykładzie. Laboratorium: • obecność obowiązkowa na zajęciach laboratoryjnych, • uruchomienie i przetestowanie programów realizowanych na zającach laboratoryjnych, • opracowanie dokumentacji projektowej i użytkowej dla programów realizowanych na zającach laboratoryjnych. Wymagania ogólne: Zgodnie z Regulaminem Studiów AfiBV podstawowym terminem uzyskania zaliczenia jest ostatni dzień zajęć w danym semestrze. Termin zaliczenia poprawkowego jest określany przez prowadzącego zajęcia w termin sesji poprawkowej. Formę i warunki zaliczenia poprawkowego ustala prowadzący zajęcia. Wyrównywanie zaległości powstałych wskutek nieobecności na zajęciach: • nieobecność na zajęciach wymaga od studenta samodzielnego opanowania materiału prezentowanego (omawianego) na tych zajęciach, • nieobecność na przeprowadzanym kolokwium/teście wymaga od studenta uzgodnienia z prowadzącym formy i terminu jego zaliczenia, nie później niż w ostatnim tygodniu trwania zajęć. |
Zajęcia w cyklu "Semestr letni 2021/2022" (zakończony)
Okres: | 2022-02-19 - 2022-09-30 |
zobacz plan zajęć |
Typ zajęć: |
Ćwiczenia, 15 godzin
Wykład, 30 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 |
Zajęcia w cyklu "Semestr letni 2022/2023" (zakończony)
Okres: | 2023-02-18 - 2023-09-30 |
zobacz plan zajęć |
Typ zajęć: |
Laboratorium, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Alexander Prokopenya | |
Prowadzący grup: | Alexander Prokopenya | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin/zaliczenie na ocenę/zal w skali zal-std2
Laboratorium - Egzamin/zaliczenie na ocenę/zal w skali zal-std2 Wykład - Egzamin/zaliczenie na ocenę/zal w skali zal-std2 |
Zajęcia w cyklu "Semestr letni 2023/2024" (w trakcie)
Okres: | 2024-02-19 - 2024-07-14 |
zobacz plan zajęć |
Typ zajęć: |
Laboratorium, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Maria Baczyńska-Wilkowska | |
Prowadzący grup: | Maria Baczyńska-Wilkowska | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin/zaliczenie na ocenę/zal w skali zal-std2
Laboratorium - 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.