Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowania
Strona główna

Algorytmy i struktury danych

Informacje ogólne

Kod przedmiotu: 1000-ZiASD
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 struktury danych
Jednostka: Wydział Matematyki i Informatyki
Grupy:
Punkty ECTS i inne: 12.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
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.

Rodzaj przedmiotu:

przedmiot obowiązkowy

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

Skrócony opis:

Jest to podstawowy kurs algorytmiki, obejmujący najważniejsze metody projektowania algorytmów oraz wykorzystywane w nich struktury danych. Szczególny nacisk kładzie się na metody szacowania złożoności obliczeniowej algorytmów. Dokładnie omawiane są przykłady algorytmów rozwiązujących konkretne problemy, w tym: zasady ich działania, niezbędne elementarne narzędzia matematyczne oraz uzasadnienia poprawności.

Pełny opis:

  • 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.
    • 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.
  • Wyszukiwanie wzorca w tekście.
    • Algorytm naiwny.
    • Metoda haszowania, algorytm Karpa-Rabina (przy okazji - schemat Hornera).
  • Geometria obliczeniowa.
    • Wzajemne położenie obiektów geometrycznych.
    • Elementy geometrii fraktalnej - fraktale (m.in. trójkąt i dywan Sierpińskiego), iterowane układy funkcyjne i metoda IFS generowania fraktali.
    • Geometryczne podejście do numerycznego obliczania pierwiastka kwadratowego z liczby - algorytm Newtona-Rhapsona.
    • 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.
    • Wzmianka o teorii informacji - entropia.

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ść.

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.

Metody i 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

Zajęcia w cyklu "Rok akademicki 2020/21" (zakończony)

Okres: 2020-10-01 - 2021-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 100 miejsc więcej informacji
Koordynatorzy: Bartosz Ziemkiewicz
Prowadzący grup: Dariusz Borkowski, Michał Dudkiewicz, Bartosz Ziemkiewicz
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin
Uwagi:

Część wykładów będzie się odbywała w formie zdalnej na platformie MS Teams. Link do zespołu:

https://teams.microsoft.com/l/team/19%3ad2c17087f7e04f7ab04f56aecbbf22fb%40thread.tacv2/conversations?groupId=c8848370-8acc-4d7c-bc29-4841d1f5be8f&tenantId=e80a627f-ef94-4aa9-82d6-c7ec9cfca324

Pozostałe wykłady odbywać się będą w formie asynchronicznej na platformie Moodle. Adres kursu:

https://plas.mat.umk.pl/moodle/course/view.php?id=1991

Klucz do kursu: algorytm2021

Zajęcia w cyklu "Semestr letni 2021/22" (zakończony)

Okres: 2022-02-21 - 2022-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 100 miejsc więcej informacji
Koordynatorzy: Bartosz Bieganowski
Prowadzący grup: Bartosz Bieganowski, Bartosz Ziemkiewicz
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr letni 2022/23" (zakończony)

Okres: 2023-02-20 - 2023-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 100 miejsc więcej informacji
Koordynatorzy: Bartosz Bieganowski
Prowadzący grup: Bartosz Bieganowski, Bartosz Ziemkiewicz
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.
ul. Jurija Gagarina 11, 87-100 Toruń tel: +48 56 611-40-10 https://usosweb.umk.pl/ kontakt deklaracja dostępności USOSweb 7.0.2.0-1 (2024-03-12)