Informatika

Co je formální jazyk, abeceda a slovo. Základní pojmy teorie formálních jazyků vysvětlené na srovnání s běžným jazykem a na příkladech.

Konečný automat jako výpočetní model se stavy a přechody. Definice, stavový diagram, formalizace výpočtu a příklady přijímaných slov.

Nedosažitelné stavy konečného automatu, do kterých nevede žádný přechod. Definice a postup, jak je z automatu bezpečně odstranit.

Regulární jazyky jsou uzavřené na sjednocení, průnik, zřetězení i uzávěr. Co uzavřenost na operaci znamená a proč u regulárů platí.

Co je regulární výraz a jak popisuje množinu slov. Definice, srovnání s aritmetickými výrazy a vazba na konečné automaty.

Linear counting: jak odhadnout počet unikátních hodnot ve velkých datech. Hašovací funkce, bitové mapy a proč naivní postup nestačí.

Bloom filter je pravděpodobnostní datová struktura, která rychle odpoví, zda prvek je v množině. Princip, hašovací funkce a praktické použití.

« Předchozí: Matice přechodu

Další: Formální jazyky »