Vladan Majerech - domácí stránka

Last Modified: 19.11.2017
Kdo a odkud jsi? ?

Valid HTML 4.01 Strict

Index

kontakt, zápočty, zkoušky, rozvrh, skripta, TeX/METAFONTware, Články k dynamickým datovým strukturám, Analýza hry Quarto, Důchodová reforma, Šifrovací hry, Hádanky, Arimaa


Kontakt

Termín konzultace je nejlepe dohodnout předem e-mailem jmeno.prijmeni@mff.cuni.cz(subj:Konzultace) - odpovím jak bude v mých silách.

Kde mne najdete?
Česká republika, Praha, budova MFF UK Malostranské náměstí 24, 3. patro číslo dveří 302.


Zápočty

NTIN090

Příklady:

  1. Ukažte, jak lze libovolný jednopáskový Turingův stroj $M$ převést na Turingův stroj $M'$, který v každém kroku provádí jen dvě ze tří možných akcí (tj. každá instrukce buď změní stav a pozici hlavy, změní stav a písmeno na pásce, nebo změní písmeno na pásce a pozici hlavy, ale neučiní všechny tyto akce najednou). [1 bod]
  2. Ukažte, že je-li $L$ částečně rozhodnutelný jazyk, pak i jazyk $L^*=\{w\;|\;(\exists k\in{\mathbb N})(\exists u_1, \dots, u_k\in L)[w=u_1u_2...u_k]\}$ je částečně rozhodnutelný. Při řešení mějte na paměti, že pokud $L=L(M)$ pro nějaký TS $M$, pak se může stát, že $M(w)$ se nezastaví pro $w\not\in L$. [2 body]
  3. Ukažte, že jazyk $L$ je rozhodnutelný, právě když existují rozhodnutelné jazyky $A$ a $B$, pro které platí, že $L=\{x\;|\;(\exists y)[\langle x, y\rangle\in A]\}= \{x\;|\;(\forall y)[\langle x, y\rangle\in B]\}$ (Nápověda: Vzpomeňte si na Postovu větu.) [2 body]
  4. Popište algoritmus (pro Turingův stroj), který ignoruje svůj vstup a na výstup vypisuje postupně všechna prvočísla v rostoucím pořadí. [1 bod]
  5. Ukažte, že rozhodnout, zda existuje vstup Turingova stroje $M_i$, pro nějž stroj použije stav $q_k$, je algoritmicky nerozhodnutelné. [2 body]
  6. Nechť $A\leq_mB$ a víme, že $B$ je jazyk přijímaný konečným automatem. Vyplývá z toho že i $A$ je přijímané konečným automatem? Proč? [1 bod]
Studentcelkem122121
Tomáš Novotný61221
Matěj Konečný9122121
Jiří Tumpach512101
Jiří Kučera61221
Adam Filandr61221
Jakub Arnold61221
Martin Dvořák9122121
Vojtěch Sejkora11
Gergely Tóth9122121
Pavel Madaj9122121
David Tomandl7122101
Martin Hora61221
Dalibor Zeman61221
Michal Klein9122121
Tadeáš Berkman41021
Filip Hauptfleisch61221
Juraj Eduard Páll61221
Jan Kolář9122121
Jan Vojnar412100
Jakub Hančin41021
Martin Homa41201
Richard Eliáš3120.5
Marek Žídek61221
Bohdan Ihnatchenko51121
Luka Ihnatchenko61221
Jana Bátoryová4121
Luis Sanchez2101
Jan Brýda7.50.512121
David Bouška321
Matěj Lieskovský6.50.511121

Zkoušky


Rozvrh

Pondělí9:00-10:30 S302přednáším"Testování software NTIN070"
Pondělí10:40-12:10 (lichý kalendářní) S1cvičím"Základy složitosti a vyčíslitelnosti NTIN090"
Pondělí12:20-13:50 S302přednáším"Dynamické grafové datové struktury NTIN023"
Úterý15:30-18:30 T-014přednáším"Teorii složitosti (01TSLO)"
Čtvrtek10:40-12:10 (lichý kalendářní) S8cvičím"Základy složitosti a vyčíslitelnosti NTIN090"
Čtvrtek12:20-13:50 (oba kalendářní) S8cvičím"Datové struktury I NTIN066"


Skripta

"Úvod do složitosti a NP-úplnosti", "Složitost a NP-úplnost" již dlouho nedoznala změn.
Psaní skript k přednášce "Dynamické datové struktury" jsem pozastavil, protože vzhledem k odbornosti tématu je český text nepotřebný, anglických článků je mnoho a obor se stále ještě rozvíjí. Články mohu zapůjčit.
Aktuálně píšu "Povídání o datových strukturách", které by se mělo s původně zamýšleným obsahem dynamických datových struktur překrývat. Sudá nebo lichá?
Slovníček "Vnitřnosti TeXu" je napsán do konce expand procesoru.
V září 2008 obhájila (pod mým vedením) rešeršní diplomovou práci koncipovanou jako výukový materiál pro „Testování software“ Anna Borovcová.


TeX/METAFONTware

Jako obdivovatel a intenzivní uživatel TeXu, a v poslední době i META(FONT/POST)u čas od času vytvářím (aspoň spoluvytvářím) nějaké pomůcky pro pohodlnější práci s těmito programy. Jednou z těchto pomůcek je mnou v roce 1994 vytvořené TeXmenu. Druhou je METAFONT-editor vytvořený Alešem Vanclem.

Jako zajímavé cvičení z TeXu a trochu taky z algebry a teorie kódování bylo vytvoření makra pro sazbu QR kódů.


Dynamické datové struktury

Kopie veřejně přístupných článků týkajících se dynamických datových struktur najdete u Martina Mareše v adresáři dga/papers. U mne můžete najít články Mikkela Thorupa a spol. týkající se amortizovaně polylogaritmických datových struktur Amortizované polylog datové struktury pro 1 a 2souvislost, 1souvislost s mazáním, Obecná metoda vylepšující randomizované algoritmy založené na vzorkování. Kromě toho zde můžete najít článek Moniky Henzinger (Rauch) Worst case datová struktura pro vrcholovou 2souvislost.

Quarto

Na semináři v Josefově Dole 1998 jsem se seznámil s matematickou hrou Quarto. Napadlo nás zkusit nalézt optimální strategii v této hře. První pokusy vedly k tomu, že jsme byli schopni hru prozkoumat do hloubky 7 (z 16). Zkusil jsem aplikovat různé techniky na urychlení výpočtu a podařilo se mi hru prozkoumat úplně. Hra je zajímavá hlavně obrovským množstvím symetrií, které umožnily tak výrazné prořezání prostoru konfigurací, že úloha již byla řešitelná.

Pravidla hry: Hra se hraje na čtverci 4x4, je k dispozici 2^4 figurek. (figurky jsou nízké/vysoké, bílé/černé, hranaté/kulaté, plné/duté ... od každého druhu jedna). Hru hrají dva hráči, kteří se střídají v tazích. Vždy jeden hráč určí figurku a druhý ji položí na desku. Vítězí hráč, kterému se podařilo vytvořit horizontální/verikální/diagonální čtveřici figurek, které jsou alespoň v jedné vlastnosti stejné. V případě, že se to nikomu nepodaří, končí hra remízou.

V adresáři ftp/quarto Naleznete příslušný program i výsledek 14 denního výpočtu.

Výsledkem analýzy je, že při správné hře obou hráčů končí hra remízou.

Variantou hry je hledat čtveřici i ve čtvercích 2x2 (sousední řádky a sloupce). Tuto variantu hry daný program nezkoumá, mám pocit, že pocet symetrii tím klesá na polovinu, a vzhledem k nárůstu rychlosti počítačů za posledních 5 let by neměl být problém upravit program a přepočítat výsledky i pro tuto variantu. Najde se zájemce?

Implementačně nejjednodušší je upravit program pro výpočet varianty hry, kde se čtveřice hledá i ve vrcholech libovolného obdélníku s horizontální a vertikální stranou (tytéž symetrie). Mám pocit, že neexistuje remizová pozice pro takováto pravidla hry.


Příprava podkladů pro rozhodnutí o důchodové reformě

V období duben 2004 - červen 2005 jsem se podílel na přípravě podkladů pro rozhodnutí o důchodové reformě. Více informací o výsledcích modelování se dozvíte zde.


Šifrovací hry

Byl jsem ukecán k účasti na šifrovací hře OSUD. Natolik se mi to zalíbilo, že jsem se účastnil i dalších her. Reportáž účastníka z těchto akcí přináším

Dnem2006 Svíčky2006 Tmou8(podzim2006)
Matrix3(2007) Bedna2007 Svíčky2007 Tmou9(podzim2007)
Matrix4(2008) Bedna2008 Svíčky2008 Tmou10(podzim2008)
Bedna2009 Svíčky2009 Tmou11(podzim2009)
Bedna2010 Svíčky2010 Tmou12(podzim 2010)
Bedna2012 Tmou14(podzim 2012)
PoTrati2013 Bedna2013 PoŠkole2013 Svíčky2013
PoŠkole2014
PoŠkole2015 Svíčky2015 Tmou17(Q)(podzim 2015)
PoŠkole2016 Svíčky2016

(Kalendář šifrovacích her).
Malá šifrovací pomůcka a podklady pro dálkově pořádanou šifrovačku pro doktorandy (často zabývající se harmonickou analýzou) na Morávce (Krušné hory). Nehledejte originální šifry, zajímavá byla spíš technika nápovědy formou mnohonásobného výskytu principu šifry, vzhledem k tomu, že se nedaly očekávat velké zkušenosti s šifrovačkama. Autoři šifrovaček Dnem, Matrix a hlavně Haluz určitě znovupoužití principu šifry prominou. Ukázalo se, že

Malá šifrovačka se v roce 2009 zopakovala. Posílal jsem mentiony co to šlo, ale hra která měla končit kolem 19h se protáhla až do 23h 30m. Museli jsme se uchýlit k předložení alternativní startovní šifry protože „typografické stegano“ se ukázalo být těžkým.
P.S.: Pro rok 2009. Když píšu že v anglické gramatice nemáte hledat šifru, myslím to vážně.
P.P.S: Každá šifra ukrývá aspoň 3 tajenky (dvě ukrývají dokonce 4).
P.P.P.S.: Naprosto nechápu, že se nikdo nezamyslel nad tím tiskovým zrcadlem.
4P.S: Pokud byste si tiskli zadání, použijte ghostview. Pokusy s Acrobatem nedávaly dobré výsledky.
5P.S: Kdybych to dělal teď, asi bych i před ROBINem odřádkoval. Ne. To by bylo extrémně snadné!
6P.S: Očekávám bezprostřední dojmy na e-mailu. Ne že to budete sepisovat rok :)


Hádanky

Hádanky považuji za stěžejní „médium“ pro rozvoj matematiky. Jsem přesvědčen že na mé matematické/informatické vzdělání mělo řešení hádanek přinejmenším tak velký vliv, jako celý školský systém. Nebavím se o dětských hádankách typu „leze, leze po železe, ...“, ale o hádankách, které ač mají triviální formulace, nejsou rozumě řešitelné bez zavádění vlastní nové terminologie, případně dobře zdůvodňují, proč k zavedení takové terminologie vůbec došlo ... MMO

Mé oblíbené hádankářské fórum je Wu forum a nejraději mám ty hádanky, co ještě nemám vyřešené ... „n vězňů a k-stavový přepínač“ (známý především pro 100 vězňů a „žárovku“, kde pravděpodobně držím světový rekord ... strategii s průměrem kolem 3430, 3390 3370 návštěv). K oblíbeným patří i hádanky, s řešením typu heuréka, které mi daly hodně zabrat a většina mých kamarádů matematiků je ještě nemá vyřešené. Příkladem je varianta „vězňů s čepičkami“, kteří opouštějí vězení, pokud alespoň jeden z nich oznamí číslo ze své čepičky. (Pro n-vězňů věznitel vytvoří seznam n přirozených čísel z intervalu 1 až n, a i-tému vězni pošle seznam upravený tak, že na místě i-tého čísla je volné místo. Vězni mu nezávisle na ostatních seznamy vrátí s doplněným i-tým číslem a pokud se některý s  věznitelovým shoduje, vězni vítězí. Otázkou je, jakou strategii si mají vězni předem domluvit, aby zvítězili.)

Na daném fóru je spousty hádanek z oblastí, kde naprosto tápu. Příkladem jsou různé hádanky o trojúhelnících s celočíselnými stranami, které vedly k rozvoji teorie eliptických křivek. Své si zde najde každý zvídavý človíček kterému anglický jazyk nebrání v chápání jednoduchého textu.

Zajímavé úlohy (zvláště pak seriály) najdete taky na hacker.org. Stále mne ještě pár úloh čeká.

Jednodušší hádanky poskytujeme středoškolským studentům ve „studentském časopise“ M&M.

Krátký článek srovnávající rychle rostoucí funkce Zaneprázdněný bobr a Ackermanova funkce nechávám v této sekci. Stejně tak kompilát o rubikově kostce.

Zaujalo mne, že si dal někdo práci implementovat digitální hodiny ve hře Life. Nelíbilo se mi, že segmenty spínají zcela nezávisle, což brání rychlejšímu taktu hodin. Synchronizaci spínání segmentů jednotlivých číslic jsem vylepšil a hodiny jsem pustil dvakrát rychleji. Taky jsem zmenšil překladové tabulky zapínání/vypínání jednotlivých segmentů a nahradil je přepínáním. Hodiny jsem dále synchronizoval tak, aby i jednotlivé číslice překlápěly současně, a v intervalech neovlivňovaných vzdáleností v překladové tabulce. Opravil jsem taky bug vyniklý urychlením hodin, kdy přepnutí 0 na posledním místě nestíhalo správně filtrovat přepínač PM a nejvyšší hodiny. Rychlejší hodiny by vyžadovaly zmenšení displeje.

No a implementoval jsem i menší, ještě dvakrát rychlejší hodinky. Dělal jsem je zcela od začátku, nejprve jsem zúžil překladové tabulky na polovic, pak jsem využil sudosti počtu stavů každé "číslice" takže jsem redukoval šířku stavového automatu pro každou "číslici" na polovinu, což krásně zapasovalo do polovičních překladových tabulek. Zcela jsem zrušil synchronizaci přepínání stavů původního řešení. Místo toho jsem zvolil spouštění stavů opožděné o to, o kolik kratší trajektorie následuje za stavem v překladové tabulce. Proto nebylo potřeba použít individuální opožďovací bludiště jednotlivých stavů před překladovou tabulkou. To umožnilo synchronizovat přepínání číslic v polovičním čase. Později se ukázalo, že stavy pro nejrychlejší číslici se v dané frekvenci nestihnou resetovat a každé páté přepnutí číslice jeden takt vynechávalo. Nezbylo než rozdvojit stavový automat. Kompaktní část se stará o počítání do 5 a zajišťuje reset automatu. Velká část po resetu postupně vysílá 5(×2) signálů do překladové tabulky. Pak už šlo jen o to, vytvořit zobrazovací část. Rozhodl jsem se vynechat pauzu mezi přepínáním, a radši vytvořit největší segmenty, které se v daném čase ještě stihnou přepnout. Cílem bylo vytvořit plně synchronizované segmenty. Vzhledem k tomu, že signály po pravé straně běží v jiné fázi než po levé, není možné řetězy gliderů udržet ve stejné fázi a ve stejné vzdálenosti. Přesto se podařilo odchýlit od symetrie o jediný pixel. Co se týče přepínání segmentů, zvolil jsem nejrychlejší možnou trajektorii k dolnímu segmentu. Ostatní trajektorie jsem prodloužil tak, aby přepínání segmentů bylo synchronizováno v rámci každé "číslice". Tytéž trajektorie byly použity pro všechny "číslice". (Přepínání mezi trajektorií C/2 glideru a C/4 glideru umožnily poměrně pohodlné ladění). Po synchronizaci segmentů číslic v rámci "číslic" bylo potřeba ještě sesynchronizovat číslice navzájem. Vyšší řády musí být opožděny ve stavovém automatu, nezbývá proto pro nižší řády počkat před překladovými tabulkami. Rezignoval jsem na nekřížení "drátů" v rámci zpožďovacího bludiště (dostatečné zpoždění v úzkých koridorech by vyžadovalo extrémně dlouhou dráhu). Alternativou by mohlo být přenášet signál část úseku C/2 glidery. Pak by šlo synchronizovat volbou délky urychlení. Poslední změnou byla implementace AM ukazatele, kde jsem využil přepínače generátoru C/2 gliderů objeveného během zužování překladových tabulek.
Tak jsem přeci jen nahradil brzdící labyrinty urychlením pomocí C/2 gliderů. Určitě by ještě bylo možno místo „kolizních reflektorů“ použít jiné reflektory s periodou dělící 60. Bylo by to čistší (méně živých buněk).
Na přehrávání je určitě dobré stáhnout si Golly. Jako chabou náhražku je možno použít online Javascript Conway’s Life Simulator.


Arimaa Challenge

Díky diplomce Tomáše Kozelka jsem zabředl do hry Arimaa. Hra je rozměrově podobná šachům, ale co se týče velikosti stromu hry, převyšuje go. Hra byla navržena tak, aby byla lehká pro lidi a odolávala hrubé síle počítačů. Následuje text, který postupně zastaral, snažil jsem se připisovat dospod aby byl vidět historický vývoj.


Zatím nejlepší lidé odolávají, zkusil jsem zjistit, jak na tom nejlepší lidé jsou a jak jsou na tom boti. Myslím že už mám dobrou představu o nedostatcích obou stran a věřím tomu, že vím, jak se získání Arimaa Challenge výrazně přiblížit. Více na Arimaa gameroom, MS 2010 a MS 2011. Obávám se, že nejsem sám, kdo tuší jak se k zdolání Arimaa Challenge přiblížit. Letošní (2011) vítěz WCC bot_sharp naprogramovaný Davidem Wu (lightvector) používá řazení tahů na základě vektoru popisujícího „smysl tahu“ natrénováno na základě vektorů z her výše hodnocených lidských hráčů. Toto řazení je navíc použito k omezení hloubky prohledávání neperspektivních větví. Zdá se, že po drobném doladění parametrů statické ohodnocovací funkce budou obdobní boti v roce 2012 lidmi neporazitelní. (Stále ještě věřím tomu, že letos challenge odolá, ale nebyl bych překvapen, kdyby jeden nebo dva ze zápasů skončily vítězstvím stroje. A to byli letos zvoleni obránci z top 10 aktivních hráčů.) Challenge v roce 2012 odolala, navíc se objevili další dobří lidští hráči, zatímco na straně strojů k výraznému zlepšení nedošlo. Byl jsem ukecán zúčastnit se mistrovství s 40 účastníky MS 2013. Po krachu internetového spojení pro mne WC2013 skončilo předčasně a tak jsem si to zopakoval MS 2014. Můj bot má zatím spoustu potenciálu na zlepšování (pomalé jádro, možnosti vylepšení prohledávání, slabá ohodnocovací funkce, nevyužití paralelizace), v korespondenčních partiích má v „rozevlátých“ partiích šanci díky množství času, který je ochoten partiím věnovat. Bot mého diplomanta je nesrovnatelně lepší, ukecal jsem jej pro účast na wcc.

V noci ze dne 18.4.2015 na 19.4.2015 Arimma Challenge padla. Bot Sharp od Davida Wu (lightvector) získal vedení 2:0, 2:0, 2:0 v challenge hrách proti 5 násobnému mistru světa, zároveň třetímu z letošního mistrovství, čtvrtému muži z letošního mistrovství a letošnímu mistru světa. Druhý člověk z letošního mistrovství světa (dvojnásobný mistr světa) v „screeningu“ dokázal s botem remizovat 1:1, což se povedlo ještě jednomu hráči. Nakonec challenge zápasy skončily 3:0, 2:1, 2:1. Pětinásobný mistr světa ukázal, že bot nadhodnotil frame koně a za jeho udržení byl ochoten obětovat postupně spoustu materiálu. Aktuální mistr světa pak porazil bota bez zneužití této slabiny. Získal sdílenou kontrolu nad botovou pastí což vedlo k přetížení botova slona a k vynucení výměny koně a psa za dva králíky (v tahu 27). Později bot ztratil i psa, ale materiální ztrátu dokázal po drobné nepřesnosti kompenzovat silným gólovým útokem. Aktuální mistr světa ale nezpanikařil, obětoval kočku a se stále ještě výrazným materiálním vedením získal zpět kontrolu nad gólovými hrozbami a v tahu 72 dovedl hru do vítězního konce.

David odvedl letos na vylepšení Sharpa skutečně velký kus práce. Trochu povídání o Arimaa.