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

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: [NTIN090] Základy složitosti a vyčislitelnosti

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

od Štefan » 9. 2. 2011 10:07

Lada píše: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 píše: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 píše: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.

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

od Vinc » 27. 1. 2010 11:47

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

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

od Lada » 16. 1. 2010 13:23

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...

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

od zoufaly » 15. 1. 2010 19:05

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.

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

od Lada » 15. 1. 2010 02:11

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/

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

od jkt » 15. 1. 2010 01:32

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

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

od zoufaly » 14. 1. 2010 18:15

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!

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

od Lada » 13. 1. 2010 21:13

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

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

od Xerxes » 12. 1. 2010 18:42

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

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

od Lada » 11. 1. 2010 23:07

Zdarek,

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

Dik

Lada

Nahoru