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

Algorytmy i struktury danych

Informacje ogólne

Kod przedmiotu: 1000-I1ASD
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: 6.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.

zobacz reguły punktacji
Język prowadzenia: polski
Wymagania wstępne:

Zakłada się, że uczestnik niniejszego kursu posiada następującą wiedzę i umiejętności (zdobyte na przedmiocie Podstawy algorytmiki programowania (1000-I1PAiP) i przedmiotach matematycznych na 1 roku):


  • zna podstawowe techniki programistyczne (obsługa wejścia/wyjścia, pętle, instrukcje warunkowe, funkcje, przekazywanie parametrów, tablice, struktury) potrafi ich sprawnie używać w wybranym języku programowania (zalecane C++ lub Python);

  • 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:

30 godz. – wykład; 30 godz. – ćwiczenia

50 godz. – praca własna: bieżące przygotowanie do zajęć, praca z literaturą

35 godz. – praca własna: przygotowanie do egzaminu

3 godz. – egzamin


RAZEM: 148 godz.

6 pkt. ECTS


Efekty uczenia się - wiedza:

(W1) ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie programowania, algorytmów oraz ich poprawności i złożoności (por. K_W02 );


(W2) zna najważniejsze struktury danych i wykonywane na nich operacje oraz ich wpływ na złożoność obliczeniową algorytmów i zarządzanie pamięcią (por. K_W05, również K_W07);


(W3) zna podstawowe metody projektowania, analizowania i programowania algorytmów (projektowanie strukturalne, rekurencja, metoda dziel i zwyciężaj, metoda zachłanna, programowanie dynamiczne, złożoność obliczeniowa), por. K_W04;


(W4) zna podstawowe klasyczne algorytmy i ich zastosowania: algorytmy wyszukiwania i porządkowania, algorytmy optymalizacyjne, algorytmy grafowe (por. K_W02 i K_W04).


Efekty uczenia się - umiejętności:

(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ą (por. K_U01);


(U2) 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 (por. K_U07);


(U3) implementuje podstawowe klasyczne algorytmy, uzasadnia ich poprawność, określa ich złożoność obliczeniową oraz umie dostosować je do rozwiązania konkretnych, specyficznych problemów (por. K_U07);


(U4) potrafi pisać, uruchamiać i testować programy w wybranym środowisku programistycznym (por. K_U05);


(U5) potrafi pracować indywidualnie nad projektem programistycznym, w tym także potrafi zarządzać swoim czasem oraz podejmować zobowiązania i dotrzymywać terminów (por. K_U03).



Efekty uczenia się - kompetencje społeczne:

(K1) myśli twórczo w celu udoskonalenia istniejących bądź stworzenia nowych rozwiązań (w zakresie problemów algorytmicznych, por. K_K02);


(K2) jest gotów do pokonywania trudności stojących na drodze do realizacji założonego celu i systematycznej pracy nad projektem programistycznym; jest nastawiony na jak najlepsze i terminowe wykonanie zadania (por. K_K04);


(K3) jest gotów do krytycznej oceny swojej wiedzy i dalszego jej doskonalenia z wykorzystaniem różnych źródeł informacji (por. K_K03).



Metody dydaktyczne eksponujące:

- pokaz

Metody dydaktyczne podające:

- wykład informacyjny (konwencjonalny)
- wykład problemowy

Metody dydaktyczne poszukujące:

- ćwiczeniowa
- doświadczeń
- klasyczna metoda problemowa
- laboratoryjna
- projektu
- referatu

Metody dydaktyczne w kształceniu online:

- metody rozwijające refleksyjne myślenie
- metody służące prezentacji treści

Skrócony opis:

Jest to podstawowy kurs algorytmiki, obejmujący najważniejsze metody projektowania i analizy algorytmów oraz wykorzystywane w nich struktury danych. Szczególny nacisk kładzie się na uzasadnianie poprawności i szacowanie 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, uzasadnienia poprawności oraz metody efektywnej implementacji.

Pełny opis:

  • Pojęcie algorytmu i jego złożoności obliczeniowej.
    • Problem a algorytm. Specyfikacja problemu.
    • Funkcja kosztu i pełna funkcja kosztu.
    • Koszt zamortyzowany.
    • Złożoność asymptotyczna, notacje "O", "Ω", "Θ". Własności i przykłady.
    • Metody wyznaczania funkcji kosztu algorytmów rekurencyjnych.
  • Elementarne struktury danych: tablica, stos, kolejka, lista, wektor.
  • Przegląd wybranych algorytmów sortowania.
  • Metody projektowania algorytmów.
    • Metoda przyrostowa.
    • Dziel i zwyciężaj.
    • Metoda zachłanna.
    • Programowanie dynamiczne.
    • Przykłady zastosowań, m.in.: sortowanie przez scalanie, problem bankomatu, problem plecakowy, optymalny wybór zajęć, optymalne nawiasowanie ciągu mnożeń macierzy.
  • Dowodzenie poprawności algorytmu.
    • Częściowa poprawność: systemy formalne Hilberta i Hoare'a, niezmiennik pętli.
    • Całkowita poprawność: własność stopu, zbieżnik pętli.
  • Drzewiaste struktury danych.
    • Drzewa poszukiwań binarnych (BST).
    • Wzmianka o drzewach czerwono-czarnych.
    • Kopiec binarny.
    • Złożoność operacji.
    • Zastosowania, m.in.: wyszukiwanie, analiza wyrażeń, implementacja kolejki priorytetowej, sortowanie (heapsort).
  • Elementy teorii grafów, reprezentacja grafów w komputerze.
  • Algorytmy grafowe i ich zastosowania.
    • Przeglądanie grafów w głąb (DFS) i wszerz (BFS). Testowanie spójności i najkrótsze drogi.
    • Najkrótsze drogi w grafach z wagami - algorytmy Dijkstry i Bellmana-Forda.
    • Minimalne drzewo rozpinające (MST), przekroje.
    • Struktura danych zbiorów rozłącznych, analiza heurystyczna implementacji.
    • Algorytmy Kruskala i Prima znajdowania MST.
  • *Wprowadzenie do algorytmów aproksymacyjnych i teorii NP-zupełności. Problem komiwojażera.

W trakcie ćwiczeń w laboratoriach studenci analizują i implementują zarówno poznane na wykładzie, jak i zaprojektowane przez siebie algorytmy.

Literatura:

Literatura podstawowa:

  • T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, WNT PWN, 2018.
  • L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, 2018.
  • M.M. Sysło, Algorytmy, Helion, 2016.
  • D. Harel, Rzecz o istocie informatyki. Algorytmika, WNT, 1992.
  • J. Tomasiewicz, Zaprzyjaźnij się z algorytmami, Przewodnik dla początkujących i średnio zaawansowanych, PWN, 2016.

Literatura uzupełniająca:

  • M.M. Syslo, N. Deo, J.S. Kowalik, Algorytmy optymalizacji dyskretnej z programami w języku Pascal, WN PWN, 1997.
  • M.M. Sysło, Piramidy, szyszki i inne konstrukcje programistyczne, Helion, 2015.
  • A.V. Aho, J.E. Hopcroft, J.D. Ullman, Algorytmy i struktury danych, Helion, 2003.
  • R.J. Wilson, Wprowadzenie do teorii grafów, PWN 2016.
  • P. Stańczyk, Algorytmika praktyczna. Nie tylko dla mistrzów, PWN, 2009.
  • P. Mikołajczyk, Wprowadzenie do STL, UMCS, Lublin 2012.
Metody i kryteria oceniania:

Na zaliczenie przedmiotu składa się :

  • Zaliczenie laboratorium na podstawie oceny z kolokwium (W1-W4, U1-U3, K1) oraz z implementacji algorytmów (U3-U5) i ich prezentacji (K1-K3).
  • Zaliczenie egzaminu pisemnego z wykładu (W1-W4, U1-U3, K1).

Warunkiem koniecznym jest uzyskanie pozytywnej oceny dla każdego z powyższych elementów. Warunkiem dopuszczenia do egzaminu jest zaliczenie laboratoriów. Bardziej szczegółowe zasady zaliczenia mogą znajdować się w informacjach dla zajęć w konkretnym cyklu i będą podane przez prowadzących laboratoria i wykład.

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, 150 miejsc więcej informacji
Koordynatorzy: Łukasz Mikulski, Andrzej Mróz
Prowadzący grup: Anna Kwiatkowska, Łukasz Mikulski, Andrzej Mróz, Katarzyna Zając
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, 50 miejsc więcej informacji
Koordynatorzy: Łukasz Mikulski
Prowadzący grup: Anna Kwiatkowska, Łukasz Mikulski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr zimowy 2023/24" (zakończony)

Okres: 2023-10-01 - 2024-02-19
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy: Andrzej Mróz
Prowadzący grup: Witold Kraśkiewicz, Damian Kurpiewski, Anna Kwiatkowska, Łukasz Mikulski, Andrzej Mróz, Katarzyna Zając
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)