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

<{ForumPost(poster="Lada", timestamp=2010-01-11 23:07:29)}>
Zdarek,  
  
byli jste nekdo dneska na prvnim zapoctovem testu? Nepodelite se s dojmy? Hlavne co zhruba jsou otazky + jak se to hodnoti?  
  
Dik  
  
Lada
<{/ForumPost}>

<{ForumPost(poster="Xerxes", timestamp=2010-01-12 18:42:33)}>
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

<{/ForumPost}>

<{ForumPost(poster="Lada", timestamp=2010-01-13 21:13:37)}>
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
<{/ForumPost}>

<{ForumPost(poster="zoufaly", timestamp=2010-01-14 18:15:56)}>
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!
<{/ForumPost}>

<{ForumPost(poster="jkt", timestamp=2010-01-15 01:32:19)}>
Terminy nejsou vypsane, zapocet pry probiha pred kazdym zkouskovym terminem. Na absolvovani je neomezeny pocet pokusu.
<{/ForumPost}>

<{ForumPost(poster="Lada", timestamp=2010-01-15 02:11:26)}>
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/](http://ktiml.mff.cuni.cz/~kucerap/NTIN090/)
<{/ForumPost}>

<{ForumPost(poster="zoufaly", timestamp=2010-01-15 19:05:13)}>
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.
<{/ForumPost}>

<{ForumPost(poster="Lada", timestamp=2010-01-16 13:23:10)}>
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...
<{/ForumPost}>

<{ForumPost(poster="Vinc", timestamp=2010-01-27 11:47:55)}>
** 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
<{/ForumPost}>

<{ForumPost(poster="Štefan", timestamp=2011-02-09 10:07:59)}>

 > 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/](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](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.
<{/ForumPost}>