Автореферат (1103423)
Текст из файла
ÔÃÁÎÓ ÂÎÌîñêîâñêèéãîñóäàðñòâåííûéóíèâåðñèòåò èìåíè Ì. Â. ËîìîíîñîâàÍà ïðàâàõ ðóêîïèñèÌóñàòîâ Äàíèèë Âëàäèìèðîâè÷Êîìáèíàòîðíûå ìåòîäûâ òåîðèè êîëìîãîðîâñêîé ñëîæíîñòèñ îãðàíè÷åíèåì íà ðåñóðñû01.01.06 ìàòåìàòè÷åñêàÿ ëîãèêà, àëãåáðà è òåîðèÿ ÷èñåëÀÂÒÎÐÅÔÅÐÀÒäèññåðòàöèè íà ñîèñêàíèå ó÷åíîé ñòåïåíèêàíäèäàòà ôèçèêî-ìàòåìàòè÷åñêèõ íàóêÌîñêâà 2014Ðàáîòà âûïîëíåíà íà êàôåäðå ìàòåìàòè÷åñêîé ëîãèêè è òåîðèè àëãîðèòìîâÌåõàíèêî-ìàòåìàòè÷åñêîãî ôàêóëüòåòà ÔÃÁÎÓ ÂÎóíèâåðñèòåò èìåíè Ì.Â.ÌîñêîâñêèéãîñóäàðñòâåííûéËîìîíîñîâà.Íàó÷íûé ðóêîâîäèòåëü:Îôèöèàëüíûå îïïîíåíòû:Âåðåùàãèí Íèêîëàé Êîíñòàíòèíîâè÷,äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê, ïðîôåññîð.Àáëàåâ Ôàðèä Ìàíñóðîâè÷,äîêòîðôèçèêî-ìàòåìàòè÷åñêèõ(ÔÃÀÎÓ ÂÎíûéÊàçàíñêèéóíèâåðñèòåò,íàóê,ïðîôåññîð(Ïðèâîëæñêèé) ôåäåðàëü-Èíñòèòóò âû÷èñëèòåëüíîé ìàòå-ìàòèêè è èíôîðìàöèîííûõ òåõíîëîãèé, êàôåäðà òåîðåòè÷åñêîé êèáåðíåòèêè, çàâ.
êàôåäðîé);Ïîäîëüñêèé Âëàäèìèð Âëàäèìèðîâè÷,êàíäèäàò ôèçèêî-ìàòåìàòè÷åñêèõ íàóê (ÔÃÁÓÍ Ìàòåìàòè÷åñêèé èíñòèòóò èì. Â.À. Ñòåêëîâà ÐÀÍ, îòäåë ìàòåìàòè÷åñêîé ëîãèêè, ñòàðøèé íàó÷íûé ñîòðóäíèê).Âåäóùàÿ îðãàíèçàöèÿ:ÔÃÁÓÍ Ñàíêò-Ïåòåðáóðãñêîå îòäåëåíèå Ìàòåìàòè÷åñêîãî èíñòèòóòà èì. Â.À. Ñòåêëîâà ÐÀÍ.Çàùèòà äèññåðòàöèè ñîñòîèòñÿ 13 ôåâðàëÿ 2015 ã. â 16 ÷. 45 ìèí. íà çàñåäàíèèäèññåðòàöèîííîãî ñîâåòà Ä 501.001.84, ñîçäàííîãî íà áàçå ÔÃÁÎÓ ÂÎÌîñêîâñêèéãîñóäàðñòâåííûé óíèâåðñèòåò èìåíè Ì.Â.
Ëîìîíîñîâà, ïî àäðåñó: Ðîññèéñêàÿ Ôåäåðàöèÿ, 119991, Ìîñêâà, ÃÑÏ-1, Ëåíèíñêèå ãîðû, ä. 1, ÔÃÁÎÓ ÂÎ ÌÃÓ èì. Ì.Â.Ëîìîíîñîâà, Ìåõàíèêî-ìàòåìàòè÷åñêèé ôàêóëüòåò, àóä. 14-08.Ñ äèññåðòàöèåé ìîæíî îçíàêîìèòüñÿ â Ôóíäàìåíòàëüíîé áèáëèîòåêå ÔÃÁÎÓ ÂÎÌÃÓ èì. Ì.Â. Ëîìîíîñîâà ïî àäðåñó: Ìîñêâà, Ëîìîíîñîâñêèé ïðîñïåêò, ä. 27, ñåêòîðÀ, à òàêæå â ñåòè Èíòåðíåò ïî àäðåñóhttp://mech.math.msu.su/~snark/index.cgi.Àâòîðåôåðàò ðàçîñëàí 13 ÿíâàðÿ 2015 ã.Ó÷¼íûé ñåêðåòàðüäèññåðòàöèîííîãî ñîâåòàÄ 501.001.84, ñîçäàííîãî íà áàçåÔÃÁÎÓ ÂÎ ÌÃÓ èì.
Ì.Â. Ëîìîíîñîâà,äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê,ïðîôåññîðÈâàíîâ Àëåêñàíäð Îëåãîâè÷Îáùàÿ õàðàêòåðèñòèêà ðàáîòûÀêòóàëüíîñòü òåìûÏîíÿòèå êîëìîãîðîâñêîé ñëîæíîñòè ïîÿâèëîñü â 1960-õ ãîäàõ â ðà-1áîòàõ Êîëìîãîðîâà , Ñîëîìîíîâà2è ×åéòèíà3,4. Êîëìîãîðîâñêóþ ñëîæ-íîñòü ìîæíî îïðåäåëÿòü äëÿ ëþáûõ êîíå÷íûõ îáúåêòîâ, íî äîñòàòî÷íîðàññìàòðèâàòü äâîè÷íûå ñëîâà, ò.å. êîíå÷íûå ïîñëåäîâàòåëüíîñòè èç íóëåé è åäèíèö. Íåôîðìàëüíî ãîâîðÿ, ñëîæíîñòü ñëîâà åñòü ñëîæíîñòü åãîàëãîðèòìè÷åñêîãî îïèñàíèÿ, ò.å. äëèíà êðàò÷àéøåé ïðîãðàììû, êîòîðàÿïå÷àòàåò ýòî ñëîâî íà ïóñòîì âõîäå. Òàêæå ðàññìàòðèâàþò óñëîâíóþñëîæíîñòü îäíîãî ñëîâà îòíîñèòåëüíî äðóãîãî, ò.å.
äëèíó êðàò÷àéøåéïðîãðàììû, ïå÷àòàþùåé ïåðâîå ñëîâî ïîñëå ïîëó÷åíèÿ íà âõîä âòîðîãî.Ðàçóìååòñÿ, ýòè îïðåäåëåíèÿ çàâèñÿò îò òîãî, êàêîé ÿçûê ïðîãðàììèðîâàíèÿ èñïîëüçóåòñÿ äëÿ îïèñàíèÿ, íî ñîãëàñíî òåîðåìå ÊîëìîãîðîâàÑîëîìîíîâà ñóùåñòâóåò îïòèìàëüíûé ÿçûê ïðîãðàììèðîâàíèÿ, ïðè êîòîðîì ñëîæíîñòè âñåõ ñëîâ ìèíèìàëüíû ñ òî÷íîñòüþ äî àääèòèâíîéêîíñòàíòû. Ýòî ïîçâîëÿåò íå ññûëàòüñÿ íà êîíêðåòíûé ÿçûê ïðîãðàììèðîâàíèÿ è ïðè ýòîì ôîðìóëèðîâàòü ðàçëè÷íûå óòâåðæäåíèÿ î ñâÿçèñëîæíîñòåé ðàçëè÷íûõ ñëîâ.
Ýòè óòâåðæäåíèÿ ôîðìóëèðóþòñÿ ñ òî÷íîñòüþ äî àääèòèâíîé êîíñòàíòû, çàâèñÿùåé òîëüêî îò âûáîðà îïòèìàëüíîãî ÿçûêà ïðîãðàììèðîâàíèÿ è íå çàâèñÿùåé îò êîíêðåòíûõ ñëîâ. ôîðìóëèðîâêàõ ýòà êîíñòàíòà òðàäèöèîííî îáîçíà÷àåòñÿ ÷åðåçO(1).(Íåêîòîðûå óòâåðæäåíèÿ ôîðìóëèðóþòñÿ ñ òî÷íîñòüþ äî äðóãîãî àääèòèâíîãî ñëàãàåìîãî:O(log n), O(log3 n)è ò.ï.) Ê ñîæàëåíèþ, äî ñèõïîð íå ñëîæèëîñü åäèíîãî îáîçíà÷åíèÿ äëÿ ñëîæíîñòè.  äèññåðòàöèèx îáîçíà÷àåòñÿ ÷åðåç C(x), à óñëîâíàÿ ñëîæíîñòü ñëîâày ÷åðåç C(x|y).ñëîæíîñòü ñëîâàxîòíîñèòåëüíîÒàêæå ðàññìàòðèâàþò êîëìîãîðîâñêóþ ñëîæíîñòü ñ îãðàíè÷åíèåì íàðåñóðñû.5 ýòîì ñëó÷àå ïðîãðàììà, ãåíåðèðóþùàÿ ñëîâî, äîëæíà áûòü1 À.Í.Êîëìîãîðîâ. Òðè ïîäõîäà ê îïðåäåëåíèþ ïîíÿòèÿ Êîëè÷åñòâî èíôîðìàöèè // Ïðîáëåìû ïåðåäà÷è èíôîðìàöèè.
1965. Ò.1. 1. Ñ. 311.2 R.J. Solomono. A Formal Theory of Inductive Inference, Part 1, Part 2 // Information and Control(now Infromation and Computation). 1964. V. 7. P. 122, 224254.3 G.J. Chaitin. On the length of programs for computing binary sequences // Journal of the ACM 1966. V. 13. 4. P. 547569.4 G.J. Chaitin. On the length of programs for computing binary sequences: statistical considerations// Journal of the ACM. 1969. V. 16.
1. P. 145159.5 M. Li, P.M.B. Vitanyi. An Introduction to Kolmogorov Complexity and its Applications. 3rd1íå òîëüêî êîðîòêîé, íî è èñïîëüçóþùåé îãðàíè÷åííûå âû÷èñëèòåëüíûåðåñóðñû, à èìåííî âðåìÿ ðàáîòû è ïàìÿòü. Ðàçóìååòñÿ, ïðè íàëîæåíèèýòèõ äîïîëíèòåëüíûõ îãðàíè÷åíèé ñëîæíîñòü íå óìåíüøàåòñÿ. Âàæíî,÷òî â îòëè÷èå îò ñëîæíîñòè áåç îãðàíè÷åíèé ñëîæíîñòü ñ îãðàíè÷åíèÿìèÿâëÿåòñÿ âû÷èñëèìîé ôóíêöèåé.Äëÿ äîêàçàòåëüñòâà òîãî, ÷òî ñëîæíîñòü íåêîòîðîãî ñëîâà ìàëà, ÷àñòî èñïîëüçóþò ñëåäóþùèé ïðèíöèï, âîñõîäÿùèé ê Ñèïñåðó:6ýëåìåíòûëþáîãî íåáîëüøîãî ïåðå÷èñëèìîãî ìíîæåñòâà ïðîñòû.
Áîëåå òî÷íî: åñëè ïåðå÷èñëèìîå ìíîæåñòâîSK ñëîâ äëèíû n, òîlog K + log n + O(1). Äåé-ñîäåðæèò íå áîëüøåâñå ýòè ñëîâà èìåþò ñëîæíîñòü íå áîëüøåñòâèòåëüíî, êàæäîå èç íèõ ìîæíî çàäàòü ïåðå÷èñëÿþùèì àëãîðèòìîì,äëèíîén è íîìåðîì â ïåðå÷èñëåíèè ñëîâ äàííîé äëèíû. Ýòî íàáëþäåíèåïîçâîëÿåò äîêàçûâàòü ðàçëè÷íûå óòâåðæäåíèÿ î êîëìîãîðîâñêîé ñëîæíîñòè ÷åðåç êîìáèíàòîðíûå êîíñòðóêöèè: ñíà÷àëà ñòðîèòñÿ íåêîòîðîåïåðå÷èñëèìîå ìíîæåñòâî, çàòåì êîìáèíàòîðíûìè ìåòîäàìè äîêàçûâàåòñÿ âåðõíÿÿ îöåíêà íà åãî ðàçìåð, è, íàêîíåö, äåëàåòñÿ âûâîä î ìàëîéñëîæíîñòè ëþáîãî âõîäÿùåãî â íåãî ñëîâà. Áîëåå òîãî, åñëè ïåðå÷èñëÿþùèé àëãîðèòì âû÷èñëèòåëüíî ýôôåêòèâåí, òî ñëîæíîñòü ñ îãðàíè÷åíèåì íà ðåñóðñû òàêæå ìàëà.
 äèññåðòàöèè èçó÷àþòñÿ äâà ïðèìåðàòàêîãî ïîäõîäà.7Âî-ïåðâûõ, èçó÷àåòñÿ òåîðåìà Ìó÷íèêà îá óñëîâíîì êîäèðîâàíèè.Îíà ãëàñèò, ÷òî äëÿ ëþáûõ ñëîâaèb,òàêèõ ÷òîC(a|b) < k ,íàéä¼ò-p äëèíû k , äëÿ êîòîðîãî îäíîâðåìåííî âåðíû ñîîòíîøåíèÿC(a|b, p) = O(log n) è C(p|a) = O(log n), ãäå n = C(a). Èíûìè ñëîâàìè, ñðåäè âñåõ îïèñàíèé a ïðè èçâåñòíîì b íàéä¼òñÿ p, ïðîñòîå îòíîñèòåëüíî a. Ïðèíöèï äîêàçàòåëüñòâà òàêîé: ðàññìàòðèâàåòñÿ íåêîòîðîåñåìåéñòâî õåø-ôóíêöèé, îòîáðàæàþùèõ ñëîâà äëèíû n â ñëîâà äëèíûk . Ñëîâî p ñòðîèòñÿ êàê îáðàç ñëîâà a, ïîýòîìó äëÿ åãî îïèñàíèÿ òðåáóåòñÿ ëèøü çàäàòü íîìåð õåø-ôóíêöèè. Äëÿ òîãî, ÷òîáû a ìîæíî áûëîâîññòàíîâèòü ïî b è p, íóæíî ÷òîáû p ìîãëî áûòü âûáðàíî êàê õåøñÿ ñëîâîçíà÷åíèå ó íå ñëèøêîì áîëüøîãî ÷èñëà ñëîâ, èìåþùèõ ñëîæíîñòü íåáîëüøåkïðè óñëîâèèb.Ýòîãî ìîæíî äîáèòüñÿ, íàëîæèâ ñïåöèàëüíûåEdition.
Springer, 2008. XXIV, 792 p.6 M. Sipser. A Complexity Theoretic Approach to Randomness // Proceedings of the 15th AnnualACM Symposium on Theory of Computing. 1983. P. 330335.7 An.A. Muchnik. Conditional Complexity and Codes // Theoretical Computer Science. 2002. V. 271. 12. P. 97109.2êîìáèíàòîðíûå òðåáîâàíèÿ íà ñåìåéñòâî ôóíêöèé. Ñàì Àí.À.Ìó÷íèê8èñïîëüçîâàë ñâîéñòâî ýêñïàíäåðà, À.Øåíüèñïîëüçîâàë ñâîéñòâî ñóùå-ñòâîâàíèÿ îíëàéí-ïàðîñî÷åòàíèé, à â äèññåðòàöèè ïîêàçàíî, ÷òî ìîæíîðàññìîòðåòü ñâîéñòâî ýêñòðàêòîðà.Ïîíÿòèå ýêñòðàêòîðà áûëî ââåäåíî â íà÷àëå 1990-õ ãîäîâ â ðàáîòå9Í.Íèñàíà è Ä.Öóêåðìàíàêàê òåõíè÷åñêèé èíñòðóìåíò.
Íåôîðìàëüíîãîâîðÿ, ýêñòðàêòîð ýòî ôóíêöèÿ, êîòîðàÿ ïîëó÷àåò íà âõîä äâåî÷åíü õîðîøèå ñëó÷àéíûå âåëè÷èíû è ïðåâðàùàåò èõ âïî÷òèíåñëó÷àé-íûå.  ïîñëåäóþùèå ãîäû áûëî ðàçðàáîòàíî ìíîæåñòâî êîíñòðóêöèé è10,11,12ïðèëîæåíèé ýêñòðàêòîðîâ, ê êîòîðûì äèññåðòàöèÿ äîáàâëÿåò åù¼îäíî.Àí.À.Ìó÷íèê òàêæå äîêàçàë âàðèàöèþ òåîðåìû äëÿ äâóõ óñëîâèé.Îíà ãëàñèò, ÷òî äëÿ ëþáûõ ñëîâC(a|c) < l,a, bèc,òàêèõ ÷òîC(a|b) < kèl 6 k , íàéä¼òñÿ ñëîâî p äëèíû k , òàêîå ÷òî äëÿ íåãîâåðíû ñîîòíîøåíèÿ C(a|b, p) = O(log n) è C(p|a) = O(log n), à äëÿ åãîíà÷àëà q äëèíû l âåðíî C(a|c, q) = O(log n).
Ìîæíî îáîáùèòü ýòó òåîðåãäåìó íà ëþáîå êîíñòàíòíîå è äàæå ïîëèíîìèàëüíîå ÷èñëî óñëîâèé. Èíûìèñëîâàìè, ïðîãðàììû, ïðåâðàùàþùèå ðàçíûå ñëîâà âñòû îòíîñèòåëüíîa,íå òîëüêî ïðî-a, íî è ÿâëÿþòñÿ ïðåôèêñàìè îäíîé è òîé æå äëèííîéïðîãðàììû ñ òî÷íîñòüþ äî íåáîëüøèõ äîáàâîê ëîãàðèôìè÷åñêîé äëèíû. Ïðèíöèï äîêàçàòåëüñòâà ýòîé òåîðåìû òàêîé æå, íî êîìáèíàòîðíîåóñëîâèå íà ñåìåéñòâî ôóíêöèé áóäåò íåñêîëüêî äðóãèì.Âòîðûì ïðèìåðîì ïàðàëëåëèçìà ìåæäó ñëîæíîñòíûìè è êîìáèíàòîðíûìè óòâåðæäåíèÿìè ÿâëÿþòñÿ òåîðåìû î ñóùåñòâîâàíèè êîëìîãîðîâñêèõ ýêñòðàêòîðîâ (îáû÷íûõ è óñèëåííûõ).
Êîëìîãîðîâñêèì ýêñòðàêòîðîì íàçûâàåòñÿ ôóíêöèÿ äâóõ àðãóìåíòîâ, çíà÷åíèå êîòîðîé èìååò ìåíüøèéäåôåêò ñëó÷àéíîñòè, ò.å. ðàçíîñòü ìåæäó äëèíîé è ñëîæ-íîñòüþ, ÷åì êàæäûé èç å¼ àðãóìåíòîâ. Åñëè8 A.óñëîâíûéäåôåêò ñëó÷àé-Shen. Combinatorial Proof of Muchnik's Theorem // M. Hutter, W. Merkle, P. Vitanyi,eds. Kolmogorov complexity and applications. 2006. Dagstuhl Seminar Proceedings 06051.
http://drops.dagstuhl.de/opus/volltexte/2006/625.9 N. Nisan, D. Zuckerman. Randomness is Linear in Space // Journal of Computer and SystemSciences. 1996. V. 52. 1. P. 4352.10 R. Shaltiel. Recent Developments in Explicit Constructions of Extractors // Current and Trendsin Theoretical Computer Science: The Challenge of the New Century. Volume 1: Algorithms andComplexity. World Scientic, 2002. P. 189228.11 R.
Shaltiel. An Introduction to Randomness Extractors // Proceedings of the InternationalConference on Automata, Languages and Programming. 2011. LNCS V. 6756. 2. P. 2141.12 S. Vadhan. Pseudorandomness. Draft survey/monograph. 2012. http://people.seas.harvard.edu/ salil/pseudorandomness/3íîñòè, ò.å. ðàçíîñòü ìåæäó äëèíîé è óñëîâíîé ñëîæíîñòüþ çíà÷åíèÿôóíêöèè ïðè óñëîâèè îäíîãî èç àðãóìåíòîâ, òàêæå óìåíüøàåòñÿ, òîòàêàÿ ôóíêöèÿ íàçûâàåòñÿ óñèëåííûì êîëìîãîðîâñêèì ýêñòðàêòîðîì.Êîëìîãîðîâñêèå ýêñòðàêòîðû áûëè îïðåäåëåíû Äæ.
Õè÷êîêîì è ñîàâòîðàìè13,1415,16,17è çàòåì èçó÷àëèñü Ì. Çèìàíäîì. Çèìàíä îïðåäåëèëêîìáèíàòîðíûå ïîíÿòèÿ ï¼ñòðûõ è ðàâíîìåðíî ï¼ñòðûõ òàáëèö, äîêàçàë èõ ñóùåñòâîâàíèå è ïîêàçàë, ÷òî îíè ÿâëÿþòñÿ êîëìîãîðîâñêèìèýêñòðàêòîðàìè (îáû÷íûìè è óñèëåííûìè).Îñíîâíîé òåìîé äèññåðòàöèè ÿâëÿåòñÿ ðàñïðîñòðàíåíèå èçâåñòíûõðåçóëüòàòîâ î êîëìîãîðîâñêîé ñëîæíîñòè íà ñëîæíîñòü ñ îãðàíè÷åíèåì íà ðåñóðñû. Äîñòèæåíèé â ýòîì íàïðàâëåíèè íå òàê ìíîãî. Ìîæíî18îòìåòèòü ðåçóëüòàò Ò. Ëè è À.Å.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
