Uniwersytet w Białymstoku - Centralny System Uwierzytelniania
Strona główna

Algorytmy i struktury danych II

Informacje ogólne

Kod przedmiotu: 400-IS1-2ASD2
Kod Erasmus / ISCED: 11.301 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (brak danych)
Nazwa przedmiotu: Algorytmy i struktury danych II
Jednostka: Filia Uniwersytetu w Białymstoku w Wilnie, Wydział Ekonomiczno-Informatyczny
Grupy: 3L stac. I st. studia informatyki - przedmioty obowiązkowe - WILNO
Wilno - informatyka 2 rok 1 st. stacjonarne sem.letni
Punkty ECTS i inne: (brak) 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
Rodzaj przedmiotu:

obowiązkowe

Wymagania (lista przedmiotów):

Algorytmy i struktury danych 1000-IS1-1ASD

Założenia (lista przedmiotów):

Algorytmy i struktury danych 1000-IS1-1ASD

Założenia (opisowo):

Zakłada się, że student zaliczył przedmiot Algorytmy i struktury danych (1000-IS1-1ASD) i posiada wiedzę dotyczącą takich pojęć, jak algorytm, koszty algorytmu, techniki projektowania algorytmów, oraz problemy obliczeniowo trudne (NP-zupełność, nierozstrzygalność). Zna podstawowe techniki wyszukiwania i sortowania. Zapoznał się z takimi strukturami danych i podstawowymi operacjami na nich, jak: tablice, listy, stosy, kolejki, grafy, tablice z haszowaniem, struktury drzewiaste. Student zna problem wyszukiwania wzorca i algorytmy go dotyczące. Przyjmuje się, ze student biegle posługuje się językami programowania strukturalnego i obiektowego (np. C, C++, C# Java).

Tryb prowadzenia przedmiotu:

w sali

Skrócony opis:

Celem przedmiotu jest zapoznanie studentów z wybranymi zaawansowanymi algorytmami i strukturami danych. Zostaną omówione podstawowe algorytmy grafowe oraz algorytmy tekstowe (problem wyszukiwania wzorca), a także zagadnienia dotyczące problemów obliczeniowo trudnych (w tym NP-zupełnych). Student zapozna się z technikami przekształcania przestrzeni atrybutów oraz analizy skupień (grupowania), a także elementami przetwarzania obrazów oraz sieci przepływowych.

Pełny opis:

Zajęcia składają się z wykładu, laboratorium i projektu. Celem wykładu jest zapoznanie studentów z wybranymi zaawansowanymi algorytmami i strukturami danych: kolejki priorytetowe, kopce, tablice z mieszaniem, drzewa (w tym drzewa BST), grafy. Podstawowe algorytmy grafowe (przeszukiwanie wszerz, przeszukiwanie w głąb, algorytm Dijkstry, algorytm Bellmana-Forda, budowanie minimalnego drzewa rozpinającego). Algorytmy tekstowe: problem wyszukiwania wzorca. Problemy obliczeniowo trudne (w tym NP-zupełne). Student zapozna się z technikami przekształcania przestrzeni atrybutów, w tym z dyskretyzacją. Wykład obejmie także prezentacje celu i technik analizy skupień (grupowania), a także elementy przetwarzania obrazów oraz sieci przepływowe i metodę Forda-Fulkersona.

Zajęcia laboratoryjne polegają na wykonaniu zadań bezpośrednio związanymi z wybranymi tematami omawianymi na wykładzie. Praca w ramach projektu dotyczy samodzielnego wykonania i przygotowania raportu z zadania o tematyce związanej (choć niekoniecznie bezpośrednio) z treściami podanymi na wykładzie.

W celu opanowania treści przedmiotu student potrzebuje 15 godzin wykładu, ponadto około 15 godzin pracy własnej nad treściami przekazanymi na wykładzie oraz 15 godzin zajęć laboratoryjnych i 15 godzin zajęć projektowych uzupełnionych łącznie około 20 godzinami pracy własnej. Punkty ECTS: 5.

Literatura:

1. Aho A. V., Hopcroft J. E., Ullman J. D.: Algorytmy i struktury

danych, Helion, Gliwice 2003

2. L. Banachowski, A. Kreczmar, W.Rytter, „Algorytmy i struktury danych”, WNT, Warszawa,1985

3. T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, „Wprowadzenie do algorytmów”, WNT, 1997

4. Homenda W.: Algorytmy, złożoność obliczeniowa, granice obliczalności, Centrum Studiów Zaawansowanych Politechniki Warszawskiej, 2009

5. Sysło M.M.: Algorytmy, WSiP, Warszawa 2002

6. Wirth N.: Algorytmy + struktury danych = programy, WNT, Warszawa 2002

7. P. Wróblewski, „Algorytmy, struktury danych i techniki programowania”, Helion, 2003

Efekty uczenia się:

KW_03 zna pojęcie algorytmu oraz zasady projektowania i analizy aIgorytm6w.

KU_03 samodzielnie potrafi zaprojektować algorytmy realizujące wybrane zadania. potrafi przeprowadzić analizę złożoności danego algorytmu.

KU_05 samodzielnie implementuje algorytmy stosując odpowiednie elementy wybranego języka programowania.

KU_18 potrafi przygotować opracowanie zagadnień informatycznych (w tym dokumentacji technicznej) w języku polskim oraz zaprezentować je.

Metody i kryteria oceniania:

Zaliczenie przedmiotu polega na zaliczeniu w/w wykładu, laboratorium i projektu. Wykład zaliczony będzie na podstawie sprawdzianu pisemnego, na który składa się 5 pytań/zadań dotyczących tematów omawianych na wykładzie. Zaliczenie laboratorium polega na zaliczeniu ćwiczeń wykonanych w pracowni laboratoryjnej, zaś zaliczenie projektu odbywa się na podstawie demonstracji wykonanego zadania projektowego i przedłożenia krótkiego raportu z jego wykonania. Skale ocen zaliczenia wykładu i laboratorium podane są odpowiednio w Sekcjach - Zajęcia: Wykład i Zajęcia: laboratorium).

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet w Białymstoku.
ul. Świerkowa 20B, 15-328 Białystok tel: +48 85 745 70 00 (Centrala) https://uwb.edu.pl kontakt deklaracja dostępności USOSweb 7.0.2.0-1 (2024-03-12)