|
|
Vyhledávací problémy a hledání kolizí pro hašovací funkce
Čarnoký, Samuel ; Krajíček, Jan (vedoucí práce) ; Pudlák, Pavel (oponent)
Název práce: Vyhledávací problémy a hledání kolizí pro hašovací funkce Autor: Samuel Čarnoký Katedra : Katedra algebry Vedoucí diplomové práce: prof. RNDr. Jan Krajíček, DrSc. e-mail vedoucího: krajicek@karlin.mff.cuni.cz Abstrakt: Centrálnymi bodmi tejto práce sú NP vyhľadávacie problémy a existencia redukcie medzi nimi v relativizovanom zmysle. Absolútna separácia by separovala P od NP. Venujeme sa špeciálne problému hľadania kolízii v hešovacích funkciách, ktorých existencia je garantovaná známym holubníkovým princípom (PHP). Podávame stručný úvod do problematiky, definujeme rôzne NP vyhľadávacie problémy a pripomíname redukcie a separácie. Referujeme o redukcii slabej verzie PHP na hľadanie homogénneho podgrafu a prinášame vlastnú redukciu varianty PHP na problematiku súvisiacu s hľadaním ciest v grafe. Pojednávame o redukovaní hladania kolízií vo viacerých funkciach na hľadanie kolízie v jednej. Klíčová slova: NP vyhľadávanie, redukcie, pigeonhole principle, orákula
|
|
|
Výroková logika a algebra
Polach, František ; Krajíček, Jan (vedoucí práce) ; Pudlák, Pavel (oponent)
Algebraic proof systems of which the most important are the polynomial calculus and the Nullstellensatz proof system are proof systems that use algebraic means for proving propositional tautologies - they are based on polynomial identities over (commutative) rings. Razborov [9] have proved a non-trivial lower bound on degree for polynomia calculus proofs of the tautologies (a set of polynomials) that express the pigeonhole principle over any field. This work gathers present important results for algebraic proof systems and generalizes the Razborov's construction used in his proof of the lower bound to another set of polynomials. We explicitly describe the basis of the vector space of polynomials that are derivable by a small degree polynomial calculus proof from the tautologies that express a variant of the pigeonhole principle (that generalizes the principle for multifunctions).
|
|
| |
|
|
Definovatelnost v matematických strukturách
Paták, Pavel ; Jeřábek, Emil (oponent) ; Krajíček, Jan (vedoucí práce)
Nazev pram: Defiuovatelnost v matrnnatickych struktnrneh Auiur: Pave! Patak Kat.odra: Katedra algebry Vedouci bakalafske prace: Prof. R.XDr. Jan Krajicek, DrSc. e-mail vedouciho: krajicek'Q'math.cas.cz AbytrakL: V pfedlo/.ene praci so zabyvame popisem definovatelnych nmozin v ruznych matematickych st.rukturaeh. Ukazujerne, zo defiuovatelne mnoziny v pfirozenych, celych a racionalnich cfslcch inohon byt volico kompliko- vann. naproti toinn dnfiiiovatolnr mnoziny ve .striiktnrach s {'liininari kvanti- fikatoru (reaina, komplexni cfsla,. - . ) JHOU jcdnoduclic. Vciinjoino se i pojinu modolovo I'iplnosti. S poinoci zfskanych poznatku a vo.ty o nplno.sti pak snadno dokazeme nektere obtizne vety jinych disciplin - alji,ebraickou Xnll- stollcnsatz a Artinovn charaktorizaci pozitivnr dofinitnicb racionalnfcli fimkoi, geometrickou Tarski-Seidenbergovn vetn a ninohc dalyi. Klicova slova: nmtematicke sl.rnktnry, dcliiiuvatelnost, eliminace kvantilika- toru Title: DcfinnViility in inatlioinatica.l structures Author: Pavel Patak Department: Department of Algebra Supervisor: Prof. RNDr. Jan Krajirek, DrSc. Supervisor's e-mail address: kra.jicokv'iJina.lb.cas.cz Abstract: In t,be present work we study the description of definable sets in various mathematical structures. We show that, the definable sets in natural, integer...
|
|
|
Profesní orientace studentů závěrečných ročníků UK FTVS
Krajíček, Jan ; Tilinger, Pavel (vedoucí práce) ; Kocourek, Jan (oponent)
Název magisterské práce: Profesní orientace studentů závěrečných ročníků UK FTVS. Professional orientation of students in the last term at the Faculty of physical education and sport, Charles university. Cíle práce: Cílem práce bylo prostřednictvím dotazování získat objektivní aktuální názory studentů posledních ročníků UK FTVS na záležitosti spojené s pracovní aktivitou po skončení studia. Studenti byli osloveni v době, kdy jim do skončení studia zbývalo půl roku. Metoda práce: Pomocí dotazníků jsme zjistili současné tendence profesní orientace studentů posledních ročníků UK FTVS. Výsledky práce: Práce zjistila názory studentů posledních ročníků UK FTVS na záležitosti spojené s pracovní aktivitou po skončení studia. Většina studentů podle očekávání preferuje práci trenéra (54%) a učitele na střední škole (59%), ale doposud ještě váhají a nemají jisté zaměstnání (42%). Stále větší část studentů se chystá dále studovat a cestovat (shodně 17%). Studenti řadí mezi hlavní zásady výběru zaměstnání osobní uspokojení z práce (95%) a fmanční atraktivitu (96%). Studenti zpravidla hodnotí vzdělání získané na UK FTVS za převážně dostačující (40%) nebo dostačující (42%), vyžadující pouze drobné úpravy (69%). Studenti jednoznačně očekávají budoucí doplnění vzdělání (96%). Klíčová slova - profese tělovýchovného...
|
|
|
Silné důkazové systémy
Mikle-Barát, Ondrej ; Krajíček, Jan (vedoucí práce) ; Pudlák, Pavel (oponent)
R-OBDD je nový Cook-Reckhowův důkazový systém pro výrokovou logiku založen na kombinaci OBDD důkazového systému a rezolučního důkazového systému. R-OBDD má sílu OBDD důkazového systému - tautologie s exponenciálně velkými důkazy v rezoluci jako PHPn nebo Tseitinovy kontradikce mají v R-OBDD systému polynomiální důkazy (R-OBDD p-simuluje jak OBDD důkazový systém, tak rezoluci). Na druhé straně, odvozovací pravidla R-OBDD systému byly navrhnuty, aby se podobaly odvozovacím pravidlům rezoluce. Tím pádem je možné vytvořit modifikaci DPLL algoritmu, která bude pracovat v R-OBDD systému a zároveň použít některé heuristiky známé z algoritmů založených na DPLL. Vzniká možnost vytvořit efektivnejší algoritmus na řešení problému splnitelnosti formule (SAT). Ukážeme návrh algoritmu, který je adaptací DPLL algoritmu pro R-OBDD důkazový systém. Přikldáme důkaz z jeho korektnosti a ukážeme, že jeho běh nad nesplnitelnou formulí je možné transformovat do stromového důkazu v R-OBDD systému.
|
|
| |
|
|
Analýza pigmentů z integumentu Graphosoma semipunctatum.
Krajíček, Jan ; Svobodová, Eva (oponent) ; Bosáková, Zuzana (vedoucí práce)
Pteriny patří do důležité skupiny látek, fungující jako pigmenty u řady druhů živočichů. Některé z nich jsou pravděpodobně zodpovědné za charakteristické zbarvení skupiny hmyzu. Toto zbarvení funguje jako varovný signál pro vizuálně se orientující predátory (ptáky, ještěrky aj.). Tato práce byla zaměřena na vývoj HPLC separační metody pro analýzu pterinů, obsažených v Graphosoma semipunctatum. Pro vývoj metody byl zvolen reverzní separační mód s C18 stacionární fází (Spherisorb ODS 2) a binární mobilní fází (organický modifikátor/fosfátový pufr nebo voda). V rámci optimalizační procedury byl sledován vliv typu a obsahu organického modifikátoru (methanol, ethanol, tetrahydrofuran) a koncentrace fosfátového pufru, pH 3,0 (10 - 30 mM) v mobilní fázi na retenční a separační chování studovaných pterinů (leukopterin, biopterin, xanthopterin, isoxanthopterin a erythropterin). Za optimalizovaných separačních podmínek (5/95 (v/v) methanol/20 mM fosfátový pufr, pH 3,0, průtoková rychlost 0,7 ml.min-1 , UV detekce při 290 nm) byl analyzován extrakt z integumentu ploštice Graphosoma semipunctatum.
|
|
| |
|
| |
host ::
RSS.