Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowaniaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Algorytmy i struktury danych

Informacje ogólne

Kod przedmiotu: 1000-I1ASD Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji
Nazwa przedmiotu: Algorytmy i struktury danych
Jednostka: Wydział Matematyki i Informatyki
Grupy: Informatyka, studia I stopnia, 1 rok
Informatyka, studia I stopnia, 2 rok
Informatyka, studia inżynierskie 1 stopnia, 1 rok
Przedmioty z polskim językiem wykładowym
Punkty ECTS i inne: 6.00
zobacz reguły punktacji
Język prowadzenia: polski
Wymagania wstępne:

Wstęp do programowania

Znajomość języka programowania, pozwalająca na implementacje algorytmów

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:

• Zna metody tworzenia, analizowania i implementacji algorytmów

• Zna podstawowe algorytmy: wyszukiwania i porządkowania, na liczbach całkowitych, grafowe, tekstowe i geometryczne oraz przykłady ich zastosowań

• Zna wybrane struktury danych oparte na: tablicach, listach i drzewach


Efekty uczenia się - umiejętności:

• Wyjaśnia podstawowe metody tworzenia algorytmów, takie jak: przeszukiwanie, sortowanie, podejście zachłanne, dziel i zwyciężaj, rekurencja, programowanie dynamiczne, przeszukiwanie z nawrotami i stosuje je do odpowiednio dobranych problemów

• Podaje specyfikacje problemów i algorytmów ich rozwiązywania

• Przedstawia algorytmy wymienione w opisie przedmiotu i określa ich złożoność obliczeniową

• Definiuje proste i złożone struktury danych

• Dobiera odpowiednie struktury danych do algorytmu i sposobu jego implementacji


Efekty uczenia się - kompetencje społeczne:

• Poznane algorytmy i struktury danych odnosi do ich rzeczywistych zastosowań

• Poprawnie posługuje się terminologią z zakresu algorytmów i struktur danych

• Dzieli się swoją wiedzą z innymi w przystępny dla nich sposób


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:

Celem przedmiotu jest przedstawienie podstawowych metod tworzenia algorytmów, omówienie wybranych algorytmów i ich zastosowań oraz struktur danych używanych w implementacjach tych algorytmów. Analiza algorytmów i struktur danych dotyczy złożoności obliczeniowej implementacji algorytmów. W czasie zajęć laboratoryjnych studenci analizują, implementują i testują wybrane algorytmy stosując odpowiednie struktury danych oraz wyznaczają rząd złożoności niektórych programów.

Pełny opis:

Omawiane są następujące zagadnienia :

• Podstawowe algorytmy: schemat Hornera oraz biblioteka standardowa C++ (stos, kolejka, wskaźniki i iteratory)

• Elementy analizy algorytmów: funkcje całkowitoliczbowe, notacja złożoności obliczeniowej

• Sortowanie przez: zliczanie, scalanie, kopcowanie, sortowanie szybkie; złożoność problemu i algorytmów sortowania

• Podstawowe metody projektowania algorytmów: wyszukiwanie, porządkowanie, metoda dziel i zwyciężaj, rekurencja, podejście zachłanne, programowanie dynamiczne; przykłady użycia tych metod w projektowaniu algorytmów

• Grafy - definicja, wprowadzenie teoretycznie i grafy szczególne (Eulera i Hamiltona)

• Algorytmy grafowe: DFS i BFS, kopce i kolejki; znajdowanie przechodniego domknięcia, sortowanie topologiczne

• Znajdowanie najkrótszych dróg: algorytm Dijkstry, Bellmana-Forda, Floyda – Warshalla

• Znajdowanie najkrótszego drzewa rozpinającego - algorytm Prima-Dijkstry, Kruskala; struktury danych dla zbiorów rozłącznych

• Drzewa poszukiwań binarnych inne struktury drzewiaste (np. drzewa przedziałowe i potęgowe)

• Drzewa czerwono-czarne

• Algorytmy tekstowe: funkcje skrótu, algorytm Rabina-Karpa, algorytm Knutha-Morrisa-Pratta, kodowanie Huffmana

• Algorytmy geometryczne na płaszczyźnie : podstawowe algorytmy geometryczne, znajdowanie otoczki wypukłej, przecinanie odcinków w zbiorze odcinków

• Algorytmy przeszukiwania z nawrotami i aproksymacyjne: kolorowanie grafów i problem komiwojażera

Literatura:

Literatura podstawowa:

• L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, 2018

• T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, WNT PWN, 2012

• D. Harel, Rzecz o istocie informatyki. Algorytmika, WNT, 1992.

• M.M. Syslo, N. Deo, J.S. Kowalik, Algorytmy optymalizacji dyskretnej z programami w języku Pascal, WN PWN, 1997

• M.M. Sysło, Algorytmy, Helion, 2016

• M.M. Sysło, Piramidy, szyszki i inne konstrukcje programistyczne, Helion, 2015

• J. Tomasiewicz, Zaprzyjaźnij się z algorytmami, Przewodnik dla początkujących i średnio zaawansowanych, PWN, 2016

Literatura uzupełniająca:

• 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 r.

• 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, oceny z implementacji algorytmów i ich prezentacji

Ocena pozytywna z egzaminu pisemnego

Zajęcia w cyklu "Semestr letni 2017/18" (zakończony)

Okres: 2018-02-26 - 2018-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Łukasz Mikulski, Maciej Sysło
Prowadzący grup: Anna Kwiatkowska, Łukasz Mikulski, Andrzej Mróz, Maciej Sysło, 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 2018/19" (zakończony)

Okres: 2019-02-25 - 2019-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Łukasz Mikulski
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 2019/20" (w trakcie)

Okres: 2020-02-29 - 2020-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Łukasz Mikulski
Prowadzący grup: Damian Kurpiewski, Anna Kwiatkowska, Łukasz Mikulski, Andrzej Mróz, Marcin Piątkowski, 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 2020/21" (jeszcze nie rozpoczęty)

Okres: 2021-03-01 - 2021-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: (brak danych)
Prowadzący grup: (brak danych)
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.