Организация, в которой проходила защита:
Филиал МГУ им. М.В.Ломоносова в г. Душанбе
Год защиты:2019
Аннотация:Работа относится к области моделирования элементов искусственного интеллекта. Первые программы подобного типа реализовывали одну из популярных игр – шахматы, Реверси, Го и т. п. В этих играх компьютерные программы соревнуются с человеком и зачастую переигрывают его. В работе реализована программа для игры «Получить сотню из автобусного билета». Номер автобусного билета содержит 6 цифр, нужно путем расстановки знаков арифметических операций и скобок между некоторыми цифрами билета получить формулу, значением которой является число 100. Например, из номера 123456 сотню можно получить так: (1+2/3)*(4+56)=100. В свое время подобное развлечение было очень популярно и представляло собой хорошее упражнение на сообразительность и умение быстро считать; купив в автобусе билет, люди тотчас же пытались получить из него сотню и соревновались, кто быстрее это сделает. Тогда же было высказано предположение, что из любого номера, содержащего 6 разных цифр и начинающегося не с нуля, можно получить сотню.
В работе реализована программа на С++, которая решает эту задачу, причем намного быстрее и эффективнее, чем человек. Также требовалось доказать или опровергнуть высказанную гипотезу. В принципе такую программу можно было бы реализовать путем полного перебора всех деревьев с 6 терминальными вершинами, соответствующих всем арифметическим выражениям. Однако перебор очень большой, он усложняется тем, что помимо четырех арифметических операций есть операция унарного минуса, а также операция приписывания цифры справа к числу.
В работе такая программа реализована не путем полного перебора всех деревьев, а с помощью более интеллектуального представления формулы в виде комбинации подформул с использованием идей динамического программирования.
Высказанная выше гипотеза опровергнута – программа нашла много номеров, состоящих из шести различных цифр и начинающихся не с нуля, из которых сотню получить не удается. Например, из номеров 103459, 207459, 302456 и др. сотню получить невозможно.