Informatyka
Języki formalne
Czym jest język formalny, alfabet i słowo. Podstawowe pojęcia teorii języków formalnych wyjaśnione przez porównanie ze zwykłym językiem i na przykładach.
Automaty skończone
Automat skończony jako model obliczeń ze stanami i przejściami. Definicja, diagram stanów, formalny opis obliczenia i przykłady akceptowanych słów.
Redukcja automatu
Stany nieosiągalne automatu skończonego, do których nie da się dostać ze stanu początkowego. Definicja i sposób, jak je bezpiecznie usunąć z automatu.
Domkniętość języków regularnych
Języki regularne są domknięte ze względu na sumę, przecięcie, konkatenację i domknięcie Kleene’ego. Co znaczy domkniętość ze względu na działanie i dlaczego zachodzi dla języków regularnych.
Wyrażenia regularne
Czym jest wyrażenie regularne i jak opisuje zbiór słów. Definicja, porównanie z wyrażeniami arytmetycznymi i związek z automatami skończonymi.
Szacowanie liczby unikalnych wartości
Linear Counting: jak oszacować liczbę unikalnych wartości w dużych zbiorach danych. Funkcje haszujące, mapy bitowe i dlaczego naiwne podejście nie wystarcza.
Filtr Blooma
Filtr Blooma to probabilistyczna struktura danych, która szybko odpowiada, czy element należy do zbioru. Zasada działania, funkcje haszujące i praktyczne zastosowanie.