To'rt rusning usuli - Method of Four Russians - Wikipedia
Yilda Kompyuter fanlari, To'rt rusning usuli tezlashtirish texnikasi algoritmlar jalb qilish Mantiqiy matritsalar yoki umuman olganda matritsalarni o'z ichiga olgan algoritmlar, unda har bir katak faqat mumkin bo'lgan qiymatlarning chegaralangan sonini qabul qilishi mumkin.
Fikr
Usulning asosiy g'oyasi matritsani kattalikdagi kichik kvadrat bloklarga bo'lishdir t × t ba'zi parametrlar uchun tva foydalanish uchun a qidiruv jadvali algoritmni har bir blok ichida tezda bajarish. Izlash jadvalidagi indeks algoritmning biron bir ishidan oldin blok chegarasining yuqori chap qismidagi matritsa katakchalarining qiymatlarini kodlash va qidiruv jadvalining natijasi blokning pastki o'ng qismidagi chegara kataklari qiymatlarini kodlash. operatsiyadan keyin. Shunday qilib, umumiy algoritm faqat ustida ishlash orqali amalga oshirilishi mumkin (n/t)2 o'rniga bloklar n2 matritsa hujayralari, qaerda n matritsaning yon uzunligi. Qidiruv jadvallarining hajmini (va ularni ishga tushirish uchun zarur bo'lgan vaqtni) etarlicha oz ushlab turish uchun, t odatda tanlanadi O(log n).
Ilovalar
To'rt rus usuli qo'llanilishi mumkin bo'lgan algoritmlarga quyidagilar kiradi:
- hisoblash o'tish davri yopilishi grafik,
- Mantiqiy matritsani ko'paytirish,
- masofani tahrirlash hisoblash,
- ketma-ketlikni tekislash,
- uchun indekslarni hisoblash ikkilik jumbled naqshni moslashtirish.
Ushbu holatlarning har birida algoritmni bir yoki ikkitaga tezlashtiradi logaritmik omillar.
Bard tomonidan nashr etilgan "To'rt rus matritsasi inversiya algoritmi" usuli M4RI kutubxonasida zich matritsali tezkor arifmetik uchun joriy qilingan. F2. M4RI tomonidan ishlatiladi SageMath va PolyBoRi kutubxonasi.[1]
Tarix
Algoritm tomonidan kiritilgan V. L. Arlazarov, E. A. Dinic, M. A. Kronrod va 1970 yilda I. A. Faradžev.[2] Ismning kelib chiqishi noma'lum; Aho, Hopkroft va Ullman (1974) tushuntiring:
- Ko'pincha "to'rtta rus" algoritmi deb nomlangan ikkinchi usul, ixtirochilarining kardinalligi va millatidan keyin, 6.9-teoremadagi algoritmga qaraganda bir oz ko'proq "amaliyroq".[3]
To'rt muallif ham ishlagan Moskva, Rossiya vaqtida.[4]
Izohlar
- ^ M4RI - Asosiy sahifa
- ^ Arlazarov va boshq. 1970 yil.
- ^ Aho, Hopcraft & Ullman 1974 yil, p. 243.
- ^ Mualliflik aloqalari MathNet.ru saytida.
Adabiyotlar
- Arlazarov, V.; Dinik, E .; Kronrod, M.; Faradžev, I. (1970), "Yo'naltirilgan grafaning o'tish davri yopilishining iqtisodiy qurilishi to'g'risida", Dokl. Akad. Nauk SSSR, 194 (11). Asl sarlavha: "Ob ekonomnom postroenii tranzitivnogo zamykaniya orientirovannogo grafik", nashr etilgan Doklady Akademii Nauk SSSR 134 (3), 1970.
- Aho, Alfred V.; Xopkroft, Jon E. Ullman, Jeffri D. (1974), Kompyuter algoritmlarini tuzish va tahlil qilish, Addison-Uesli
- Bard, Gregori V. (2009), Algebraik kriptanaliz, Springer, ISBN 978-0-387-88756-2
 | Bu amaliy matematika bilan bog'liq maqola a naycha. Siz Vikipediyaga yordam berishingiz mumkin uni kengaytirish. |