Prowadzony w
cyklach:
2022/23L, 2024/25, 2025/26
Kod ISCED: 0613
Punkty ECTS:
10
Język:
polski
Organizowany przez:
Wydział Matematyki i Informatyki
Algorytmy i struktury danych 1000-ZiASD
Pojęcie algorytmu i jego złożoności obliczeniowej.- Specyfikacja problemu, (częściowa) poprawność algorytmu.
- Funkcja kosztu.
- Złożoność asymptotyczna, notacje "O", "Omega", "Theta". Własności i przykłady.
Wybrane algorytmy sortowania, ich porównanie i analiza złożoności.
Podstawowe dynamiczne stuktury danych, metody ich implementacji i zastosowania.- Stos. Odwrotna notacja polska.
- Kolejka. Szukanie najkrótszej drogi wyjścia z labiryntu.
- Lista. Problem Flawiusza.
- Lista priorytetowa.
Sortowanie leksykograficzne z zastosowaniem dynamicznych struktur danych.
Elementy teorii grafów.- Grafy i metody ich reprezentacji.
- Przeszukiwanie grafów (DFS, BFS).
- Zastosowanie przeszukiwań grafów. Spójność i spójne składowe, dwudzielność.
- Najkrótsze ścieżki w grafach. Algorytm Dijkstry, algorytm Floyda-Warshalla.
- Drzewa, w tym drzewa rozpinające, kopiec jako przykład drzewa. Sortowanie przez kopcowanie.
- Minimalne drzewo rozpinające grafu.
- Analiza złożoności algorytmów operujących na grafach.
Metody projektowania algorytmów.- Metoda przyrostowa.
- Dziel i zwyciężaj.
- Metoda zachłanna.
- Programowanie dynamiczne.
- Przykłady zastosowań: problem pakowania plecaka, problem optymalnego nawiasowania ciągu mnożeń macierzy.
Drzewa BST.- Wstawianie, wyszukiwanie, usuwanie węzłów.
- Przeglądanie drzewa: preorder, inorder, postorder.
- Wzmianka o drzewach czerwono-czarnych.
Algorytmy tekstowe- Wyszukiwanie wzorca w tekście - algorytm naiwny.
- Metoda haszowania, algorytm Karpa-Rabina (przy okazji - schemat Hornera).
- Palindromy, algorytm Manachera
Geometria obliczeniowa.- Wzajemne położenie obiektów geometrycznych.
- Otoczka wypukła podzbioru płaszczyzny i algorytmy jej wyznaczania - algorytm Jarvisa, algorytm Grahama, podejście rekurencyjne.
Kompresja.- Współczynnik kompresji. Kompresja stratna i bezstratna.
- Algorytmy słownikowe kompresji.
- Algorytmy statystyczne kompresji - drzewa Huffmana.
W trakcie ćwiczeń w laboratoriach studenci implementują zarówno poznane na wykładzie, jak i zaprojektowane przez siebie algorytmy, szacują ich złożoność obliczeniową i analizują ich poprawność.
Całkowity nakład pracy studenta
1. Godziny realizowane z udziałem nauczycieli
a) wykład – 30 godzin,
b) laboratorium – 30 godziny,
c) bieżące przygotowanie do zajęć, w tym rozwiązywanie zadań zleconych przez prowadzących, zapoznanie się z informacją zwrotną dotyczącą rozwiązanych zadań oraz konsultacje z prowadzącymi zajęcia – 60 godzin.
2. Czas poświęcony na pracę indywidualną studenta potrzebny do pomyślnego zaliczenia przedmiotu:
a) studiowanie literatury – 30 godzin,
b) zapoznanie się z materiałami dodatkowymi – 45 godzin,
c) wykonanie zadań domowych – 60 godzin.
3. Czas wymagany do przygotowania się do uczestnictwa w procesie oceniania (np. w egzaminach):
a) przygotowanie się do egzaminu – 45 godzin.
RAZEM: 300 godz.
12 pkt. ECTS
Efekty uczenia się - wiedza
Po zakończeniu przedmiotu student osiąga następujące efekty (kody odnoszą się do efektów dla studiów pierwszego stopnia na kierunku informatyka - studia inżynierskie):
W1: ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie programowania, algorytmów i złożoności obliczeniowej - K_W02;
W2: zna dynamiczne struktury danych wykorzystywane w algorytmach (stos, kolejka, lista, drzewo BST, kopiec binarny, kolejka priorytetowa, struktura zbiorów rozłącznych), ich wady i zalety oraz ich wpływ na złożoność obliczeniową algorytmów i zarządzanie pamięcią - K_W05, K_W07;
W3: ma uporządkowaną wiedzę ogólną w zakresie możliwości i ograniczeń wykorzystania komputera w rozwiązywaniu problemów obliczeniowych - K_W02, K_W04;
W4: zna podstawowe metody projektowania, analizowania i programowania algorytmów (projektowanie strukturalne, rekurencja, metoda dziel i zwyciężaj, metoda zachłanna, programowanie dynamiczne, poprawność, złożoność obliczeniowa) - K_W04;
W5: zna wybrane algorytmy i ich zastosowania: algorytmy grafowe, algorytmy tekstowe - K_W04.
Efekty uczenia się - umiejętności
Po zakończeniu przedmiotu student osiąga następujące efekty (kody odnoszą się do efektów dla studiów pierwszego stopnia na kierunku informatyka - studia inżynierskie):
U1: potrafi zastosować wiedzę matematyczną do formułowania, analizowania i rozwiązywania obliczeniowych problemów informatycznych, analizuje je pod kątem możliwości ich algorytmicznego rozwiązania z jak najlepszą złożonością obliczeniową - K_U01;
U2: używa klasycznych algorytmów oraz modyfikuje je w celu rozwiązania konkretnych, specyficznych problemów - K_U06, K_U07;
U3: projektuje, analizuje pod kątem poprawności i złożoności obliczeniowej oraz programuje algorytmy; wykorzystuje podstawowe techniki algorytmiczne i umie dopasować struktury danych i metody projektowania algorytmów odpowiednie do danego problemu - K_U07;
U4: potrafi pozyskiwać informacje z dokumentacji, systemów pomocy, literatury, baz wiedzy, Internetu oraz innych wiarygodnych źródeł, integrować je, dokonywać ich interpretacji oraz wykorzystywać w praktyce - K_U02;
U5: potrafi pisać, uruchamiać i testować programy w wybranym środowisku programistycznym - K_U05;
U6: potrafi pracować indywidualnie i w zespole informatyków, w tym także potrafi zarządzać swoim czasem oraz podejmować zobowiązania i dotrzymywać terminów - K_U03.
Efekty uczenia się - kompetencje społeczne
Po zakończeniu przedmiotu student osiąga następujące efekty (kody odnoszą się do efektów dla studiów pierwszego stopnia na kierunku informatyka - studia inżynierskie):
K1: myśli twórczo w celu udoskonalenia istniejących bądź stworzenia nowych rozwiązań, w tym w zakresie problemów algorytmicznych - K_K02;
K2: jest nastawiony na jak najlepsze i terminowe wykonanie zadania; dba o szczegół; jest systematyczny - K_K04;
K3: skutecznie przekazuje innym swoje myśli w zrozumiały sposób, właściwie posługuje się terminologią fachową - K_K02;
K4: jest nastawiony na nieustanne zdobywanie nowej wiedzy, umiejętności i doświadczeń; rozumie potrzebę ciągłego doskonalenia się i podnoszenia kompetencji zawodowych - K_K03.
Metody dydaktyczne
Zagadnienia dyskutowane na tym przedmiocie podawane są studentom w formie wykładów informacyjnych i problemowych przeplatanych pokazami działania algorytmów na konkretnych, reprezentatywnych danych wejściowych. Wykłady uzupełnione są zajęciami laboratoryjnymi poświęconymi zarówno implementacji poznawanych algorytmów i struktur danych jak i rozwiązywaniu teoretycznych ćwiczeń problemowych pozwalających pogłębić wiedzę przyswojoną w czasie wykładów.
Metody dydaktyczne eksponujące
- pokaz
Metody dydaktyczne podające
- wykład informacyjny (konwencjonalny)
Metody dydaktyczne poszukujące
- laboratoryjna
Rodzaj przedmiotu
przedmiot obligatoryjny
Wymagania wstępne
Zakłada się, że uczestnik niniejszego kursu posiada następującą wiedzę i umiejętności (zdobytą np. na kursach Podstawy programowania i Matematyka dla informatyków I):
- zna podstawowe techniki programistyczne (obsługa wejścia/wyjścia, pętle, instrukcje warunkowe, funkcje, przekazywanie parametrów, tablice, rekordy) potrafi ich sprawnie używać w wybranym języku programowania (zalecane C++);
- posiada elementarną wiedzę matematyczną: rozumie zapis symboliczny, zna podstawy logiki, kombinatoryki i arytmetyki (indukcja, ciągi liczbowe) oraz zna pojęcie funkcji i związane z nim notacje;
- umie czytać ze zrozumieniem algorytmy w postaci pseudokodu oraz pisać programy na ich podstawie.
Koordynatorzy przedmiotu
Kryteria oceniania
Na ocenę z wykładu składają się:
- zadania domowe z części asynchronicznej weryfikujące efekty U2-U4, K1, K2,
- egzamin pisemny weryfikujący efekty W1-W5, U1, K1, K3.
Warunkiem koniecznym jest uzyskanie pozytywnej oceny dla każdego z powyższych elementów. Bardziej szczegółowe zasady mogą znajdować się w informacjach dla zajęć w konkretnym cyklu i będą podane przez prowadzącego wykład.
Zaliczenie laboratoriów na ocenę. Elementami składowymi zaliczenia są:
- kolokwium teoretyczno-praktyczne weryfikujące efekty W2, W4, W5, U1-U5, K1,
- aktywność na zajęciach i samodzielne przygotowanie rozwiązań zadań programistycznych weryfikujące efekty W2, W4, W5, U1-U6, K1-K4.
Warunkiem koniecznym jest uzyskanie pozytywnej oceny dla każdego z powyższych elementów. Bardziej szczegółowe zasady zaliczenia laboratorium mogą znajdować się w informacjach dla zajęć w konkretnym cyklu i będą podane przez prowadzących laboratoria.
Praktyki zawodowe
Nie dotyczy
Literatura
Literatura podstawowa:
1. T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, L. C. Stein, Wprowadzenie do algorytmów, PWN, Warszawa 2018.
2. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, PWN, Warszawa 2018.
3. D. Harel, Rzecz o istocie informatyki. Algorytmika, WNT, Warszawa 2008.
Literatura uzupełniająca:
1. R. Sedgewick, K. Wayne, Algorytmy. Wydanie IV, Helion, Warszawa 2017.
2. M. M. Sysło, Algorytmy, Helion, Warszawa 2016.
3. M. M. Sysło, Piramidy, szyszki i inne konstrukcje programistyczne, Helion, Warszawa 2015.
4. N. M. Josuttis, C++ Biblioteka standardowa. Wydanie II, Helion, Warszawa 2014.
5. D. E. Knuth, Sztuka programowania, WNT, Warszawa 2002.
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: