Diff for ''

Revision 107
Author:
black
Time:
2024-03-04 23:28
Revision 9
Time:
2024-09-18 21:04
Comment:
Automatizovaná konverze z MediaWiki do Markdownu
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
== Jak se sem dostanete ==
Nejobvyklejší cesta vede ze stanice metra Hradčanská tramvají 1 nebo 18 do zastávky 'Větrník'.
Další možnost je dojet metrem až na Dejvickou a odtud tramvají 2 opět do zastávky 'Větrník'.
Z Andělu je možné sednout na autobus 191 a nechat se dovézt až na zastávku 'Koleje Větrník', nebo ze stanice 'Nové Butovice' na stejnou zastávku jezdí autobusy 179 a 184.
{{Předmět|Základy složitosti a vyčíslitelnosti|Petr Kučera|NTIN090}}
Line 6: Line 3:
== Jak to tu vypadá == Ú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 8: Line 5:
Dvojlůžkové pokoje (2,5 × 5 m). Výjimkou jsou 3 trojlůžáky na druhém bloku. Bydlení tam je levnější, ale tři lidi mají společné dvě skříně, takže trocha komfortu chybí. Sociální zařízení a kuchyňka jsou všude společná pro patro (cca 40 lidí). # Zápisky #
Line 10: Line 7:
=== Ubytování === [Řešené otázky NTIN090](Řešené%20otázky%20NTIN090)
Line 12: Line 9:
Větrník má 4 bloky. # Zápočtový test #
Line 14: Line 11:
'''I. blok''' je lukrativní místo s dobrým výhledem směrem na východ. Západní strana je na tom hůře. Má společnou vrátnici s II. blokem a díky většímu počtu lidí jsou u vrátnice instalovány automaty na všelico možné. * 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
Line 16: Line 19:
'''II. blok''' má podle mnoha lidí nejsilnější atmosféru. Má pověst hlučného bloku s častými večírky. Východní strana má výhled na fotbalové "hřišťátko" (rozuměj udusanou hlínu) a dále přes sousedy, věčně a hlučně opravující loď, až do oken bloku 3.A. Západní strana má romantický výhled na parkoviště a především na Billiard Club. Společná vrátnice s 1. blokem zajišťuje oběma blokům výhodnou pozici. Mají to nejblíž na autobus, do hospody, do obchodu, na tramvaj. Na ubytovačku o něco dál, než 3.blok. K menze to má nejdál, ale ta je stejně tak daleko, že to nehraje skoro roli. ## 10. 1. 2011 ##
Line 18: Line 21:
'''III. blok''' je rozdělen na dva podbloky. Blok III. A a III. B.<br />
Ačko, kam se dostanete, když na vrátnici zahnete doprava, má na západ výhled na 2. blok a sousedy, na východ kouká na 3.B. Béčko (na vrátnici doleva) zas na západ kouká na 3.A a na východ na blok 4. Pokoje na koncích chodeb se vyznačují bonusem - mají navíc jedny prosklené francouzské dveře a nejvyšší patra z nich ten nejlepší výhled jaký můžete na této koleji mít. Celý blok je podstatně tišší a klidnější než 2, chodby jsou kratší a vzniká tady rychleji takové domáčtější prostředí. K tomu přispívá i možnost vysedávání (např. u grilu) uvnitř 'podkovy', kde je klid a poměrně zeleno. Blok je čerstvě po zateplení a rekonstrukci koupelen. Vzdálenostmi je na tom průměrně. Všude to má dál, jen k ubytovačce to má kousek.
* 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.
Line 21: Line 32:
'''IV. blok''' je rozdělený na IV. A a IV. B stejně jako III. blok. Je často obsazován zahraničními studenty a podle toho to tam vypadá. Párty, oslavy, křik, kterému nerozumíte. Občasné kulturní rozdílnosti způsobují problémy. Přesto, nebo právě proto, se do něj investují největší peníze. Je zateplený, rekonstruované koupelny a jsou tam automaty na vrátnici. Má to nejdál na ubytovačku, do obchodu, na autobus a na tramvaj. Zase k menze na Kajetánce to má nejblíž. ## 8.2.2010 ##
Line 23: Line 34:
'''Vybavení bloků''' prochází poslední dobou průběžnou obnovou. Všude jsou nové postele (na III. A nejnovější a nejlepší). Nábytek je nový na IV. bloku a na některých pokojích bloku 1. Jinde je nábytek takový, že na něm můžete najít vyrytý i podpis vašich rodičů z dob studijních. Ale nezoufejte - dá se esteticky vylepšit a svou kvalitu prokazuje již několik desetiletí.
Na podlaze je linoleum, stěny jsou děravé a padá z nich omítka. Je možné si vymalovat a nechat proplatit barvu. Stejně tak v nouzi můžete poprosit údržbáře, zda by vám nepůjčil nářadí, případně sám nepomohl při zkulturňování pokoje.<br />
V přízemí jsou v oknech mříže. III. a IV. blok má okna plastová. Z těch ostatních starých se odlupuje barva a dělá binec v pokoji.<br />
Pokoje na všech blocích jsou zasíťované a na každém jsou 2 ethernetové zásuvky. Připojení rychlostí 100MBit zajišťuje [http://kam.cuni.cz KaM]. Každý připojený má vlastní veřejnou IP adresu, ale všechna příchozí spojení jsou blokována, tedy zapomeňte na ssh, ftp, www, apod. servery přístupné z divočiny internetu. Abyste mohli na internet, je nutné si zaregistrovat MAC adresu a k tomu potřebujete ID Univerzity Karlovy. Studentům jiných škol jako nápověda slouží [http://kam.cuni.cz/KAM-66.html tato stránka].
* 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)
Line 28: Line 39:
Ve většině pokojů jsou ledničky (dokupují se další).<br />
Záchod, sprchy a kuchyňku uklízí každý všední den uklízečka, takže máte všude čisto bez práce. Tedy alespoň do té doby, než to nějaké čuně před vámi zaneřádí.
## 4.2.2010 ##
Line 31: Line 41:
Na závěr, nezapomeňte, že každý pokoj se dá zútulnit. :)
   
=== Co najdete na koleji a kolem ní ===
* 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.
Line 35: Line 46:
Na II. a III. bloku je ping-pongový stůl, na II. bloku je posilovna, kterou spravuje KR. Na I. bloku jsou dvě místnosti s klavírem - najdete tu jak klasický klavír, tak křídlo. Na III. bloku je další klavír. Na každém bloku je řada studoven a po jedné televizní místnosti. ## 28.1.2010 ##
Line 37: Line 48:
Za druhým blokem najdete menší fotbalové hřiště s mizernými brankami, ale hrát se tam dá dobře. Za prvním blokem je volejbalové hřiště s antukou. Pokud jej chcete využívat, ptejte se na vrátnici. Za kolejí je veliký sad, kde se dá buď učit pod stromem, nebo na lavičce, když je teplo, nebo si tam i zaběhat. * 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?
Line 39: Line 53:
Kousek od koleje jsou tři obchody (2×Billa, 1×Norma), pošta, 2×drogerie, hospoda (cca 4×, podle toho jak daleko chcete jít) a spousta dalšího. ## 27.1.2010 ##
Line 41: Line 55:
Přímo v budově prvního bloku je Bécéčko (Billiard Club), zakouřená hospoda, kde se dá zahrát kulečník nebo i fotbálek. Pro nekuřáky tam mají i salónek, překvapivě relativně bez kouře (nebojte se, stejně pak budete smrdět). Asi 5 minut pěšky můžete jít na Hvězdu do [http://www.klubhvezda.cz/ klubu], kde jsou skoro každý den diskotéky. * 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
Line 43: Line 60:
Nevýhoda bydlení na sousední koleji Hvězdě je v tom, že hned vedle je umístěna plochodrážní dráha, která vás může občas rušit (hlavně pokoje, které mají okna obrácena k dráze). Radši pojďte na Větrník, je to kousek. ## 13.1.2010 ##
Line 45: Line 62:
Docela slušně tu funguje společenský život. Stačí se jen trochu zajímat. Určitě si prohlédněte [http://www.vetrnik.koleje.cuni.cz/diskuse/ naše fórum], najdete tam mnoho informací a třeba i nějaká překvapení. ;) * 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
Line 47: Line 67:
=== Matfyzáci === # Zkouška #
Line 49: Line 69:
Od doby, kdy zdražili kolej 17. listopadu, je na Větrníku mnohem víc matfyzáků. A hlavně, tady nejsou zavření v buňkách u počítače, ale pořád se tu něco děje. Matfyzáků je tu opravdu dost. * 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.
Line 51: Line 73:
== Vzdálenost od školy == # Zdroje #
Line 53: Line 75:
* nám. Jana Palacha
**tram 18 -> Staroměstská (~20 minut)
* Malá Strana
**tram 18 -> Malostranská, tram 12,20,22,23 -> Malostranské Náměstí (~25 minut)
**tram 1,18 -> Hradčanská, tram 20 -> Malostranské náměstí (~25 minut)
**tram 1,2,18 -> Vozovna Střešovice, přesun asi 2min, Brusnice, tram 22,23 -> Malostranské náměstí (~25 minut)
* Karlín
**tram 1,18 -> Hradčanská, tram 8 -> Křižíkova (~35-40 minut)
**tram 1,18 -> Hradčanská, metro A -> Můstek, metro B -> Křižíkova (~35 minut)
**tram 2 -> Dejvická, metro A -> Můstek, metro B -> Křižíkova (~35 minut)
* Trója
**tram 1 -> Vltavská, metro C -> Nádraží Holešovice, bus -> Kuchyňka (nebo Pelc Tyrolka) (~45 minut)
**tram 1,2,18 -> Vozovna Střešovice, tram 15 -> Nádraží Holešovice, bus -> Kuchyňka (nebo Pelc Tyrolka) (~45 minut)
* Hostivař
**tram 1,18 -> Hradčanská, metro A -> Skalka, bus 154,271 -> Gercenova (~60 minut)
**tram 2 -> Dejvická, metro A -> Skalka, bus 154,271 -> Gercenova (~60 minut)
* Motol
**bus 179,184 -> Nemocnice Motol/Motol (~15 minut)
* Karlovo náměstí, Albertov
**tramvaj 18 -> Karlovo náměstí/Albertov (~30 minut)
**bus 191 -> Anděl, tram 7 -> Albertov (~30 minut)

== Odkazy ==

[http://www.vetrnik.koleje.cuni.cz/ www.vetrnik.koleje.cuni.cz/] Stránky KR Větrník

[http://www.vetrnik.koleje.cuni.cz/diskuse/ www.vetrnik.koleje.cuni.cz/diskuse/] Diskuzní fórum

[http://www.ff.cuni.cz/dok/studium/lekar.php http://www.ff.cuni.cz/dok/studium/lekar.php] Ordinace praktického lékaře pro studenty na Hvězdě

== Akce, možnosti ==

Nechce se vám tahat knihy na kolej? Pro studenty dějin umění, kulturologie, historie a podobných oborů je tu řešení: [http://obrazar.2web.cz/obrazar/knihovna.phtml MiniKnihovna na Větrníku]

A ještě pro studenty dějin umění: sháníte zkušnosti, grantovou historii, položky do CV?
http://obrazar.2web.cz/obrazar/mista.phtml

Na koleji funguje už delší čas klub [http://www.coolnicka.cz Coolnička], který vedou převážně křesťani z koleje. Pořádá mimo jiné středeční diskuzní večery a pondělní kavárnu [http://www.coolnicka.cz/index.php?htm=mm&mnu=4 Mississipi Mud].

== Adresa ==
Kolej Na Větrníku
 Na Větrníku 1932
 162 00 Praha 6 - Petřiny

bloky I-II: čp. 1931,
blok III: čp. 1933,
blok IV: čp. 1934
(Pokud nechcete hledat poštu po všech blocích koleje, pište do adresy přesný blok a pokoj)
[[Category:Koleje]]
* [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)