Русские вычислители

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » Русские вычислители » Вычислители по-русски » Метод четырёх русских


Метод четырёх русских

Сообщений 1 страница 2 из 2

1

https://en.wikipedia.org/wiki/Method_of_Four_Russians

The algorithm was introduced by V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, and I. A. Faradzev in 1970.
uses precomputed lookup tables to speed up transitive closure
goes from O(n^3) to O(n^3/log n)
so for a grammar of say 1000 symbols, it would reduce a transitive closure time by one order of magnitude
also video of a UCDavis professor explaining it https://youtu.be/cYJrMUvJQGc (sub-cubic method for bit-matrix multiplication)

А встречается transitive closure в парсере Marpa (дефалтовом парсере языка perl):
https://irclog.perlgeek.de/marpa/2015-11-18

Отредактировано ВежливыйЛис (10.09.2016 10:32:43)

0

2

Наверно все же четырех советских - потому что Кронрод, Фараджев и арлазаров явно не русские фамилии. Извиняюсь, конечно, за банальность, но СССР был многонациональным государством.

0


Вы здесь » Русские вычислители » Вычислители по-русски » Метод четырёх русских


форум на 24bb Создать форум бесплатно