Algorytmy strumieniowe (streaming algorithms) zajmują się sytuacjami, w których dane wejściowe nie są dostępne do standardowego swobodnego odczytu. Zamiast tego program analizuje strumień danych (np. pojawiające się kolejno liczby), którego ze względu na ogromny rozmiar nie jesteśmy w stanie zapisać. Często dysponujemy jedynie pamięcią logarytmiczną względem rozmiaru wejścia, a jednak istnieją liczne algorytmy randomizowane, z wysokim prawdopodobieństwem wyliczające interesujące nas metryki danych.
Będziemy rozważać problem od strony teoretycznej, ale obecnie nie trzeba przesadnie się wysilać, by znaleźć przykłady odpowiadające temu modelowi. Jeśli chcemy analizować dane np. z wielkiego portalu internetowego, całej giełdy lub czujników fizycznych (w nowoczesnych laboratoriach czy satelitach), możemy mieć do czynienia z terabajtami danych napływającymi każdej godziny, co trudno w całości zapisywać, a już w szczególności obsłużyć w pamięci RAM. Innym przykładem są routery i różne urządzenia sieciowe, obsługujące potężną ilość pakietów w porównaniu do ich możliwości obliczeniowych.
Na seminarium jesteśmy zainteresowani podstawowymi problemami streamingowymi, jak: \
-probabilistyczne liczniki, używające mniej niż logn bitów, \
-analiza częstości danych, jak liczba elementów unikalnych lub liczność najczęstszego elementu w ciągu liczb, \
-wszelkie rodzaju szkice (sketche) danych liczbowych i nie tylko, gdzie stosowane są główne sprytne losowe próbkowania danych, haszowanie, i ich złożenia, \
-algorytmy grafowe lub szkice dla grafów, \
-elementarne ograniczenia dolne na możliwy rozmiar pamięci, \
-być może również problemy tekstowe oraz algorytmy działające w przesuwającym się oknie ("ostatnie _k_ liczb", w każdym momencie).
Będziemy zajmować się przedstawieniem i analizą prostszych prac w dziedzinie, lub nawet częściej elementów dostępnych kursów które w przystępniejszy sposób opisują konkretne zagadnienie lub jego fragment,
np. jak w notatkach Amita Chakrabarti
(https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf) oraz kilku innych kursach.
Wymagania to głównie podstawowa znajomość rachunku prawdopodobieństwa, dyskretne zmienne losowe. Obliczenia są raczej pomysłowe niż złożone/długie, niemniej trzeba uważnie analizować prawdopodobieństwa zdarzeń.
