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

Algorytmy eksploracji i przetwarzania masywnych zbiorów danych

Informacje ogólne

Kod przedmiotu: 1000-I2AlgEkspMZD
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 eksploracji i przetwarzania masywnych zbiorów danych
Jednostka: Wydział Matematyki i Informatyki
Grupy: Inf., II st, stacjonarne, przedmioty do wyboru
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
Wymagania wstępne:

Aby w pełni docenić materiał w tego wykładu, zalecamy następujące wymagania:

1. Podstawowe wiadomości z zakresu informatyki obejmujące bazy danych i programowanie współbieżne oraz systemy operacyjne.

2. Algorytmy oraz struktury danych i matematyka dyskretna.

3. Eksploracja danych oraz metody uczenia maszynowego.

4. Algorytmy i metody skalowanego przetwarzania danych.

5. Inżynieria oprogramowania i języków programowania.

Wymagana jest praktyczna znajomość współczesnego języka programowania (J​ava, ​Python,​ C, ​C++, C# itp)​, oraz zasad programowania obiektowego.

Całkowity nakład pracy studenta:

30 godz. ­ wykład

30 godz. ­ laboratoria

3 godz. ­ egzamin

3 godz. ­ prezentacja zadań laboratoria

40 godz. ­ praca własna: przygotowanie zadań

40 godz. ­ bieżące przygotowania do zajęć, studiowanie literatury 40 godz. ­ praca własna: przygotowanie do egzaminu

Efekty uczenia się - wiedza:

M_W01 - zna zaawansowane metody projektowania i analizowania złożoności obliczeniowej algorytmów i programów sekwencyjnych, równoległych i rozproszonych ­ K_W04.

M_W02 - zna metody statystycznej analizy danych, w tym zagadnienia estymacji, testowania hipotez i redukcji wymiaru danych ­ K_W08.

M_W03 - zna metody algorytmicznego rozwiązywania problemów obliczeniowo trudnych (aproksymacja, FFT, szybkie algorytmy wykładnicze, heurystyki, metody Monte Carlo, algorytm Metropolisa, symulowane wyżarzanie, algorytmy genetyczne) ­ K_W09.

M_W04 - zna biegle co najmniej jeden język programowania oraz biblioteki algorytmów i struktur danych; ma wiedzę na temat praktycznych uwarunkowań wydajnych implementacji algorytmów ­ K_W10.


Efekty uczenia się - umiejętności:

M_U01 - potrafi opisywać algorytmy i struktury danych w sposób zrozumiały dla nie informatyków ­ K_U02.

M_U02 - projektuje i analizuje algorytmy rozproszone; potrafi uzasadnić ich poprawność i przeanalizować złożoności ­ K_U04.

M_U03 - posługuje się bibliotekami algorytmów i struktur danych, w tym bibliotekami algorytmów numerycznych ­ K_U05.

M_U04 - potrafi posługiwać się podstawowymi narzędziami informatycznymi wspomagającymi tworzenie oprogramowania i jego utrzymanie ­ K_U07.

M_U05 - umie znajdować niezbędne informacje w literaturze fachowej, bazach danych i innych źródłach, zna podstawowe czasopisma i konferencje naukowe w swojej specjalności ­ K_U13.


Efekty uczenia się - kompetencje społeczne:

M_K01 - Kreatywność: Myśli twórczo w celu udoskonalenia istniejących bądź stworzenia nowych rozwiązań ­ K_K02.

M_K02 - Analityczne myślenie: Samodzielnie i efektywnie pracuje z dużą ilością danych, dostrzega zależności i poprawnie wyciąga wnioski posługując się zasadami logiki ­ K_K03.

M_K03 - Sumienność i dokładność: Jest nastawiony na jak najlepsze wykonanie zadania; dba o szczegół; jest systematyczny ­ K_K04.

M_K04 - Komunikatywność: Skutecznie przekazuje innym swoje myśli w zrozumiały sposób; właściwie posługuje się terminologią fachową; potrafi nawiązać kontakt w obrębie swojej dziedziny i z osobą reprezentującą inną dziedzinę ­ K_K05.

M_K05 - Wytrwałość i konsekwencja: Pracuje systematycznie i posiada umiejętność pozytywnego podejścia do trudności stojących na drodze do realizacji założonego celu; dotrzymuje terminów ­ K_K08.


Metody dydaktyczne:

Metody dydaktyczne podające:


* wykład informacyjny (konwencjonalny).


Metody dydaktyczne poszukujące:


* ćwiczeniowa,

* laboratoryjna,

* klasyczna metoda problemowa.


Metody dydaktyczne eksponujące:

- pokaz

Metody dydaktyczne podające:

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

Metody dydaktyczne poszukujące:

- ćwiczeniowa
- laboratoryjna
- projektu
- referatu

Skrócony opis:

Dynamiczne pojawienie się dużych zbiorów danych w internecie spowodowała konieczność ich szybkiego przetwarzania, a umiejętność ta powoli staje się jednym z podstawowych wymogów pracy w wielu dużych firmach. Zagadnienie to jest wymagające i pozwala na praktyczne wykorzystanie wiedzy zdobytej z takich dziedzin jak algorytmika, przetwarzanie danych, eksploracja danych itp. Ponadto, ze względu na specyfikę problemu, istotnym elementem zagadnienia stała się nauka optymalizacji kodu eksplorującego dane z wykorzystaniem dostępnych narzędzi w rożnych kontekstach: obliczeń, zużycia energii, ograniczeniami związanymi z przesyłem i składowaniem danych. Wykład ten przedstawi pojawiające się w tej dziedzinie problemy oraz paradygmaty pozwalające na ich rozwiązanie.

Pełny opis:

Popularność sieci Web i biznesu w internecie (tzw. e-commerce) spowodowała powstanie wielu zbiorów danych, z których informacje mogą być pozyskiwane za pomocą metod eksploracji danych. Tym co odróżnia ten wykład od innych o podobnej tematyce jest to, że skupia się on na eksploracji danych ze zbiorów o bardzo dużej wielkości, czyli danych tak dużych, że nie mieszczą się swobodnie w pamięci operacyjnej czy wręcz dysku pojedynczego węzła obliczeniowego. Opiszemy i podamy motywacje technik w eksploracji dużych zbiorów danych.

Skoncentrujemy się na praktycznych aspektach algorytmów, które zostały wykorzystane w celu rozwiązania kluczowych problemów w eksploracji danych, a które mogą być wykorzystane na nawet największych zbiorach danych. Dział ten w literaturze był dotąd potraktowany tylko powierzchownie i nie ma jeszcze kompleksowego przeglądu istniejących metod.

Co ważne, w tym wykładzie będziemy mówić o tym jak rozwiązać konkretne problemy eksploracji danych w kontekście ogromnego rozmiaru danych. Ponadto, celem tego wykładu jest także wyrobienie intuicji programistycznych dotyczących rozwiązywania standardowych problemów związanych z przetwarzaniem danych typu "big data".

Wykład zaczyna się od przypomnienia podstawowych zagadnień eksploracji danych, następnie krótkiej dyskusji na temat Map Reduce’a, który jest ważnym modelem skalowalnego przetwarzania danych. Dalej wyjaśnimy tajniki poszukiwania podobnych obiektów z szczególnym uwzględnieniem technik hash­wania. Następnie zajmiemy się algorytmami eksploracji i przetwarzania strumieni danych, które pojawiają się zbyt szybko i jest ich zbyt dużo by dokonać wyczerpującej analizy. Kolejnym z omówionych tematów będą metody analizy połączeń w sieci Web, pojawi się idea Page Rank­u oraz inne metody. Pozostałe tematy dotyczą problemów ze znalezieniem zbiorów częstych i klastrowania. Ponadto rozpatrzymy dwa zastosowania: systemy rekomendacyjne oraz reklamę internetową, obydwie niezbędne w e­biznesie. Wykład z założenia zamierza być interesujący zarówno dla teoretyków jak i praktyków.

Przedmiot będzie zrealizowany w dwóch częściach: wykład oraz laboratorium. Wykład będzie obejmował teoretyczne i praktyczne aspekty przetwarzania i eksploracji dużych zbiorów danych. W ramach wykładu zamierzamy przedstawić modele eksploracji danych w paradygmacie rozproszonym.

Materiały wykładu zostaną udostępnione w formie slajdów. Praca w laboratorium będzie polegać przede wszystkim na samodzielnym wykonaniu przez studentów zadań związanych z prezentowanymi na wykładzie zagadnieniami. Ćwiczenia będą prowadzone w formie zachęcającej uczestników do intensywnej pracy w trakcie zajęć, jak i samodzielnej pracy domowej. W ramach laboratorium przewidujemy implementację i eksperymentowanie z otwartymi implementacjami przedstawionych algorytmów. Treści zadań (wraz z opisem ich realizacji) będą udostępnione w formie materiałów z laboratorium publikowanych w systemie Modle.

Program ramowy kursu:

1. Rozproszone systemy plików i Map Reduce jako wygodny model do tworzenia skalowalnych algorytmów przetwarzania danych,

2. Wyszukiwanie podobieństwa, w tym rożne metody hash­ujące.

3. Przetwarzanie strumieni danych, w których dane trzeba przeanalizować szybko lub będą nieprzydatne ("przeanalizuj albo wyrzuć").

4. Analiza połączeń w sieci Web: w tym Google s Page Rank, wykrywanie link­spam, podejście "hubs-and-authorities".

5. Wyszukiwanie elementów częstych, w tym reguły

asocjacyjne, metoda koszykowa, algorytmy typu apriori.

6. Algorytmy grupowania dużych zbiorów danych oraz zbiorów danych w wysokich wymiarach.

7. Problemy w aplikacjach internetowych: zarządzanie reklamami i systemy rekomendujące.

8. Algorytmy analizy i eksploracji bardzo dużych grafów, zwłaszcza tych występujących na serwisach społecznościowych.

9. Redukcja wymiarowości, w tym rozkład według wartości osobliwych, indeksowanie semantyczne.

10. Algorytmy uczenia maszynowego, które mogą być stosowane do bardzo dużych zbiorów danych, np.: perceptron, SVM, algorytm spadku gradientowego itd.

Literatura:

Jure Leskovec, Anand Rajaraman, and Jeffrey David Ullman. Mining of massive datasets. Cambridge University Press, 2014. (http://www.mmds.org/)

Jiawei Han, Micheline Kamber. Data Mining: Concepts and Techniques. The Morgan Kaufmann Series in Data Management Systems, 2000.

Tadeusz Morzy. Eksploracja danych Metody i algorytmy. PWN, 2013.

Metody i kryteria oceniania:

Zaliczenie laboratorium odbywa się na podstawie 4/5 projektów zaliczeniowych wykonywanych częściowo w trakcie laboratoriów i częściowo samodzielnie.

Zaliczenie wykładu na podstawie oceny z ćwiczeń i indywidualnego projektu (prezentacja + pytania do projektu).

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