[NTIN090] Základy složitosti a vyčislitelnosti

Zdarek,

byli jste nekdo dneska na prvnim zapoctovem testu? Nepodelite se s dojmy? Hlavne co zhruba jsou otazky + jak se to hodnoti?

Dik

Lada

Slyšel jsem ze dvou různých zdrojů, že to bylo prý jednoduché - 4 příklady naprosto srovnatelné s těmi, co se dělaly na cvičeních:

1. Konstrukce TS rozpoznávající nějaký jazyk

2. Konstrukce PRF z axiomů a odvozovacích pravidel

3. Úloha na s-m-n větu

4. Převod jedné úlohy na druhou

tak dneska byl test taky vcelku prijemny - urcite by nemel delat problem lidem co chodili na cviceni:

1. popsat TS, ktery prijima jazyk { 1 na ( 2 na x), x >=0}

2. odvodit ze x-1 je PRF

3. pokud mam blackbox ktery resi rozhodovaci SAT (ANO/NE) jak pomoci nej sestrojim algoritmus ktery najde dane ohodnoceni promennych

4. dokaz ze celociselne programovani je NP-uplne

Ahoj,
na poslednim cviceni na kterem jsem byl(v pulce semestru) ptal jsem se na podminky na zapocet. Rikal ze rozepise termin na zapoctovy test a ze bude v SISu. Nejak jsem ho tam nevidel a tady ctu, ze uz dva terminy byly. Jeho stranky neznam(pokud nejake ma), tak bych byl vdecny kdyby mi nekdo mohl rict, jak a kde se da zjistit, jestli dalsi termin na zapocet vubec bude a kdy?
Dekuji!

Terminy nejsou vypsane, zapocet pry probiha pred kazdym zkouskovym terminem. Na absolvovani je neomezeny pocet pokusu.

presneji receno na kazdem zkouskovem terminu muzes psat i zapoctovy test, na to se nemusis nikam prihlasovat

jinak Kucerovy stranky jsou trochu schovane, ale docela uzitecne:)
http://ktiml.mff.cuni.cz/~kucerap/NTIN090/

Diky moc! To me potesilo. Nechci otravovat, ale kdyz uz vim, ze ten zapocet jeste muzu ziskat, zacina me zajimat prubeh zkousky :) a rad bych to zkusil 18. v pondeli. Nerikal nahodou jeste jak to bude vypadat? 1.kolik asi otazek 2.priklady taky jak u zapoctu, nebo jenom definice teoreme, tvrzeni, dukazy 3. nebo ma nejaky uplne jiny system zkouseni(test mozna :) ) ? Abych vedel jak se mam ucit, pripadne cemu venovat... Takhle to zabira dost casu a jeste si nejsem jisty jestli to dostatecne umim.

no - ve stredu na zapoctu se zminil o tom, ze by ta zkouska mela vypadat podobne jako je treba na slozitosti - tj. test se spis praktickymi ulohami a potom ustni spis s teorii... ale jednim dechem dodal, ze zatim zadny test nevymyslel, tak to neni uplne na 100%...
jinak ale myslim ze je nutne nejdriv udelat zapocet a az pak muzes jit na zkousku... nebo to muzes delat najednou, ale to je vcelku casove narocne...

** Zapoctova pisomka 27/01/2010:**
(1) Popiste TS pre jazyk L={a^{i}b^{i}c^{i}; i z N}
(2) Ukazke ze sign(x) je PRF
(3) Za pomoci nektereho problemu z prednasky dokazte, ze Hamiltonovska cesta HC(s,t) je NP-uplny problem
(4) Ukazte, ze pre hornovsku KNF existuje polynomialny algoritmus, ktory najde splnujuce ohodnotenie

Lada wrote:presneji receno na kazdem zkouskovem terminu muzes psat i zapoctovy test, na to se nemusis nikam prihlasovat

To už není pravda a dnes jsem na tom vyhořel. Budu si muset počkat do letního zkouškového nebo ho hodně přemlouvat, aby dal ještě nějaký termín v semestru - již na zimní zkouškové nechce vypisovat žádné zkouškové termíny (a tedy možnosti domluvit se s ním, že by si někdo napsal zápočet).

Lada wrote:jinak Kucerovy stranky jsou trochu schovane, ale docela uzitecne:)
http://ktiml.mff.cuni.cz/~kucerap/NTIN090/

Ano, tady je výslovně napsáno, jak to se zápočty (letos) je:

http://ktiml.mff.cuni.cz/~kucerap/NTIN090 wrote:Další možnost napsání zápočtové písemky je během zkouškové písemky v prvních dvou termínech 17.1. a 20.1. v S1, nemusíte se zvlášť hlásit, další možnosti po dohodě.

Tyto stránky se aktualizují podle potřeby bez upozornění a v době, kdy jsem se snažil zorganizovat plán na zkouškové, tam ještě onen text nebyl.