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

Algorytmy i złożoność

Informacje ogólne

Kod przedmiotu: CII4SP001CI
Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
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) 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.

zobacz reguły punktacji
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
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć:
Ćwiczenia, 15 godzin więcej informacji
Wykład, 30 godzin więcej informacji
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
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć:
Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
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
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć:
Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
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
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)