Fórum studentů MFF UK

1. Nakreslete graf a tabulku zpetne a vystupni funkce podle algoritmu Aho-Corasickova pro slova strom, stroj, postroj, trojka. 2. Mate mrizku n * n, kde je m cernych bodu a ostatni bile. Navrhnete polynomialni algoritmus, ktery zjisti, jestli existuje prave m cest z cernych bodu do nejakych bilych n...

Ano. Ale doporucuji ti si to nejdrive sam rozmyslet, jde celkem o jednoduchou myslenku. Udelas si pole cisel (v tomto pripade 64-bitovych integeru), ktere bude dlouha tolik, kolik je znaku na prvnim radku, tzn. max 255. Kazda bunka bude reprezentovat jeden znak na tom prvnim radku. Pak zacnes cist t...

Vstup: neomezene velky soubor, jen 1. radek obsahuje max. 255 znaku. Proces: Hledat vsechny vybrane podposloupnosti ve tvaru 1. radku. Vystup: Pocet vsech vybranych podposloupnosti. Priklad: v souboru je na prvni radce slovo "SOS". Pak vysledek pro tento text: "ASOGSOSF" je 4. Ex...

postup pres 3-rozmernou tabulku v dynamickem programovani je spravny. Naopak naprosto chybny je postup pres hledani do hloubky (backtracking), za coz mi dal trojku a mohl jsem byt rad. Topfer je ale hodny clovek, na teorii se snazi najit neco, cemu rozumite. Jen je potreba mluvit jasne a formulovat ...

1. Definujte izomorfismus mezi grafy, izomorfni zobrazeni. Ukazte priklad dvou neizomorfnich stromu na 4 vrcholech, pokud takove existuji. 2. Jaky je maximalni pocet hran v grafu o n vrcholech bez trojuhelniku? Vysledek dokazte. (Ne rovinny, ale kterykoli i bez rovinneho nakresleni) 3. Mejme osm kar...

Zadani: 1) definujte znamenko permutace 2) veta o izomorfismu linearniho zobrazeni 3) co vim o elementarnich upravach (co meni/nemeni, jestli se daji zapsat jako maticovy soucin, pouziti, apod.) Jinak u 3) po me chtel dukaz tvrzeni ze A*B je regularni <=> A i B jsou regularni. Chce precizni vyjadrov...