Fórum studentů MFF UK

Test je podobný jako všechny. Doporučuji se dobře naučit pojmy. Určitě tam bude dotaz, jestli je něco extenze. Jinak test je na 90 min, což není moc prostoru na vymýšlení něčeho z ničeho. Není žádné oznámení 15 min do konce nebo tak, jediné, co bylo: "za minutu konec, pomalu dopište". Takž...

1) sestavte automat AC pro hledání zadaných jehel 2)Dokažte, že Batoh(věci, váhy, kapacita, cíl) je NP-úplný (použijte problémy probírané na přednášce) 3)pomocí algoritmu na hledání maximálního toku (ten nepopisujte ani nevysvětlujte) najděte (hranovou) souvislost grafu v polynomiálním čase. Dokažte...

4 úlohy: 1) 5 bodů Definujte latinský čtverec, ortogonalní čtverce + příklad o. čtverců řádu 3. 2) 10 bodů Formulujte Singletonuv, Hamminguv a Gilbert-Varshamovuv odhad a jeden z nich dokažte. 3) 5 bodů Formulujte Ramseyovu větu pro nekonečnou spocetnou množinu a definujte netrivialni pojmy z formul...