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

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

Příspěvekod 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
Hail to you, champion:o)
Uživatelský avatar
Lada
Donátor
Donátor
 
Příspěvky: 165
Registrován: 9. 1. 2005 10:17
Bydliště: Slaný / zácpa na Evropské

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

Příspěvekod 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
Xerxes
Matfyz(ák|ačka) level I
 
Příspěvky: 37
Registrován: 23. 1. 2007 16:32
Bydliště: Zlínský kraj / Kolej 17. listopadu
Typ studia: Informatika Bc.

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

Příspěvekod 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
Hail to you, champion:o)
Uživatelský avatar
Lada
Donátor
Donátor
 
Příspěvky: 165
Registrován: 9. 1. 2005 10:17
Bydliště: Slaný / zácpa na Evropské

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

Příspěvekod 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!
zoufaly
 

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

Příspěvekod jkt » 15. 1. 2010 01:32

Terminy nejsou vypsane, zapocet pry probiha pred kazdym zkouskovym terminem. Na absolvovani je neomezeny pocet pokusu.
jkt
Matfyz(ák|ačka) level I
 
Příspěvky: 20
Registrován: 17. 5. 2007 13:02
Typ studia: Informatika Mgr.

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

Příspěvekod 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/
Hail to you, champion:o)
Uživatelský avatar
Lada
Donátor
Donátor
 
Příspěvky: 165
Registrován: 9. 1. 2005 10:17
Bydliště: Slaný / zácpa na Evropské

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

Příspěvekod 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.
zoufaly
 

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

Příspěvekod 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...
Hail to you, champion:o)
Uživatelský avatar
Lada
Donátor
Donátor
 
Příspěvky: 165
Registrován: 9. 1. 2005 10:17
Bydliště: Slaný / zácpa na Evropské

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

Příspěvekod 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
Vinc
Matfyz(ák|ačka) level I
 
Příspěvky: 9
Registrován: 4. 11. 2006 22:29
Typ studia: Informatika Mgr.

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

Příspěvekod Š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.
Štefan
Matfyz(ák|ačka) level I
 
Příspěvky: 6
Registrován: 27. 1. 2005 16:17
Bydliště: Praha


Zpět na NTIN090 Základy složitosti a vyčíslitelnosti

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 2 návštevníků