Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 [4] 5   вперед  Ctrl      все
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
Aleksandr Sharahov
м,
т.к. не соблюдены *все* необходимые требования.

1) и какие же требования не соблюдены?
а) строка есть
б) правила есть
в) все шаги алгоритма выполнены
г) конечный ответ получен
2) сложение в столбик может быть приведено к Марковскому алгоритму, нужно лишь записать строку нужным нам образом
30 май 20, 20:47    [22142853]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
Aleksandr Sharahov,
я знаю, что решетки # это чит, но идея состоит в том, чтобы воспроизвести сложение в столбик
:-)

PS
а если число преобразовывать, и решетки убирать, то остаются 2 правила (как в твоем решении)
12->20
02->10


111111 + 111
0111222

12->20: 0112022
02->10: 0112102
02->10: 0112110
12->20: 0120110
12->20: 0200110
02->10: 1000110

Res: 1000110
30 май 20, 21:40    [22142877]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab
Aleksandr Sharahov,
я знаю, что решетки # это чит, но идея состоит в том, чтобы воспроизвести сложение в столбик
:-)

PS
а если число преобразовывать, и решетки убирать, то остаются 2 правила (как в твоем решении)
12->20
02->10


111111 + 111
0111222

12->20: 0112022
02->10: 0112102
02->10: 0112110
12->20: 0120110
12->20: 0200110
02->10: 1000110


Res: 1000110


Не в решетках дело. Можно использовать хоть решетки, хоть собачки, хоть смайлики.
Но тогда надо указать замены, которые привели исходное выражение к выражению с решетками,
а также замены, которые приводят результат с решетками к результату без решеток.

Причем записать все эти правила надо в определенном порядке,
который требуется незатейливому алгоритму Маркова.

Речь о том, что этого всего не хватает.
30 май 20, 22:17    [22142888]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
Aleksandr Sharahov,

я знаю, что формально для решения задачи as is этого не хватает, но у меня были другие цели
30 май 20, 22:40    [22142893]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 202
более шустрый алгоритм сложения и умножения в столбик

1000100111111000*1000110101111101 = 4049 замен
1000110101111101*1000100111111000 = 4386 замен

+
0t10 -> 100t
0t1 -> 10t
1g00 -> 001g
0g1 -> 10g
1g1 -> 11g
E1 -> 1E
E0 -> 0E
E -> e
s0t0t -> 00
s1t0t -> 10
1t0 -> 01t
s1t1t -> 11
1t1 -> 11t
c0 -> 0c
1g0 -> 01g
0g0000 -> 00000g
0gDe -> De0
00teS -> e0eS
00te -> e0
10teS -> e1eS
10te -> e1
11te -> ~e0
0t0000 -> 00000t
0t00 -> 000t
d0 -> 0d
0t0 -> 00t
0g00 -> 000g
0g0 -> 00g
c1 -> 1c
1gDe -> De1
0p -> p00g
1p -> p11g
d1 -> 1d
1~ -> ~0
m0 -> m
01te -> e1
0~ -> 1
s~ -> s1
D -> 0
p -> 
0ce -> p0De0eS
de -> 0e
1ce -> p1De1eS
1m -> mc
0m -> md
m1 -> m
se -> 
0s -> s0t
1s -> s1t
0eS -> s0t
me -> 
s1e -> 1
1* -> mcE
0+ -> s0tE
1+ -> s1tE
0* -> mdE
s1 -> 1
1eS -> s1t
e -> 
s0 -> s

В интерпретатор добавлен оптимизатор порядка правил. Для этого в командной строке запустите с ключам /o и /s или используйте DropAtMe(Opt).bat.
В файле все образцы должны быть с верными эталонными значениями. Образцы нужно подобрать таким образом что бы использовались все правила. Оптимизатор только переставляет правила местами для того что бы уменьшить число итераций (не замен). Если перестановка увеличила число шагов или какой либо из образцов перестал быть равным эталону то она отклоняется.

К сообщению приложен файл (nam.zip - 2Kb) cкачать
31 май 20, 00:58    [22142924]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
а почему бы не сделать так:
алфавит 0,1,+
Правило:
a+b -> f(a,b)

разве это противоречило бы правилам алгоритма?
31 май 20, 03:22    [22142939]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab
а почему бы не сделать так:
алфавит 0,1,+
Правило:
a+b -> f(a,b)

разве это противоречило бы правилам алгоритма?


Это противоречит определению НАМ:

1. НАМ - это упорядоченный набор строковых замен (некоторые замены могут иметь флаг останова).

2. НАМ начинает работу с единственной входной строки, последовательно выполняя шаги.

3. На очередном шаге НАМ просматривает список замен с самого начала и выполняет первую подходящую замену.
При этом замена в текущей строке выполняется 1 раз для первого подходящего фрагмента строки.

4. НАМ останавливается, если на очередном шаге не найдена подходящая замена
или если выполненная замена имела флаг останова.

5. Результатом работы НАМ является текущая строка в момент прекращения его работы.
31 май 20, 10:28    [22142961]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab,

поэтому когда вас просят разработать НАМ для сложения чисел в двоичной записи,
это означает, что нужно просто указать список замен.
31 май 20, 10:39    [22142963]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
mini.weblab
а почему бы не сделать так:
алфавит 0,1,+
Правило:
a+b -> f(a,b)

разве это противоречило бы правилам алгоритма?

Давай мы этот вопрос адресуем новому топику который ты сама создашь.
31 май 20, 11:21    [22142967]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
Swa111,

правильно ли я понял, что последний более быстрый вариант реализации бинарного умножения
отличается от предыдущего перестановкой замен и добавлением ускорителей, например:
0g0000 -> 00000g
0g00 -> 000g
0g0 -> 00g


P.S.
НАМы и без оптимизаций довольно трудны для понимания,
а после перестановок и вовсе теряют читаемость,
поэтому, проявляя заботу о читателях,
хочется попросить наряду с оптимизированной версией
также публиковать неоптимизированную версию алгоритма.
31 май 20, 13:12    [22143037]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
mayton,
нет, спасибо, думаю, не стоит
31 май 20, 14:16    [22143082]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 202
Aleksandr Sharahov,

Да весь выигрыш как раз в ускорителях. При этом если считать именно число шагов по правилам то реальную помощь дает только
0t00 -> 000t.

Остальные хоть и уменьшают число замен, но увеличивают число итераций
31 май 20, 16:21    [22143153]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Беря во внимание сугубую ДОКАЗАТЕЛЬНУЮ теоретичность НАМ, я-бы предложил писать чисто-рафинированные
алгоритмы без оптимизаций. Оптимизации всегда можно предложить потом. Ценой какой-то потери читабельности.

Мне нравится вариант когда мы например "сложение" просто заменяем инкрементом с рекурсивным условием.
Это - в духе функциональщины.
31 май 20, 16:41    [22143163]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Следующий вопрос.

Можем-ли мы реализовать ПОЛИЗ.

Пример:

Input:
sqrt(7 * (3 + 1))


Output
7 3 1 + * sqrt



При этом понимаем что плюс и минус - бинарная функция а квадратный корень - унарная.
31 май 20, 17:00    [22143179]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Еще вопрос.

Можем-ли мы реализовать общий случай генерации перестановок (combinations) для любого числа символов?

Input:
123


Output:
123
132
213
231
312
321
31 май 20, 17:02    [22143181]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
booby
Member

Откуда:
Сообщений: 2002
mayton,

это не просто "в духе", все эти папагиглеммы и есть существо функциональщины,
доказывающее, что все, что может быть вычислено, вычислимо иммутабельным образом,
если замену видеть как атомарную операцию.
Алгорифм бежит только вперед.
А то, что обычно алгоритмом называется, представлено списком замен, которые, в обычном понимании, просто "данные".
Попом на этом сидит вся функциональщина, одновременно с декларативными прологами и последователями.
Подставив еще одну замену ты внедряешь еще одну первоклассную функцию, по сути.
Я никогда не влезал в эту тему, а на беглый взгляд вот такой вопрос заинтересовал:
В классике алгорифмы статичны в отношении списка используемых правил.
Исследовал ли кто-нибудь, и как назвал, подобные конструкции с динамически изменяемым в процессе работы алгорифма списком правил.
Есть для такого случая формализьма...
31 май 20, 17:11    [22143186]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
booby

В классике алгорифмы статичны в отношении списка используемых правил.
Исследовал ли кто-нибудь, и как назвал, подобные конструкции с динамически изменяемым в процессе работы алгорифма списком правил.
Есть для такого случая формализьма...

Я на самом деле хотел еще сильнее усугубить вопрос формализма НАМ.

Лет 15 назад мне попала в руки Книга Душкина. И она (честно говоря) надолго отбила у меня желание
изучать ФП и Хаскель в том числе. Книга - изобиловала отсылкой к математике. Ну чтобы понять сравнение
это как полезность Дональда Кнута в изучении С++. Вроде и надо. И в тоже время старина Кнут затягивает
тебя как воронка в очень занудные исследования непонятных сущностей как то машина MIX, ленточные
сортировки, и прочие абстракции которые современному разработчику вобщем не нужны. Их просто негде
применить. А если кто-то ищет другой порог вхождения то он его 100% найдет. И это будет не Кнут.

Слава богу мой хороший наставник Саша Немиш и и коммитер в Хаскель сообщество Виталий Брагилевский
немного освежили во мне желание снова посмотреть на этот язык. Я вобщем не планирую особо на нем кодить.
Нет заказов вообще. Но его изучать полезно чтобы просто понять - а зачем собсно в Scala вводили ту или иную
метафору или зачем например Java нужны streams с искусственными ограничителям.

Так вот. В главе 5.1 Основы комбинаторной логики (КЛ) Душкин приводит комбинаторы тождества (I),
канцелятор (K), коннектор (S), композитор (B), пермутатор (С) и дубликатор (W). Меня это заинтересовало.
К сожелению Душкинские примеры с неподвижной точкой и играми с базисами были для меня непонятны
с практической стороны. Я искал за что зацепиться с практики. Не смог.

И данный топик является просто пред-течей или преамбулой для другого топика который я просто обдумываю.
Обычно такой вопрос у меня вызревает долгими годами. И когда я пишу его текст - он на 80 % уже
у меня в голове готов. Я просто дополняю его линками.

Так вот. Какая связь между НАМ и КЛ. Я посчитал что если момедитировать над Марковскими правилами
то возможно я увижу какую-то мысль или связь которая меня подтолкнет к логике комбинаторов.

Сообщение было отредактировано: 31 май 20, 17:27
31 май 20, 17:28    [22143196]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
booby

Попом на этом сидит вся функциональщина, одновременно с декларативными прологами и последователями.
Подставив еще одну замену ты внедряешь еще одну первоклассную функцию, по сути.

Тема пролога мне была интересна прошлой осенью. Я хотел ее применить для поиска фактов
в дата-аналитике крупного бизнеса. Но не вышло по техническим причинам. Я не смог затащить
в проект зависимость от SWI-Prolog.

И моё достижение - это формальное доказательство на Прологе того что Иисус Христос - сын божий.
Только для этого мне пришлось записать порядка несколько сотен библейских фактов о отцовстве
и наследовании.
31 май 20, 17:34    [22143199]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mayton
Еще вопрос.

Можем-ли мы реализовать общий случай генерации перестановок (combinations) для любого числа символов?

Input:
123


Output:
123
132
213
231
312
321


результат должен быть строкой с разделителем?
31 май 20, 17:34    [22143200]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Aleksandr Sharahov

результат должен быть строкой с разделителем?

Хм... хороший вопрос.

Если у нас будет автомат-преобразователь следующей перестановки - то это будет успех.

Input:
231 

Output:
312


Или если надо будет ввести искусственно код состояния. Или код рекурсии - то давай введем.

Input:
231(0)

Output:
312(1)
31 май 20, 17:45    [22143205]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
booby

В классике алгорифмы статичны в отношении списка используемых правил.
Исследовал ли кто-нибудь, и как назвал, подобные конструкции с динамически изменяемым в процессе работы алгорифма списком правил.

У меня не возникало желания изменять правила. Но очень хотелось разбить их на непересекающиеся
модули. Причем терминалка должна была бы просто переходить в другой модуль.

Пример.

module 1 {
  rule1 -> repl1
  rule2 |-> :goto module_2
}

module 2 {
  rule1 -> repl3
  rule2 |-> :stop
}


Разумеется это не чистый НАМ. Но это моё определённое улучшение в духе Маркова.

Надеюсь госпожа mini.weblab меня здесь поймет и не будет настаивать на имеративных
языках.
31 май 20, 17:58    [22143214]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
booby
Member

Откуда:
Сообщений: 2002
mayton,

это выглядит как чистый сахар, удобство программиста, даже если
после стопа предполагается возврат.
В общем - вопрос реализации.

Изменяемый состав правил - это программа пишет сама себя по мере функционирования,
в целях всякого дип лёрнинга и построения прочих нейросетей.
То есть, кроме накопления состава фактов ( в терминах пролога) происходит докидывание/накопление,
а то и замена, правил вывода.
Вот что-то такое я думал, когда предыдущий пост писал.
31 май 20, 18:22    [22143233]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
booby
Member

Откуда:
Сообщений: 2002
booby,

мне кажется, японцы чего такого про пролог измышляли,
когда хавтались за него, как язык будущего искусственного интеллекта.
31 май 20, 18:26    [22143236]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Я тебя понял. Нет о таком я не думал. Очень напоминает eval в транслируемых языках.
И вопрос доказательства останова (к примеру) для нас становится еще более неочевидным.

Хотя я не против эксперимента если ты предложишь своё улучшение. NMA-eval.

Сообщение было отредактировано: 31 май 20, 18:24
31 май 20, 18:26    [22143237]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
booby
booby,

мне кажется, японцы чего такого про пролог измышляли,
когда хавтались за него, как язык будущего искусственного интеллекта.

У меня был еще один мотиватор. Экспертные системы в роли telegram-чят ботов.

Почему я об этом задумался. Когда я посмотрел их исходники в e-commerce.
Я пришел в ужас. Интеллектом там и не пахнет. Все на if-else. И ребята
которые пишут диалоговых ботов даже слыхом не слыхали про Prolog.

Мне это показлось как минимум - обидным. Конечно я не собирался
писать своего чят бота в телеграм. Но я хотел реализовать некое теч-демо
взяв экспертную систему из 80х (ну какую-нибудь по диагностике неполадок
например автомобиля). Взять - я имею в виду "слямзить" готовую. И просто
интегрировать ее с Телеграм-Ботом и показать.

- Ребята! Вот как надо! Вот как родные!
31 май 20, 18:32    [22143243]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 [4] 5   вперед  Ctrl      все
Все форумы / Программирование Ответить