4. Одноленточные машины Тьюринга. Вычисления машин Тьюринга. Рекурсивные и рекурсивно-перечислимые языки (1162495), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Íàïðèìåð,P1 : ßâëÿþòñÿ ëè äâà çàäàííûõ ãðàôà G1 è G2èçîìîðôíûìè?P2 : Èìååò ëè çàäàííîå àëãåáðàè÷åñêîå óðàâíåíèåE (x) = 0 ðåøåíèå, ìåíüøåå çàäàííîãî ÷èñëà c ?P3 : Âûïîëíèìà ëè çàäàííàÿ ôîðìóëà ëîãèêèïðåäèêàòîâ Φ ?P4 : Âåðíî ëè, ÷òî çàäàííàÿ ÌÒ M çàâåðøàåòâû÷èñëåíèÿ íà âñåõ íà÷àëüíûõ êîíôèãóðàöèÿõ?ÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÊàæäàÿ èíäèâèäóàëüíàÿ çàäà÷à ïîëíîñòüþõàðàêòåðèçóåòñÿ íàáîðîì ñâîèõ ñïåöèôè÷åñêèõïàðàìåòðîâ:P1 = hG1 , G2 i ,P2 = hE (x), ci ,P3 = hΦi ,P4 = hMi ,êîòîðûé ìîæåò áûòü ïðåäñòàâëåí (çàïèñàí,çàêîäèðîâàí) ñëîâîì â íåêîòîðîì êîíå÷íîìàëôàâèòå.IIIIÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÌàññîâàÿ ïðîáëåìà ýòî ñîâîêóïíîñòü âñåõèíäèâèäóàëüíûõ çàäà÷ îïðåäåëåííîãî òèïà, âêîòîðîé âûäåëåíî ìíîæåñòâî èíäèâèäóàëüíûõçàäà÷ (âîïðîñîâ), ïðàâèëüíûì îòâåòîì äëÿêîòîðûõ ÿâëÿåòñÿ óòâåðäèòåëüíûé îòâåò ¾äà¿:P1 = {hG1 , G2 i : G1 è G2 èçîìîðôíû} ,P2 = {hE , ci : ∃x(E (x) = 0 ∧ x < c)} ,P3 = {hΦi : ∃I (I |= Φ)} ,P4 = {hMi : ∀α(M(α) êîíå÷íî)} .Òàêèì îáðàçîì, êàæäàÿ ìàññîâàÿ ïðîáëåìàïðåäñòàâëÿåò ñîáîé íåêîòîðûé ÿçûê â êîíå÷íîìàëôàâèòå.IIIIÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÐåøèòü ìàññîâóþ ïðîáëåìó P îçíà÷àåò íàéòèÌÒ (àëãîðèòì) M , êîòîðûé äëÿ ëþáîéèíäèâèäóàëüíîé çàäà÷è w :ïåðåõîäèò â äîïóñêàþùåå ñîñòîÿíèå, åñëèïðàâèëüíûì îòâåòîì äëÿ çàäà÷è w ÿâëÿåòñÿóòâåðäèòåëüíûé îòâåò, ò.å.

w ∈ P ;ïåðåõîäèò â îòâåðãàþùåå ñîñòîÿíèå, åñëèçàäà÷à w èìååò îòðèöàòåëüíûé îòâåò (èëèíåêîððåêòíî ñôîðìóëèðîâàíà), ò.å. w ∈/ P ;.IIÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÐåøèòü ìàññîâóþ ïðîáëåìó P îçíà÷àåò íàéòèÌÒ (àëãîðèòì) M , êîòîðûé äëÿ ëþáîéèíäèâèäóàëüíîé çàäà÷è w :ïåðåõîäèò â äîïóñêàþùåå ñîñòîÿíèå, åñëèïðàâèëüíûì îòâåòîì äëÿ çàäà÷è w ÿâëÿåòñÿóòâåðäèòåëüíûé îòâåò, ò.å. w ∈ P ;ïåðåõîäèò â îòâåðãàþùåå ñîñòîÿíèå, åñëèçàäà÷à w èìååò îòðèöàòåëüíûé îòâåò (èëèíåêîððåêòíî ñôîðìóëèðîâàíà), ò.å.

w ∈/ P ;.Òàêèì îáðàçîì, ìàññîâàÿ ïðîáëåìà P ñ÷èòàåòñÿàëãîðèòìè÷åñêè ðàçðåøèìîé , åñëè P ðåêóðñèâíûé ÿçûê.IIÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÀ êàêîâî ïîëîæåíèå ðåêóðñèâíî ïåðå÷èñëèìûõÿçûêîâ ñðåäè ìàññîâûõ àëãîðèòìè÷åñêèõïðîáëåì?ÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÀ êàêîâî ïîëîæåíèå ðåêóðñèâíî ïåðå÷èñëèìûõÿçûêîâ ñðåäè ìàññîâûõ àëãîðèòìè÷åñêèõïðîáëåì?Ñîãëàñíî òåîðåìå 4.5, ÿçûê L ðåêóðñèâíîïåðå÷èñëèì òîãäà è òîëüêî òîãäà, êîãäàb äëÿ íåêîòîðîãîL = {w : ∃u : w #u ∈ L}ðåêóðñèâíîãî ÿçûêà Lb ⊆ Σ∗#Σ∗ .À ÷òî ïðåäñòàâëÿåò ñîáîé ÿçûê Lb ?ÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛßçûê Lb ñîñòîèò èç ñëîâ w #u , â êîòîðûõw ýòî èíäèâèäóàëüíàÿ çàäà÷à (óðàâíåíèåE (x) = 0 , ïàðà ãðàôîâ (G1 , G2 ) è äð.),èìåþùàÿ ïîëîæèòåëüíîå ðåøåíèå,u ýòî ðåøåíèå çàäà÷è w , ò.å.

¾ñåðòèôèêàò¿(êîðåíü óðàâíåíèÿ, áèåêöèÿ èçîìîðôèçìà èäð), óäîñòîâåðÿþùèé ïðàâèëüíîñòü îòâåòà.IIÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛßçûê Lb ñîñòîèò èç ñëîâ w #u , â êîòîðûõw ýòî èíäèâèäóàëüíàÿ çàäà÷à (óðàâíåíèåE (x) = 0 , ïàðà ãðàôîâ (G1 , G2 ) è äð.),èìåþùàÿ ïîëîæèòåëüíîå ðåøåíèå,u ýòî ðåøåíèå çàäà÷è w , ò.å. ¾ñåðòèôèêàò¿(êîðåíü óðàâíåíèÿ, áèåêöèÿ èçîìîðôèçìà èäð), óäîñòîâåðÿþùèé ïðàâèëüíîñòü îòâåòà.Ðåêóðñèâíîñòü ÿçûêà Lb îçíà÷àåò, ÷òî åñòüàëãîðèòì, ïðîâåðÿþùèé ïðàâèëüíîñòü ðåøåíèÿ uêàæäîé èíäèâèäóàëüíîé çàäà÷è w ìàññîâîéïðîáëåìû L !IIÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÏîýòîìó âîïðîñ î òîì, ñîâïàäàþò ëè êëàññûðåêóðñèâíûõ è ðåêóðñèâíî ïåðå÷èñëèìûõ ÿçûêîâìîæíî èñòîëêîâàòü òàê:Âåðíî ëè, ÷òî êàæäàÿ ïðîáëåìà, äëÿêîòîðîé åñòüàëãîðèòì ïðîâåðêè ïðàâèëüíîñòè ðåøåíèÿ,èìååò òàêæå èàëãîðèòì ïîëó÷åíèÿ ðåøåíèÿ?ÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÝòîò âîïðîñ ìîæíî âûðàçèòü åùå ïðîùå.ÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÝòîò âîïðîñ ìîæíî âûðàçèòü åùå ïðîùå.Õîðîøèé ñòóäåíò òîò, êòî óìååò ïðàâèëüíîðåøàòü çàäà÷è.ÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÝòîò âîïðîñ ìîæíî âûðàçèòü åùå ïðîùå.Õîðîøèé ñòóäåíò òîò, êòî óìååò ïðàâèëüíîðåøàòü çàäà÷è.Õîðîøèé ýêçàìåíàòîð òîò, êòîáåçîøèáî÷íî ïðîâåðÿåò ðåøåíèÿ çàäà÷.ÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÝòîò âîïðîñ ìîæíî âûðàçèòü åùå ïðîùå.Õîðîøèé ñòóäåíò òîò, êòî óìååò ïðàâèëüíîðåøàòü çàäà÷è.Õîðîøèé ýêçàìåíàòîð òîò, êòîáåçîøèáî÷íî ïðîâåðÿåò ðåøåíèÿ çàäà÷.Âåðíî ëè, ÷òî õîðîøèé ýêçàìåíàòîð áûëõîðîøèì ñòóäåíòîì?ÊÎÍÅÖ ËÅÊÖÈÈ 4.

Характеристики

Список файлов лекций