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

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 Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
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 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.
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
- referatu

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.

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.

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 ustny odbywa się po zakończeniu wykładów

Zajęcia w cyklu "Semestr letni 2021/22" (zakończony)

Okres: 2022-02-21 - 2022-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 32 miejsc więcej informacji
Koordynatorzy: Piotr Wiśniewski
Prowadzący grup: Dawid Maliszewski, Krzysztof Rykaczewski, Piotr Wiśniewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin
Uwagi:

Dla przedmiotu utworzony jest zespół na platformie MS-TEAMS.

kod zespołu: 0i6b0fh

W przypadku zajęć zdalnych wykłady odbywać się będą w formie synchronicznej na spotkaniach tegoż zespołu

Zajęcia w cyklu "Semestr letni 2022/23" (zakończony)

Okres: 2023-02-20 - 2023-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 32 miejsc więcej informacji
Koordynatorzy: Piotr Wiśniewski
Prowadzący grup: Dawid Maliszewski, Krzysztof Rykaczewski, Piotr Wiśniewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin
Uwagi:

Dla przedmiotu utworzony jest zespół na platformie MS-TEAMS.

kod zespołu: 0i6b0fh

W przypadku zajęć zdalnych wykłady odbywać się będą w formie synchronicznej na spotkaniach tegoż zespołu

Zajęcia w cyklu "Semestr letni 2023/24" (w trakcie)

Okres: 2024-02-20 - 2024-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 32 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
Uwagi:

Dla przedmiotu utworzony jest zespół na platformie MS-TEAMS.

kod zespołu: 0i6b0fh

W przypadku zajęć zdalnych wykłady odbywać się będą w formie synchronicznej na spotkaniach tegoż zespołu

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)