Vyhledávací problémy a hledání kolizí pro hašovací funkce
| Název práce v češtině: | Vyhledávací problémy a hledání kolizí pro hašovací funkce |
|---|---|
| Název v anglickém jazyce: | Search problems and search for collisions in hash functions |
| Klíčová slova: | NP vyhľadávanie, redukcie, pigeonhole principle, orákula |
| Klíčová slova anglicky: | NP search, reductions, pigeonhole principle, oracles |
| Akademický rok vypsání: | 2008/2009 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra algebry (32-KA) |
| Vedoucí / školitel: | prof. RNDr. Jan Krajíček, DrSc. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 27.11.2008 |
| Datum zadání: | 27.11.2008 |
| Datum a čas obhajoby: | 28.01.2011 09:00 |
| Datum odevzdání elektronické podoby: | 12.12.2010 |
| Datum odevzdání tištěné podoby: | 10.12.2010 |
| Datum proběhlé obhajoby: | 28.01.2011 |
| Oponenti: | prof. RNDr. Pavel Pudlák, DrSc. |
| Zásady pro vypracování |
| Najít příklady kombinatorických vyhledávacích problémů na něž lze redukovat vyhledávání kolizí hašovacích funkcí. |
| Seznam odborné literatury |
| J.Krajíček, Structured pigeonhole principle, search problems and hard tautologies, J.Symbolic Logic, 70(2), 2005, str.619-630. |
| Předběžná náplň práce |
| Je známo, že hledání kolize u hašovací funkce lze zredukovat
na hledání homogenního podgrafu dané velikosti ve větším grafu. Cílem práce je najít další kombinatorické vyhledávací problémy s touto vlastností. |
| Předběžná náplň práce v anglickém jazyce |
| It is known that a search for a collision in a hash function can
be reduced to finding a large enough homogeneous subgraph of a larger graph. The goal of the project is to find another combinatorial search problems with this property. |