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-ZiASD 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 inżynierskie 1 stopnia, 1 rok, nst.
Punkty ECTS i inne: 12.00
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:

wykład - 30 godz.

laboratorium - 30 godz.

praca własna: (bieżące przygotowanie do zajęć, implementacja programów, zapoznanie się z materiałami dydaktycznymi umieszczonymi na platformie e-learningowej) - 205 godz..

przygotowanie do egzaminu: 35 godz.


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 1 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_W01);

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 1 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 1 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_K05;

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_K06.


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

o Specyfikacja problemu, (częściowa) poprawność algorytmu.

o Funkcja kosztu.

o Złożoność asymptotyczna, notacje "O", "Omega", "Theta". Własności,

przykłady.

• Przegląd wybranych algorytmów sortowania, ich porównanie, złożoność obliczeniowa.

• Podstawowe dynamiczne struktury danych, metody ich implementacji.

o Stos.

o Kolejka.

o Listy: jednokierunkowe, dwukierunkowe, cykliczne.

• Elementy teorii grafów.

o Pojęcie grafu oraz grafu z wagami.

o Droga w grafie, składowa spójności; graf spójny, pełny, dwudzielny, ...

o Struktury danych do reprezentowania grafów.

o Drzewo, drzewo z korzeniem, drzewo binarne, drzewo rozpinające grafu.

• Złożone struktury danych, zastosowania, złożoność obliczeniowa wykonywanych na nich operacji.

o Drzewo poszukiwań binarnych.

o Kopiec, kolejka priorytetowa.

o Zbiory rozłączne: różne implementacje, heurystyka.

• Algorytmy rekurencyjne, wady i zalety. Metody szacowania złożoności.

• Metody projektowania algorytmów, charakteryzacja, przykłady; zalety i ograniczenia.

o Metoda przyrostowa.

o Metoda „dziel i zwyciężaj”.

o Metoda zachłanna.

o Programowanie dynamiczne.

• Wybrane algorytmy z różnych dziedzin. Analiza ich poprawności, złożoności, metody implementacji, zastosowania. Niezbędne elementarne pojęcia i narzędzia matematyczne.

o Algorytmy grafowe (przeszukiwanie grafu w głąb i wszerz, algorytmy Dijkstry, Bellmana-Forda, Kruskala, Prima, Forda-Fulkersona i in.).

o Algorytmy tekstowe (wyszukiwanie wzorca, algorytm Rabina-Karpa, kodowanie Huffmana i in.).

W trakcie ćwiczeń w laboratoriach studenci implementują zarówno poznane na wykładzie, jak i zaprojektowane przez siebie algorytmy oraz szacują ich złożoność obliczeniową.

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:

egzamin ustny – W1, W2, W3, W4, W5, U1, U2, U3, K3, K4;

aktywność na zajęciach – K1, K2, K3;

implementacja algorytmów w ramach zajęć i prac domowych - W1, W2, W4, W5, U1, U2, U3, U4, U5, U6;

kolokwium - W1, W4, W5, U2, K3;

Praktyki zawodowe:

Nie dotyczy

Zajęcia w cyklu "Rok akademicki 2017/18" (zakończony)

Okres: 2017-10-01 - 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: Bartosz Ziemkiewicz
Prowadzący grup: Michał Dudkiewicz, Paweł Lebioda, Bartosz Ziemkiewicz
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Rok akademicki 2018/19" (zakończony)

Okres: 2018-10-01 - 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, 100 miejsc więcej informacji
Koordynatorzy: Bartosz Ziemkiewicz
Prowadzący grup: Bartosz Bieganowski, Michał Dudkiewicz, Paweł Lebioda, Bartosz Ziemkiewicz
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Rok akademicki 2019/20" (zakończony)

Okres: 2019-10-01 - 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, 100 miejsc więcej informacji
Koordynatorzy: Bartosz Ziemkiewicz
Prowadzący grup: Bartosz Bieganowski, Michał Dudkiewicz, Damian Kurpiewski, Bartosz Ziemkiewicz
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Rok akademicki 2020/21" (w trakcie)

Okres: 2020-10-01 - 2021-09-20
Wybrany podział planu:


powiększ
zobacz plan zajęć
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: 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.