KA07 – Operace s konečnými automaty

S konečnými automaty můžeme pracovat obdobně jako s množinami. Můžeme na ně aplikovat různé operace jako sjednocení, průnik, zřetězení, iterace, doplněk, zrcadlový obraz, kvocient, atd. Na úvod je zapotřebí si definovat třídu všech jazyků rozpoznatelných konečným automatem F.

Continue reading

Nový algoritmus řeší problém izomorfních grafů

10. listopadu na semináři Kombinatoriky a teoretické informatiky na Univerzitě v Chicagu představil počítačový vědec László Babai svůj nový algoritmus, který řeší problém izomorfních grafů. Co to vlastně jsou izomorfní grafy? Následující obrázek ukazuje dva různé grafy, které jsou naprosto totožné, byť každý vypadá úplně jinak:

isomorphism

Continue reading

Jim Parsons a evoluce počítačů

KA06 – Převod ZNKA na DKA

Zobecněný nedeterministický konečný automat lze převést přímo na deterministický konečný automat pomocí následujícího algoritmu. Je obdobný stromovému algoritmu převodu NKA na DKA. Nejprve si ale musíme vysvětlit, co je to E-funkce.

Continue reading

Ledové sopky na Plutu

Nejnovější data z mise New Horizons stále přinášejí překvapivé zprávy. Podle posledních informací to vypadá, že na Plutu existují útvary podobné našim sopkám, které ale nechrlí lávu a kameny, ale led.

Continue reading

KA05 – Zobecněné NKA

Představíme-li si automat takový, že dokáže přecházet mezi jednotlivými stavy, aniž by načetl jakýkoliv vstupní symbol, hovoříme o zobecněném nedeterministickém konečném automatu, a tyto speciální stavy se nazývají ε-přechody.

Continue reading

KA04 – Ekvivalentní automaty

Přestože dva konečné automaty obsahují rozdílný počet stavů, rozdílný počet a tvar přechodových funkcí, mohou být ekvivalentní.

Definice 1: Konečný automat A a konečný automat B jsou ekvivalentní, pokud oba rozpoznávají jeden společný jazyk, tedy L(A) = L(B).

Abychom mohli velice jednoduše ověřit, zdali dva konečné automaty jsou ekvivalentní, je zapotřebí nejprve definovat dosažitelnost a nedosažitelnost každého stavu.

Definice 2: Pokud existuje pro daný konečný automat slovo w takové, že pak je stav q dosažitelný. V opačném případě je daný stav nedosažitelný.

Continue reading

KA03 – Převod NKA na DKA

Všechny nedeterministické konečné automaty se dají pomocí jednoduchého algoritmu převést na deterministické konečné automaty. Je zapotřebí pouze sjednotit vstupní stavy do jednoho deterministického vstupu a definovat nové vnitřní stavy, které budou odpovídat všem variacím z nedeterministické množiny.

Continue reading

KA02 – Způsoby zápisu konečných automatů

Každý konečný automat můžeme reprezentovat různými způsoby zápisu. Lze použít výčet jednotlivých prvků automatu, tedy stavů a přechodových funkcí, dále lze použít reprezentaci pomocí tabulky, stavového diagramu či stavového stromu.

Reprezentace výčtem prvků

Continue reading

Tisk solárního inkoustu

Spojením univerzity v Melbourne, Monash a vědecké a průmyslové výzkumné organizace CSIRO vznikl Victorian Organic Solar Cell Consortium, který se od roku 2007 zabývá technologií tisku solárních panelů. Objevili nový způsob tvorby solárních článků pomocí tisku. Články mají sice desetkrát nižší kapacitu než standardní články vyráběné sériovým způsobem, dají se ale na druhou stranu tisknout na jakékoliv povrchy, například plasty či sklo. Údajně mají lepší konzistenci než křemík a pracují tedy i za horších klimatických podmínek, například při zatažené obloze. Do budoucna se plánuje tisk solárního inkoustu na obaly telefonů či tabletů, které by se takto mohly průběžně dobíjet, případně na skla budov.