Seminaria ogólnoinstytutowe:

Streszczenie (autorskie):

W czasie referatu zostaną przedstawione częściowe wyniki z przygotowywanej rozprawy doktorskiej, której tematem jest efektywna predykcja. Przez predykcję rozumie się tu działanie pewnej całkowitej obliczalnej funkcji, przyjmującej jako argument słowo binarne i zwracającej 0 lub 1. O predyktorze można myśleć jako o algorytmie zgadywania przyszłego zdarzenia na podstawie informacji o przeszłych zdarzeniach. W szczególności, interesować będzie autorów asymptotyczne zachowanie błędu predykcji rozumianego jako odległość Hamminga między prefiksami ciągu, który autorzy starają się przewidzieć, a odpowiedziami predyktora.

Na początku zostanie rozważona predykcja ograniczona do indywidualnych ciągów (przypadek deterministyczny). Zostanie przedstawionych kilka wyników dotyczących istnienia ciągów binarnych dla których:

1. dowolny predyktor nie ma granicy błędów,
2. każdy predyktor ma granicę błędów równą 1/2 i
3. nie istnieje predyktor optymalny.

Z punktu widzenia teorii obliczeń szczególnie interesujące są ciągi rekurencyjnie przeliczalne. Tam gdzie jest to możliwe, zostanie przedstawiona odpowiedź na pytanie o istnienie rekurencyjnie przeliczalnych ciągów o zadanych własnościach asymptotycznych predykcji. Na koniec zostanie zarysowana problematyka predykcji dla binarnych procesów stochastycznych (przypadek niedeterministyczny), ze szczególnym uwzględnieniem kontekstu algorytmicznej teorii losowości. Krótko zostanie przedstawione pojęcie losowości w sensie Martina-Loefa i zarysowane otwarte problemy związane z predykcją ciągów algorytmicznie losowych.