Metoda čtyř Rusů - Method of Four Russians - Wikipedia

v počítačová věda, Metoda čtyř Rusů je technika pro zrychlení algoritmy zahrnující Booleovské matice nebo obecněji algoritmy zahrnující matice, ve kterých může každá buňka nabývat pouze omezeného počtu možných hodnot.

Idea

Hlavní myšlenkou metody je rozdělení matice na malé čtvercové bloky velikosti t × t pro nějaký parametr t, a použít a vyhledávací tabulka provést algoritmus rychle v každém bloku. Index do vyhledávací tabulky kóduje hodnoty buněk matice v levé horní části hranice bloku před nějakou operací algoritmu a výsledek vyhledávací tabulky kóduje hodnoty hraničních buněk v pravé dolní části bloku po operaci. Celkový algoritmus lze tedy provádět pouze při provozu na (n/t)2 bloky místo zapnuto n2 maticové buňky, kde n je délka strany matice. Aby byla velikost vyhledávacích tabulek (a čas potřebný k jejich inicializaci) dostatečně malá, t se obvykle volí Ó(log n).

Aplikace

Algoritmy, na které lze použít metodu čtyř Rusů, zahrnují:

V každém z těchto případů zrychlí algoritmus o jeden nebo dva logaritmický faktory.

Algoritmus inverze matice Metody čtyř Rusů publikovaný Bardem je implementován v knihovně M4RI pro rychlou aritmetiku s hustými maticemi nad F2. M4RI používá SageMath a knihovna PolyBoRi.[1]

Dějiny

Algoritmus zavedl V. L. Arlazarov, E. A. Dinic, M. A. Kronrod a I. A. Faradžev v roce 1970.[2] Původ jména není znám; Aho, Hopcroft a Ullman (1974) vysvětlit:

Druhá metoda, často nazývaná algoritmem „Čtyři Rusové“, je po mohutnosti a národnosti jejích vynálezců poněkud „praktičtější“ než algoritmus v teorému 6.9.[3]

Všichni čtyři autoři pracovali Moskva, Rusko v době, kdy.[4]

Poznámky

  1. ^ M4RI - hlavní stránka
  2. ^ Arlazarov a kol. 1970.
  3. ^ Aho, Hopcraft a Ullman 1974, str. 243.
  4. ^ Autorská sdružení na MathNet.ru.

Reference

  • Arlazarov, V.; Dinic, E .; Kronrod, M .; Faradžev, I. (1970), „O ekonomické konstrukci přechodného uzavření směrovaného grafu“, Dokl. Akad. Nauk SSSR, 194 (11). Originální název: "Об экономном построении транзитивного замыкания ориентированного графа", publikováno v Доклады Академии Наук СССР 134 (3), 1970.
  • Aho, Alfred V .; Hopcroft, John E .; Ullman, Jeffrey D. (1974), Návrh a analýza počítačových algoritmů, Addison-Wesley
  • Bard, Gregory V. (2009), Algebraická kryptoanalýzaSpringer, ISBN  978-0-387-88756-2