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

Algorytmy i metody skalowalnego przetwarzania danych

Informacje ogólne

Kod przedmiotu: 1000-I2AMSPD Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji
Nazwa przedmiotu: Algorytmy i metody skalowalnego przetwarzania danych
Jednostka: Wydział Matematyki i Informatyki
Grupy: Informatyka, studia II stopnia, 3 sem, 1 rok
Informatyka, studia II stopnia, 4 sem, 1 rok
Punkty ECTS i inne: 6.00
Język prowadzenia: polski
Wymagania wstępne:

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


Rodzaj przedmiotu:

przedmiot obowiązkowy

Całkowity nakład pracy studenta:

30 godz. - wykład

30 godz. - ćwiczenia

30 godz. - praca z literaturą

60 godzin - realizacja projektów zaliczeniowych

10 godzin - konsultacje

Efekty uczenia się - wiedza:

K_W04

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


K_W12

ma wiedzę o aktualnych kierunkach rozwoju i o najnowszych odkryciach w zakresie technologii sieciowych i architektur komputerów


Efekty uczenia się - umiejętności:

K_U04

projektuje i analizuje algorytmy rozproszone; potrafi uzasadnić ich poprawność i przeanalizować złożoność


K_U13

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_U14

potrafi w sposób popularny przedstawić najnowsze wyniki odkryć dotyczących sieci komputerowych, systemów obliczeniowych i informatyki w ogóle


Efekty uczenia się - kompetencje społeczne:

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

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

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

4. Dążenie do rozwoju: Jest nastawiony na nieustanne zdobywanie nowej wiedzy, umiejętności i doświadczeń; rozumie potrzebę ciągłego doskonalenia się i podnoszenia kompetencji zawodowych.

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


Metody dydaktyczne:

Wykład i laboratorium.

Metody dydaktyczne eksponujące:

- pokaz

Metody dydaktyczne podające:

- wykład informacyjny (konwencjonalny)

Metody dydaktyczne poszukujące:

- klasyczna metoda problemowa
- laboratoryjna

Skrócony opis:

W ramach wykładu zamierzam przedstawić modele obliczeniowe Pregel i MapReduce, rozmaite sposoby wyznaczania ich złożoności, algorytmy rozwiązujące konkretne problemy obliczeniowe. Przedstawię także najnowsze (z 2013 i 2014) wyniki badań pozwalające ostatecznie zapanować nad złożonością programów w obu tych paradygmatach.

Pełny opis:

Teoria informatyki obejmuje wiedzę o algorytmach rozwiązujących problemy o dowolnej złożoności obliczeniowej i przy dowolnych poziome równoległości. Praktyczna implementacja tych algorytmów napotykała do tej pory trudności nie do pokonania, np. nikomu nie udało się w praktyce zaimplementować teoretycznie doskonale rozpracowanego modelu przetwarzania PRAM. Zmiana tego stanu rzeczy dokonała się w 2004 wraz z opublikowanie informacji o modelu obliczeniowym MapReduce i jego praktycznej implementacji. Rok 2010 to pierwsza publikacja o Pregelu, tj. modelu i implementacji obliczeń na ogromnych grafach. Choć oba te modele są dość proste i można by rzec, że znane w literaturze, jednak ich przełomowość wynika, z tego, że udało się je zaimplementować w wielkiej skali, tj, na danych o wielkości rzędu 10^12 rekordów/obiektów i na tysiącach komputerów. Do tej pory, teoretycy potrafili zbudować algorytm na dowolnego n, ale praktycy potrafili je zaimplementować jedynie dla n nie większego niż 10^9. MapReduce i Pregel przesuwają te granicę o kilka rzędów wielkości.

W ramach wykładu zamierzam przedstawić oba modele obliczeniowe, rozmaite sposoby wyznaczania ich złożoności, algorytmy rozwiązujące konkretne problemy obliczeniowe za pomocą MapReduce i Pregel. Przedstawię także najnowsze (z 2013 i 2014) wyniki badań pozwalające ostatecznie zapanować nad złożonością programów w obu tych paradygmatach (wcześniej znano jedynie wycinkowe metody szacowania kosztów, z ograniczeniem się w zasadzie jedynie do kosztu komunikacji).

W ramach laboratorium przewiduję implementację i eksperymentowanie z otwartymi implementacjami obu tych paradygmatów obliczeniowych, np. Hadoop, Pregel+ i Giraph.

Literatura:

[1] Jeffrey Dean and Sanjay Ghemawat. 2004. MapReduce: simplified data processing on large clusters. In Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation - Volume 6 (OSDI'04), Vol. 6. USENIX Association, Berkeley, CA, USA, 10-10.

[2] Grzegorz Malewicz, Matthew H. Austern, Aart J.C Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. 2010. Pregel: a system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data (SIGMOD '10). ACM, New York, NY, USA, 135-146. DOI=10.1145/1807167.1807184 http://doi.acm.org/10.1145/1807167.1807184

[3] Semih Salihoglu, Jennifer Widom: Optimizing Graph Algorithms on Pregel-like Systems. PVLDB 7(7): 577-588 (2014)

[4] Da Yan, James Cheng, Kai Xing, Yi Lu, Wilfred Ng, Yingyi Bu: Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees, 2014

[5] Louise Quick, Paul Wilkinson, and David Hardcastle. 2012. Using Pregel-like Large Scale Graph Processing Frameworks for Social Network Analysis. In Proceedings of the 2012 International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2012) (ASONAM '12). IEEE Computer Society, Washington, DC, USA, 457-463. DOI=10.1109/ASONAM.2012.254 http://dx.doi.org/10.1109/ASONAM.2012.254

[6] Yufei Tao, Wenqing Lin, and Xiaokui Xiao. 2013. Minimal MapReduce algorithms. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD '13). ACM, New York, NY, USA, 529-540. DOI=10.1145/2463676.2463719 http://doi.acm.org/10.1145/2463676.2463719

Metody i kryteria oceniania:

Zaliczenie laboratorium odbywa się na podstawie 5-6 projektów zaliczeniowych wykonywanych częściowo na labach i częściowo samodzielnie.

Egzamin pisemny odbywa się po zakończeniu wykładów.

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, 15 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Krzysztof Stencel
Prowadzący grup: Piotr Przymus, Krzysztof Stencel, Piotr Wiśniewski
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, 50 miejsc więcej informacji
Koordynatorzy: Krzysztof Stencel
Prowadzący grup: Krzysztof Stencel, Piotr Wiśniewski
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
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 50 miejsc więcej informacji
Koordynatorzy: Piotr Wiśniewski
Prowadzący grup: Piotr Przymus, Piotr Wiśniewski
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" (w trakcie)

Okres: 2021-02-22 - 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, 50 miejsc więcej informacji
Koordynatorzy: Piotr Wiśniewski
Prowadzący grup: Piotr Przymus, Piotr Wiśniewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr letni 2021/22" (jeszcze nie rozpoczęty)

Okres: 2022-02-21 - 2022-09-20
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 50 miejsc więcej informacji
Koordynatorzy: Piotr Wiśniewski
Prowadzący grup: Krzysztof Rykaczewski, Piotr Wiśniewski
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.