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

Algorytmy i struktury danych

Informacje ogólne

Kod przedmiotu: 0800-ALGOSD
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ł Fizyki, Astronomii i Informatyki Stosowanej
Grupy:
Punkty ECTS i inne: 8.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:

Analiza matematyczna, Algebra, Matematyka dyskretna, Języki programowania, Programowanie strukturalne

Rodzaj przedmiotu:

przedmiot obowiązkowy

Całkowity nakład pracy studenta:

30H - wykład

30H - ćwiczenia

30H - laboratorium

135H - praca indywidualna

Efekty uczenia się - wiedza:

Posiada wiedzę o szeregu podstawowych algorytmów w informatyce.

Zna metody analizowania działania algorytmu.

Posiada wiedzę o metodach oceny złożoności algorytmów.

Posiada wiedzę o różnych struktura danych i potrafi jej używać.

Zna podstawy teorii grafów.

Zna różne sposoby konstrukcji algorytmów.


W 4, 6, 10,



Efekty uczenia się - umiejętności:

Potrafi implementować algorytmy i struktury danych.

Umie dokonać analizy algorytmu.

Umie znajdować błędy w programach

Potrafi oszacować złożoność obliczeniową.

Potrafi używać instrumentów matematyki do analizy algorytmów.

Potrafi wykorzystać wiedzę z teorii grafów.

Umie stworzyć nowe programy z wykorzystanie poznanych algorytmów lub opracować nowy algorytm.

Umie używać narzędzi programistycznych.

Potrafi dokonać analizy ekonomicznej dotyczącej czasu realizacji zadań

informatycznych, a także związanych z tym kosztów.


U 1, 2, 8, 13, 21



Efekty uczenia się - kompetencje społeczne:

ma świadomość skutków wadliwie działających systemów informatycznych, które mogą doprowadzić do strat moralnych i finansowych, a nawet utraty zdrowia czy zagrożenia życia


uznaje fundamentalne znaczenie wiedzy dla ludzkości, potrafi krytycznie ocenić posiadaną wiedzę oraz zna jej ograniczenia


K 1, 6



Metody dydaktyczne:

Wykład: prezentacja materiału i problemów, dyskusja

Ćwiczenia: omawianie zagadnień i ich analiza, wspólne i indywidualne rozwiązywanie zadań. Analiza przypadków. Częściowo praca grupowa.

Laboratoria: Nacisk na indywidualne rozwiązywanie problemów + pomoc eksperta. Dyskusja nad przykładami rozwiązań.

Metody dydaktyczne eksponujące:

- pokaz
- symulacyjna (gier symulacyjnych)

Metody dydaktyczne podające:

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

Metody dydaktyczne poszukujące:

- ćwiczeniowa
- doświadczeń
- giełda pomysłów
- klasyczna metoda problemowa
- laboratoryjna
- obserwacji
- projektu
- punktowana
- studium przypadku
- sytuacyjna

Metody dydaktyczne w kształceniu online:

- metody ewaluacyjne
- metody odnoszące się do autentycznych lub fikcyjnych sytuacji
- metody rozwijające refleksyjne myślenie
- metody wymiany i dyskusji

Skrócony opis:

Przedmiot omawia szereg zagadnień dotyczących różnych sposobów reprezentacji danych, konstrukcji algorytmów i analizę wybranych algorytmów. Prezentowane są także zagadnienia związane ze złożonością obliczeniową i ich analizą.

Pełny opis:

1. Algorytmy a struktury danych - uwagi ogólne.

2. Dynamiczne struktury danych: Listy, stosy, kolejki, kolejki priorytetowe, listy cykliczne, listy dwukierunkowe, wartownik. Budowa struktur i algorytmów operujące na różnych typach list.

3. Drzewa, drzewa binarne, drzewa przeszukiwań (z porządkiem), dwukierunkowe. Sposoby wykorzystywania struktur drzewiastych.

4. Grafy, sposoby reprezentacji, terminologia. Podstawowe sposoby manipulacji na grafach.

5. Definicje złożoności i sposoby jej wyznaczania.

6. Uwagi o typach algorytmów.

7. Algorytmy sortowania:

- Analiza algorytmów sortowania O(n^2)

- Analiza algorytmów sortowania O(n log n)

- Analiza algorytmów sortowania O(n)

8. Statystyki pozycyjne

9. Metody mnożenia macierzy

10. Programowanie dynamiczne

11. Problem mnożenia ciągu macierzy

12. Algorytm wyznaczania najdłuższego wspólnego podciągu

13. Algorytm triangulacji wielokąta

14. Algorytmy przeszukiwania grafów

15. Sortowanie topologiczne

16. Algorytmy wyznaczania minimalnych drzew rozpinających

17. Algorytmy wyznaczania najkrótszych ścieżek w grafach:

- Elementy wspólne algorytmów

- Algorytm Dijkstry

- Algorytm Bellmana-Forda

- Algorytm Floyda-Warshalla

18. Analiza i algorytmy drzew zbalansowanych na przykładzie drzew czerwono-czarnych.

Literatura:

A. V. Aho, J. E. Hopcroft, J. D. Ullman. Projektowanie i analiza algorytmów. Helion, Warszawa, 2003.

A. V. Aho, J. E. Hopcroft, J. D. Ullman. Projektowanie i analiza algorytmów. Państwowe Wydawnictwa Naukowe, Warszawa, 1983.

Niklaus Wirth. Algorytmy + Struktury Danych = Programy. Wydawnictwa Naukowo-Techniczne, Warszawa, wydanie 2, 1989.

T. H. Cormen, C. E. Leiserson, R. L Rivest. Wprowadzenie do algorytmów. Wydawnictwa Naukowo-Techniczne, Warszawa, 1997.

L. Banachowski, K. Diks, W. Rytter. Algorytmy i struktury danych. Wydawnictwa Naukowo-Techniczne, Warszawa, 1996.

Metody i kryteria oceniania:

1. Bieżąca praca.

2. Kolokwia pisemne.

3. Zadania bieżące (listy zadań i programów).

4. Wejściówki (w zależności od potrzeb).

5. Zadania laboratoryjne

6. Egzamin pisemny.

Powyższe metody oceny weryfikują zakres programu jak i efekty kształcenia opisane powyżej.

Aby przystąpić do egzaminu trzeba mieć zdane ćwiczenia i laboratorium.

Szczegółowy sposób oceny laboratorium jest w dokumencie dotyczącym listy zadań. Tam też są określone ścisłe progi ocen.

Zaliczenie kolokwium:

minimum 50%, poniżej 2.0, od 50% (3.0) ocena skalowana liniowo do 5.0

Zaliczenie ćwiczeń:

średnia z kolokwiów pod warunkiem zaliczenia każdego z kolokwiów i zaliczenia wejściówek.

Ocena egzaminu:

minimum 50%, poniżej 2.0, od 50% (3.0) ocena skalowana liniowo do 5.0

W pracy bieżącej, na kolokwiach, na laboratoriach i egzaminie weryfikuje się wszystkie efekty uczenia się: wiedzy, umiejętności i kompetencje społeczne.

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

Okres: 2021-10-01 - 2022-02-20
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Norbert Jankowski
Prowadzący grup: Piotr Ablewski, Norbert Jankowski, Miłosz Michalski, Oleksandr Sokolov
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin

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

Okres: 2022-10-01 - 2023-02-19
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Norbert Jankowski
Prowadzący grup: Piotr Ablewski, Norbert Jankowski, Miłosz Michalski, Oleksandr Sokolov
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
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ęć:
Ćwiczenia, 30 godzin więcej informacji
Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Norbert Jankowski
Prowadzący grup: Piotr Ablewski, Norbert Jankowski, Miłosz Michalski, Oleksandr Sokolov
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
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)