Nechť máme problém W = (L, U, E), kde E = {g,c,a,t} je množina všech nukleotidů, U podmnožina E* je množina všech kombinací nukleotidů, L podmnožina U je množina všech DNA reprezentující druh Homo sapiens. Pak život je randomizovaný algoritmus pro problém W.
Důkaz:
1. život je korektní
pro všechna I z L: život(I) = smrt; zřejmé
2. život je randomizovaný algoritmus - konstruktivní důkaz
Mějme I z L. Pak v každém momentě T existuje j možných kroků. Algoritmus zvolí náhodně krok Tj s pravděpodobností Pj.
(To je tak, když se člověk nudí 3 hodiny v autobuse)
(To je tak, když se člověk nudí 3 hodiny v autobuse)
Žádné komentáře:
Okomentovat