Модели восстановления дискретных функций

Аннотация

Рассматриваются задачи дискретной математики, связанные с восстановлением дискретных функций и возникающие в теории тестирования и теории вычислительного обучения. Пусть, к примеру, загадана некоторая (неизвестная) функция из заранее известного класса K и требуется при помощи вопросов (запросов к оракулам) точно определить, какая именно функция из K загадана. Для ряда постановок сопоставляются возможности запросов различных типов: запросов значения в точке, запросов эквивалентности, запросов о свойствах подфункций (запросов к подкубам). Обсуждается классическая задача расшифровки монотонной булевой функции, задачи точной идентификации функций, бесповторных в различных базисах.

Литература

1. Angluin D. Queries and concept learning // Machine Learning. 1987. Vol. 2. P. 319–342.
2. Angluin D., Hellerstein L., Karpinski M. Learning read-once formulas with queries // Journal of the ACM. 1993. Vol. 40. P. 185–210.
3. Hansel G. Sur le nombre des fonctions bool´ennes monotones de n variables // C. R. Acad. Sci. Paris. 1966. Vol. 262. P. 1088–1090. (Ансель Ж. числе монотонных булевых функций n переменных // Кибернетический сборник, изд-во Мир. Новая серия. Вып. 5. 1968. С. 53–57.)
4. Golumbic M. C., Mintz A., Rotics U. Factoring and recognition of read-once functions using cographs and normality and the readability of unctions associated with partial k-trees // Discrete Applied Mathematics. 2006. Vol. 154, № 10. P. 1465–1477.
5. Вороненко А. А. О задачах глобального тестирования (расшифровки) бесповторных булевых функций // Синтаксис и семантика логических систем: материалы 3-й Российской школы-семинара. Иркутск: Изд-во Восточно-Сибирской государственной академии образования, 2010. С. 17–22.
6. Вороненко А. А. Тестирование и распознавание свойств дискретных функций. М.: МАКС Пресс, 2010. 80 с.
7. Вороненко А. А., Чистиков Д. В. Расшифровка бесповторных функций оракулом — счетчиком четности // Прикладная математика и информатика. Вып. 34. М.: МАКС Пресс, 2010. С. 93–106. (Voronenko A. A., Chistikov D. V. Learning read-once functions using subcube parity queries // Computational Mathematics and Modeling. 2011. Vol. 22, № 1. P. 81–91.)
8. Коробков В. К. О монотонных функциях алгебры логики // Проблемы кибернетики. Вып. 13. М.: Наука, 1965. С. 5–28.
9. Коробков В. К. Оценка числа монотонных булевых функций алгебры логики и сложности алгоритма отыскания разрешающего множества для произвольной монотонной функции алгебры логики // Докл. АН СССР. 1963. Т. 150, № 4. С. 744–747.
10. Чистиков Д. В. О связи задач диагностического и проверяющего тестирования бесповторных функций // Дискретная математика. 2011. Т. 23, № 1. С. 46–50.