Модели восстановления дискретных функций — различия между версиями
Материал из Кафедра математической кибернетики
Root (обсуждение | вклад) (Новая страница: «Спецкурс читается в весеннем семестре. Нагрузка - 32 часа. Лекторы: проф. Вороненко Андре…») |
Root (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
| − | |||
| − | |||
== Аннотация == | == Аннотация == | ||
Рассматриваются задачи дискретной математики, связанные с восстановлением дискретных функций и возникающие в теории тестирования и теории вычислительного обучения. Пусть, к примеру, загадана некоторая (неизвестная) функция из заранее известного класса K и требуется при помощи вопросов (запросов к оракулам) точно определить, какая именно функция из K загадана. Для ряда постановок сопоставляются возможности запросов различных типов: запросов значения в точке, запросов эквивалентности, запросов о свойствах подфункций (запросов к подкубам). Обсуждается классическая задача расшифровки монотонной булевой функции, задачи точной идентификации функций, бесповторных в различных базисах. | Рассматриваются задачи дискретной математики, связанные с восстановлением дискретных функций и возникающие в теории тестирования и теории вычислительного обучения. Пусть, к примеру, загадана некоторая (неизвестная) функция из заранее известного класса K и требуется при помощи вопросов (запросов к оракулам) точно определить, какая именно функция из K загадана. Для ряда постановок сопоставляются возможности запросов различных типов: запросов значения в точке, запросов эквивалентности, запросов о свойствах подфункций (запросов к подкубам). Обсуждается классическая задача расшифровки монотонной булевой функции, задачи точной идентификации функций, бесповторных в различных базисах. | ||
| Строка 17: | Строка 14: | ||
# Чистиков Д. В. О связи задач диагностического и проверяющего тестирования бесповторных функций // Дискретная математика. 2011. Т. 23, № 1. С. 46–50. | # Чистиков Д. В. О связи задач диагностического и проверяющего тестирования бесповторных функций // Дискретная математика. 2011. Т. 23, № 1. С. 46–50. | ||
| − | [[Категория: | + | [[Категория:Архив спецкурсов]] |
Текущая версия на 20:09, 7 января 2018
Аннотация
Рассматриваются задачи дискретной математики, связанные с восстановлением дискретных функций и возникающие в теории тестирования и теории вычислительного обучения. Пусть, к примеру, загадана некоторая (неизвестная) функция из заранее известного класса K и требуется при помощи вопросов (запросов к оракулам) точно определить, какая именно функция из K загадана. Для ряда постановок сопоставляются возможности запросов различных типов: запросов значения в точке, запросов эквивалентности, запросов о свойствах подфункций (запросов к подкубам). Обсуждается классическая задача расшифровки монотонной булевой функции, задачи точной идентификации функций, бесповторных в различных базисах.
Литература
- Angluin D. Queries and concept learning // Machine Learning. 1987. Vol. 2. P. 319–342.
- Angluin D., Hellerstein L., Karpinski M. Learning read-once formulas with queries // Journal of the ACM. 1993. Vol. 40. P. 185–210.
- 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.)
- 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.
- Вороненко А. А. О задачах глобального тестирования (расшифровки) бесповторных булевых функций // Синтаксис и семантика логических систем: материалы 3-й Российской школы-семинара. Иркутск: Изд-во Восточно-Сибирской государственной академии образования, 2010. С. 17–22.
- Вороненко А. А. Тестирование и распознавание свойств дискретных функций. М.: МАКС Пресс, 2010. 80 с.
- Вороненко А. А., Чистиков Д. В. Расшифровка бесповторных функций оракулом — счетчиком четности // Прикладная математика и информатика. Вып. 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.)
- Коробков В. К. О монотонных функциях алгебры логики // Проблемы кибернетики. Вып. 13. М.: Наука, 1965. С. 5–28.
- Коробков В. К. Оценка числа монотонных булевых функций алгебры логики и сложности алгоритма отыскания разрешающего множества для произвольной монотонной функции алгебры логики // Докл. АН СССР. 1963. Т. 150, № 4. С. 744–747.
- Чистиков Д. В. О связи задач диагностического и проверяющего тестирования бесповторных функций // Дискретная математика. 2011. Т. 23, № 1. С. 46–50.
