О расшифровке логических функций
Диссертация
В диссертации рассматривается задача расшифровки дискретных функций из различных классов при помощи запросов на значение функции. Независимо рассматривается задача определения существенных переменных. Целью диссертации является исследование обычной и параллельной сложности расшифровки функций из различных классов и определения существенных переменных, а также построение оптимальных, оптимальных… Читать ещё >
Содержание
- 1. Общая характеристика работы
- 2. Содержание работы
- 3. Обзор известных результатов
- 1. Определение существенных переменных
- 1. 1. Алгоритмы ответов на запросы и нижние оценки
- 1. 1. 1. Оценка для класса разбивающих функций
- 1. 1. 2. Оценки для класса полных разбивающих функций
- 1. 1. 3. 2-разделяемые классы функций
- 1. 1. 4. Оценка для 2-разделяемых классов функций
- 1. 1. 5. Оценки для 2-разделяемых классов функций в параллельной среде
- 1. 1. 6. 2-разделяемость класса булевских монотонных функций
- 1. 1. 7. 2-разделяемость класса разбивающих функций
- 1. 2. Алгоритмы расшифровки переменных и верхние оценки
- 1. 2. 1. Алгоритм расшифровки переменных полных разбивающих функций
- 1. 2. 2. Алгоритм расшифровки переменных полных разбивающих функций с малым числом существенных переменных
- 1. 2. 3. Связь расшифровки переменных и расшифровки функций
- 1. 1. Алгоритмы ответов на запросы и нижние оценки
Список литературы
- Angluin, D. (1988). Queries and Concept Learning. Machine Learning, Vol. 2, pp. 319−342, 1988.
- Коробков, В.К. (1965). О монотонных функциях алгебры логики. Проблемы кибернетики, 13, 5−28, 1965.
- Gilbert, E.N. (1954). Lattice theoretic properties of frontal switching functions. J. Math. Phys., 33 (1954), 57−97.
- Кудрявцев, В.В., Алешин, C.B., Подколзин, А. С (1985). Введение в теорию автоматов. НАУКА, М., 1985.
- Damaschke, Р. (2003). On Parallel Attribute-Efficient, Learning. Journal of Computer and System Sciences, Volume 67, Issue 1, August 2003, 46−62.
- Hansel, G. (1966). Nombre minimal de contacts de fermeture necessaires pour realiser une fonction booleenne symetrique de n variables. C. R. Acad. Sci. Paris, 258 (1964), 6037−6040.
- Choi, S., Jung, K., Kirn, J. (2008). Almost Tight Upper Bound for Finding Fourier Coefficients of Bounded Pseudo-Boolean Functions. COLT 2008, 123−134.
- Torvik, V.I. (2002). Data Mining and Knowledge Discovery: a Guided Approach based on Monotone Boolean Functions. Ph.D. in Engineering Science, May 24, 2002, Louisiana State University.
- Boros, E., Hammer, P.L., Ibaraki, Т., Kawakami, К. (1997). Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle. SIAM Journal on Computing, Volume 26, Issue 1, 93−109, 1997.
- Zolotykh, N.Yu., Slievchenko, V.N. (1997). Lower Bounds for the Complexity of Learning Half-Spaces with Membership Queries. ALT'98, Otzenhausen, Germany, October 8−10, 1998.
- Kovalerchuck, В., Triantapliyllou, E., Deshpande, A. S., Vityaev, E. (1996). Interactive learning of monotone Boolean functions. Information Sciences: an International Journal, Volume 94, Issue 1−4, 87 118, 1996.
- Nakamura, A., Abe, N. (1995). Exact learning of linear combinations of monotone terms from function value queries. Theoretical Computer Science, Volume 137, Issue 1, 159−176, 1995.
- Makino, K., Ibaraki T. (1994). The maximum latency and identification of positive Boolean functions. SIAM Journal on Computing, Volume 26, Issue 5, 1363 1383, 1997.
- Гайнанов Д.Н. (1984). Об одном критерии оптимальности алгоритма расшифровки монотонных булевых функций. USSR Computational Mathematics and Mathematical Physics, Volume 24, Issue 4, 1985, Pages: 176−181.
- Соколов H.A. (1982). On the optimal evaluation of monotonic Boolean functions. USSR Computational Mathematics and Mathematical Physics, Volume 22, Issue 2, 1982, Pages 207−220.
- Bshouty, N. Hellerstein, L. (1998). Attribute efficient learning in query and mistake-bound models. Journal of Computer and System Sciences, 56: 310−319, 1998.
- Uehara, R., Tsuchida, K., Wegener. I. (1997). Optimal attribute-efficient learning of disjunction, parity, and threshold functions. Lecture Notes In Computer Science- Vol. 1208, 1997.
- Bshouty, N.H. (1997). Exact learning of formulas in parallel. Machine Learning. Volume 26. Issue I, 25−41, 1997.
- Damaschke, P. (2000). Adaptive versus nonadaptive attribute-efficient learning. Machine Learning 41 (2000), 197−215.
- Damaschke, P. (2000). Parallel Attribute-Efficient Learning of Monotone Boolean Functions. Lecture Notes in Computer Science, Algorithm Theory SWAT 2000, 473−479.
- Boros, E., Hammer P.L. (2002). Pseudo-boolean optimization. Discrete Applied Mathematics, Volume 123, Issue 1−3, 155−225, 2002.
- Foldes, S. Hammer, P.L. (2000). Monotone, Horn and Quadratic Pseudo-Boolean Functions. J. UCS, Volume 6, Number 1, 97−104, 2000.
- Littlestone. N. (1987). Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm. Machine Learning, 2(4): 285 318, 1987.
- Blum, A., Hellerstein, L., Littlestone, N. (1995). Learning in the presence of finitely or infinitely many irrelevant attributes. Journal of Computer and System Sciences, 50: 32−40, 1995.
- Valiant, L. G. (1984). A theory of the learnable. ACM Press New York, NY, USA, Volume 27, Issue II, 1134−1142.
- Blum A. (2003). Learning a Function of r Relevant Variables. COLT 2003, Open problems.
- Arpe, J. Reischuk, B. (2007). Learning Juntas in the Presence of Noise. Theoret. Comput. Sci. 384(1): 2−21, 2007.
- Kolountzakis, M., Markakis, E., Mehta. A. (2005). Learning symmetric k-juntas in time In the proceedings of «Interface between Harmonic Analysis and Number Theory 2005».
- Mossel, E., O’Donnell, R., Servedio, R. (2003). Learning juntas. In Proceedings of-the 35th Annual ACM Symposium on Theory of Computing, 2003.
- Balcazar, J.L., Diaz, J., Gavalda, R., Watanabe, O. (1994). An optimal parallel algorithm for learning DFA. Proceedings of the seventh annual conference on Computational learning theory, 208−217, 1994.
- Vitter, J.S., Lin, J. (1992). Learning in Parallel. Inf. Comput. 96(2): 179 202, 1992.
- Кудрявцев В.В., Андреев А. Е., Гасанов Э. Э. (2007). Теория тестового распознавания. ФИЗМАТЛИТ, М., 2007.
- Кудрявцев В.Б., Гасанов Э. Э., Долотова О. А., Погосян Г. Р. (2005). Теория тестирования логических устройств. ФИЗМАТЛИТ, М., 2006.
- Bshouty, N.H., Eiron, N. (2002). Learning Monotone DNF from a Teacher that Almost does not Answer Membership Queries. Journal of Machine Learning Research, 3 (Jul): pp. 49−57., 2002.
- Plotkin, M. (I960). Binary codes with specified minimum distance. IRE Transactions on Information Theory, 6:445−450, I960.
- Kargupta, H., Park, B. (2001). Gene expression and fast construction of distributed evolutionary representation. Evolutionary Computation, 9(1):1—32, 2001.
- Heckendorn, R.B., Wright. A.H. (2003). Efficient linkage discovery by limited probing. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003), pages 1003−1014, 2003.
- Публикации автора по теме диссертации
- Осокин, В.В. (2007). Асимптотически оптимальный алгоритм расшифровки разбиения булевого куба на подкубы. Интеллектуальные системы, том 11, вып. 1−4, стр. 635−652 (2007).
- Осокин, В.В. (2008). О сложности расшифровки разбиения булевого куба на подкубы. Дискретная математика, том 20, вып. 2, стр. 46−62 (2008).
- Осокин, В.В. (2009). О параллельной расшифровке разбиений булевого куба. Интеллектуальные системы, том 13, вып. 1−4, стр. 427−454 (2009).
- Осокин, В.В. (2010). Сложность расшифровки монотонных функций с малым числом существенных переменных. Дискретная математика, том 22, вып. 3, стр. 134−145 (2010).
- Осокин, В.В. (2010). О параллельной параметро-эффективной расшифровке псев до-булевских функций. Интеллектуальные системы, том 14, вып. 1−4, стр. 395−424 (2010).
- Osokin, V.V. (2008). On the complexity of decoding Boolean cube splitting into cube faces. Discrete Mathematics and Applications. Volume 18, Issue 3, Pages 155−172, 2008.
- Osokin, V.V. (2010). On learning monotone Boolean functions with irrelevant variables. Discrete Mathematics and Applications. Volume 20, Issue 3, Pages 307−320, 2010.
- Осокин, В.В. (2006). Асимптотика сложности разбиения булевого куба на подкубы. Материалы IX Международной конференции «Интеллектуальные системы и компьютерные науки» (Москва, 23−27 октября 2006 г.), том 1, часть 1, с. 191−193.
- Осокин, В.В. (2007). О расшифровке разбиения булевого куба на грани. Материалы IX Международного семинара «Дискретная математика и