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: | [W1] Zna metody tworzenia, analizowania i implementacji algorytmów [W2] Zna podstawowe algorytmy: wyszukiwania i porządkowania, na liczbach całkowitych, grafowe, tekstowe i geometryczne oraz przykłady ich zastosowań [W3] Zna wybrane struktury danych oparte na: tablicach, listach i drzewach |
||
| Efekty uczenia się - umiejętności: | [U1] 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 [U2] Podaje specyfikacje problemów i algorytmów ich rozwiązywania [U3] Przedstawia algorytmy wymienione w opisie przedmiotu i określa ich złożoność obliczeniową [U4] Definiuje proste i złożone struktury danych [U5] Dobiera odpowiednie struktury danych do algorytmu i sposobu jego implementacji |
||
| Efekty uczenia się - kompetencje społeczne: | [K1] Poznane algorytmy i struktury danych odnosi do ich rzeczywistych zastosowań [K2] Poprawnie posługuje się terminologią z zakresu algorytmów i struktur danych [K3] 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) |
||
| Metody dydaktyczne poszukujące: | - ćwiczeniowa |
||
| Metody dydaktyczne w kształceniu online: | - metody rozwijające refleksyjne myślenie |
||
| 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 czerowno-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 lub 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 (W1-W3, U1-U4, K2-K3), oceny z implementacji algorytmów (U4-U5) i ich prezentacji (K1-K3). Ocena pozytywna z egzaminu pisemnego (W1-W3, U1-U5, K2). |
||
Zajęcia w cyklu "Semestr letni 2017/18" (zakończony)
| Okres: | 2018-02-26 - 2018-09-30 |
 
 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 |
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" (zakończony)
| Okres: | 2020-02-29 - 2020-09-20 |
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-02-22 - 2021-09-20 |
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, Katarzyna Zając | |
| Lista studentów: | (nie masz dostępu) | |
| Zaliczenie: |
Przedmiot -
Egzamin
Laboratorium - Zaliczenie na ocenę Wykład - Egzamin |
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.