Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

В обчислювальній теорії груп група чорної скриньки група чорного ящика це група G елементи якої закодовано бітовими рядк

Група чорної скриньки

Група чорної скриньки

В обчислювальній теорії груп група чорної скриньки (група чорного ящика) — це група G, елементи якої закодовано бітовими рядками довжини N, а групові операції виконує оракул («чорна скринька»). Ці операції включають:

  • обчислення добутку g·h елементів g і h,
  • обчислення оберненого значення g−1 елемента g,
  • з'ясування, чи g = 1.

Цей клас визначено так, що він включає як групи перестановок, так і групи матриць. Верхня межа порядку G задана, як |G| ≤ 2N показує, що G — скінченна.

Застосування

Групи чорної скриньки представили 1984 року Бабай і Семереді. Їх використовували як формалізм для (конструктивного) розпізнавання груп і [en]. Відомі алгоритми включають алгоритм Бабая для пошуку елементів випадкової групи, алгоритм заміни добутку та .

Багато ранніх алгоритмів у обчислювальній теорії груп, наприклад [en], вимагають представлення групи перестановкою і, отже, не є чорною скринькою. Багато інших алгоритмів потребують пошуку порядків елементів. Оскільки існують ефективні способи знайти порядок елемента в групі перестановок або в матричній групі (метод для останньої описали 1997 року Селлер і [en]), загальним виходом є припущення, що група чорної скриньки оснащена додатковим оракулом для визначення порядку елементів.

Див. також

  • [en]

Примітки

  1. Babai, L.; Szemeredi, E. (1984). On the Complexity of Matrix Group Problems I. 25th Annual Symposium on Foundations of Computer Science, 1984. с. 229—240. doi:10.1109/SFCS.1984.715919. ISBN .
  2. L. Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proc. 23rd STOC (1991), 164—174.
  3. Frank Celler; Charles R. Leedham-Green; Scott H. Murray; Alice C. Niemeyer; E.A. O'Brien (1995). Generating random elements of a finite group. Communications in Algebra. 23 (3): 4931—4948. CiteSeerX 10.1.1.43.2250. doi:10.1080/00927879508825509.
  4. Pak, Igor (2012). Testing commutativity of a group and the power of randomization. LMS Journal of Computation and Mathematics. 15: 38—43. doi:10.1112/S1461157012000046.
  5. See Holt et al. (2005).

Література

  • Derek F. Holt, Bettina Eick, Eamonn A. O'Brien, Handbook of computational group theory, Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, Florida, 2005.
  • Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003.
  • ; Seress, Ákos (2001). Black Box Classical Groups. Memoirs of the American Mathematical Society. Т. 708. American Mathematical Society. ISBN . ISSN 0065-9266.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

V obchislyuvalnij teoriyi grup grupa chornoyi skrinki grupa chornogo yashika ce grupa G elementi yakoyi zakodovano bitovimi ryadkami dovzhini N a grupovi operaciyi vikonuye orakul chorna skrinka Ci operaciyi vklyuchayut obchislennya dobutku g h elementiv g i h obchislennya obernenogo znachennya g 1 elementa g z yasuvannya chi g 1 Cej klas viznacheno tak sho vin vklyuchaye yak grupi perestanovok tak i grupi matric Verhnya mezha poryadku G zadana yak G 2N pokazuye sho G skinchenna ZastosuvannyaGrupi chornoyi skrinki predstavili 1984 roku Babaj i Semeredi Yih vikoristovuvali yak formalizm dlya konstruktivnogo rozpiznavannya grup i en Vidomi algoritmi vklyuchayut algoritm Babaya dlya poshuku elementiv vipadkovoyi grupi algoritm zamini dobutku ta Bagato rannih algoritmiv u obchislyuvalnij teoriyi grup napriklad en vimagayut predstavlennya grupi perestanovkoyu i otzhe ne ye chornoyu skrinkoyu Bagato inshih algoritmiv potrebuyut poshuku poryadkiv elementiv Oskilki isnuyut efektivni sposobi znajti poryadok elementa v grupi perestanovok abo v matrichnij grupi metod dlya ostannoyi opisali 1997 roku Seller i en zagalnim vihodom ye pripushennya sho grupa chornoyi skrinki osnashena dodatkovim orakulom dlya viznachennya poryadku elementiv Div takozh en PrimitkiBabai L Szemeredi E 1984 On the Complexity of Matrix Group Problems I 25th Annual Symposium on Foundations of Computer Science 1984 s 229 240 doi 10 1109 SFCS 1984 715919 ISBN 0 8186 0591 X L Babai Local expansion of vertex transitive graphs and random generation in finite groups Proc 23rd STOC 1991 164 174 Frank Celler Charles R Leedham Green Scott H Murray Alice C Niemeyer E A O Brien 1995 Generating random elements of a finite group Communications in Algebra 23 3 4931 4948 CiteSeerX 10 1 1 43 2250 doi 10 1080 00927879508825509 Pak Igor 2012 Testing commutativity of a group and the power of randomization LMS Journal of Computation and Mathematics 15 38 43 doi 10 1112 S1461157012000046 See Holt et al 2005 LiteraturaDerek F Holt Bettina Eick Eamonn A O Brien Handbook of computational group theory Discrete Mathematics and its Applications Boca Raton Chapman amp Hall CRC Boca Raton Florida 2005 ISBN 1 58488 372 3 Akos Seress Permutation group algorithms Cambridge Tracts in Mathematics vol 152 Cambridge University Press Cambridge 2003 ISBN 0 521 66103 X Seress Akos 2001 Black Box Classical Groups Memoirs of the American Mathematical Society T 708 American Mathematical Society ISBN 978 0 8218 2619 5 ISSN 0065 9266

Дата публікації:
Топ