Diff for ''
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| Oficiální stránky [http://ktv.mff.cuni.cz/ katedry tělesné výchovy], konkrétní sporty viz. níže. | {{Předmět|Základy složitosti a vyčíslitelnosti|Petr Kučera|NTIN090}} |
| Line 3: | Line 3: |
| = Historický šerm = * klub historického šermu se zaměřením na volný bojový šerm Duelanti od svatého Rocha přijímá nováčky * cvičí se 2x týdně pondělí a středa od 20:00 v tělocvičně ZŠ Lupáčova, Olšanské náměstí Žižkov * první měsíc bývá zdarma, potom cca 500kč / měsíc, pro nováčky se na první půlrok najde i nějaký ten meč * kontakt: https://www.facebook.com/duelanti/ |
Úvodní kurz do složitosti a vyčíslitelnosti. Lze nahradit předměty [Vyčíslitelnost I](Vyčíslitelnost%20I) a [Složitosti I](Složitost%20I). Na zkoušku se lze přihlásit pouze po úspěšném absolvování zápočtového testu. Ten se zpravidla píše na posledním cvičení, případně na kterékoliv zkoušce (na test se není nutné se hlásit předem, stačí přijít). |
| Line 9: | Line 5: |
| = Plavání = * matfyzáčtí plavci nejsou žádný B-čka: [http://plavani.matfyz.cz] * v [[SCUK|sportovním centru Univerzity Karlovy]] v hodinách pro veřejnost za 80 Kč na ISIC - [http://bazen-hostivar.717.cz/ Plavecký bazén Hostivař] - neoficiální, přesto stále aktualizované stránky * Plavecký bazén na Výstavišti [http://www.incheba.cz/bazen zde] * [http://www.pspodoli.cz/ plavárna v Podolí] ** možnost plaváni ve vnitřním krytém bazénu i ve vnějším, který je přes zimu vyhřívaný (kolem 27 stupňů) ** k dispozici je v ceně také pára (aka mokrá sauna) * ostatní na [http://www.koupani.cz/koupani/] |
# Zápisky # |
| Line 18: | Line 7: |
| = Squash = * centrum [http://www.squashe.cz/index.php?mm=hastal Haštal] - [http://www.squashe.cz/index.php?mm=hastal&s=2 ceny] pro studenty 130,- za kurt a hodinu (Pá, So, Ne večer dokonce 110,-) * [http://www.mybox.cz/squash-holesovice/ Squash Holešovice] - z Nádraží Holešovice cca 5min na zastávku Maniny (tram #12), [http://www.mybox.cz/squash-holesovice/cenik.htm ceny] pro studenty 130,- za kurt a hodinu |
[Řešené otázky NTIN090](Řešené%20otázky%20NTIN090) |
| Line 22: | Line 9: |
| * [http://www.squasharbes.cz/Default.aspx/ Squash Arbes] - Arbesovo náměstí, pro informatiky blízko ze školy, studentská cena 170,- za kurt a hodinu | # Zápočtový test # |
| Line 24: | Line 11: |
| = Bruslení = * zimní stadion [http://www.nikolajka.eu/ Nikolajka] - Anděl ** cena: 40,- Kč ** - mnoho lidí * stadion na [http://www.stvanice.cz/ Štvanici] ** cena: 80,- Kč ** + kulturní zážitek * stadion pri OC[http://www.icearena.cz/index.php Letnany] ** cena: 80,- Kč ** + kvalita ledu ** + servis ** - vzádlenost od Troje * [http://www.incheba.cz/main.php?pageid=56 malá sportovní hala] na pražském výstavišti ** cena: 50,- Kč ** + dostupnost z Troje ** - žádný bufet ani automat * bruslení [http://supermapy.centrum.cz/map.php?ql=&qlc=-1&bbox=3460802.697119341:5552560.1201646095-3462552.697119341:5553950.037860082&mapsize=1&poi=2,6,7,8&stred=0:0&origin=&sid=&okoli=&search_flag=6 v mrtvém rameni Vltavy] :) ** + stačí zajít na Palmovku a odtud seběhnout k vodě ** + cena :) ** - závislost na počasí * [http://www.praha13.cz/ruzne/stadion/ školní zimní stadion Bronzová] (metro B, stanice Lužiny) ** cena: 30,- Kč za hodinu, 50,- Kč za 3 hodiny ** - v sezóně 2005/2006 mimo provoz * stadion [http://www.hckobra.cz/ HC Kobra Praha] ** cena: 60,- Kč ** otevřeno pro veřejnost: So, Ne - 13:15 až 15:15 ** - vzdálenost (viz [http://www.mapy.cz/?query=Loc:%2050%C2%B01'53.17%22N,14%C2%B025'38.8%22E&zoom=16&mapType=base¢erX=133089632¢erY=135753376#centerX=133087791@centerY=135753054@typ=base@zoom=15@vizType=none@vizIds=none mapa]) ** - hodně lidí |
* 4 příklady z látky probrané na cvičeních (obtížnost nebývá odlišná) * pro úspěšné splnění je třeba mít aspoň 3 příklady správně z následujících okruhů * Konstrukce TS rozpoznávající nějaký jazyk * [Konstrukce PRF z axiomů a odvozovacích pravidel](Konstrukce%20PRF%20z%20axiomů%20a%20odvozovacích%20pravidel) * Úloha na s-m-n větu * Převod jedné úlohy na druhou * je znám případ, kdy Kučera dovolil nahlédnutí do slajdů z přednášky ## 10. 1. 2011 ## * Varianta A * Napište TS, který rozpoznává následující jazyk: $1^{x+1}01^{x+2}$ * Ukažte, že $f(x):=x!$ je PRF * Ukažte, že existuje $n$, pro které $W_n=\{k*n|k\in\mathbb{N}\}$. (Pokud použijete nějakou primitivně rekurzivní nebo částečně rekurzivní funkci, zdůvodněte, proč jde o primitivně nebo částečně rekurzivní funkci.) * Ukažte, že problém existence přípustného řešení 0-1 celočíselného lineárního programování je NP-úplný * Varianta B * Napište TS, který rozpoznává jazyk $1^{2^x}, x >= 0$. Stačil popis/postup. * Ukažte, že $2^x, x>=0$ je PRF. (odvození) * Ukažte, že existuje $n$, pro které $W_n=\{n^k | k \in\mathbb{N}\}$. * Ukažte, že rozvrhování je NPC. ## 8.2.2010 ## * Predpokladejte, ze M je TS s obousmerne nekonecnou paskou. Popiste, jak z M vytvorite TS s jednosmerne nekonecnou paskou, ktery "dela totez" co M. (stacil slovni popis bez instrukci) * Odvodte, ze funkce faktorial g(x)=x! je primitivne rekurzivni (za predpokladu, ze funkce nasobeni je PRF). * Popiste 2-aproximacni algoritmus pro obchodniho cestujiciho s trojuhelnikovou nerovnosti, ktery pouziva minimalni kostru. Ukazte, ze skutecne dany algoritmus dosahuje zmineho aprox. pomeru. * Ukazte, ze problem rozvrhovani je NP-uplny. (soucasti zadani byl popis problemu rozvrhovani z poznamek k cviceni) ## 4.2.2010 ## * Popsat TS pro jazyk $1^{k}01^{k^2}$. * Ukázat, že div je PRF. +, sign, - a * lze použít bez odvozování. * Ukázat, že existuje n, pro které $W_n = \{0,..,n\}$. * Za pomoci nějakého problému z přednášky ukázat, že klika je NP úplný problém. ## 28.1.2010 ## * Popište TS, který počítá funkci sčítání * Ukažte, že $x^y$ je PRF (můžete předpokládat, že sčítání a násobení PRF jsou) * Za pomoci některého problému, jehož těžkost jsme si ukazovali na přednášce, ukažte, že batoh je NP-uplný. * Definujeme-li problém DNF-SAT jako problém splnitelnosti formule v disjunktivně normální formě (DNF), jaká je složitost tohoto problému? Je to NP-úplný nebo patří do P? ## 27.1.2010 ## * Popiste TS pre jazyk L={a^{i}b^{i}c^{i}; i z N} * Ukazke ze sign(x) je PRF * Za pomoci nektereho problemu z prednasky dokazte, ze Hamiltonovska cesta HC(s,t) je NP-uplny problem * Ukazte, ze pre hornovsku KNF existuje polynomialny algoritmus, ktory najde splnujuce ohodnotenie ## 13.1.2010 ## * popsat TS, ktery prijima jazyk { 1 na ( 2 na x), x >=0} * odvodit ze x-1 je PRF * pokud mam blackbox ktery resi rozhodovaci SAT (ANO/NE) jak pomoci nej sestrojim algoritmus ktery najde dane ohodnoceni promennych * dokaz ze celociselne programovani je NP-uplne # Zkouška # * zkouška probíhá písemně s následnou debatou nad řešením. * v každé písemce je příklad na Riceovu větu * všechny příklady na převody bere Kučera z doporučené literatury, konkrétně - Garey, Johnson: Computers and intractability - a guide to the theory of NPcompleteness, W.H. Freeman 1978. Bere pouze ty jednodušší ze začatku. Není problém zapůjčit tuto knihu v knihovně, je tam prý v několika výtiscích. # Zdroje # * [Stránka předmětu](http://ktiml.mff.cuni.cz/%7Ekucerap/NTIN090/) * [Poznámky z cvičení](http://forum.matfyz.info/download/file.php?id=546) * [Emulátor primitivně rekurzivních funkcí](http://forum.matfyz.info/download/file.php?id=553) * [Johančiny pohádky z vyčíslitelnosti](http://web.archive.org/web/20100626015101/http://atrey.karlin.mff.cuni.cz/%7Ejohanka/vyuka/pohadky_vycislitelnost.html) |