Автореферат (1137461), страница 4
Текст из файла (страница 4)
Ïðè ýòîììîæíî ïðîâåðÿòü ñîäåðæàíèå âñåõ íîâûõ îáúåêòîâ íà ïðåäìåò óäîâëåòâîðåíèÿ âíåøíèì îãðàíè÷åíèÿì. Îäíàêî â òàêîì ñëó÷àå ýêñïåðòäîëæåí çàðàíåå ñôîðìóëèðîâàòü âåñü íàáîð îãðàíè÷åíèé, ÷òîáû ãàðàíòèðîâàòü îòñóòñòâèå îøèáîê. Òàêèì îáðàçîì, ýêñïåðòó íåîáõîäèìî çàäàòü ëîãè÷åñêèå ïðàâèëà, êîòîðûå îïèñûâàþò âñå íåâîçìîæíûåêîìáèíàöèè ïðèçíàêîâ â ïðåäìåòíîé îáëàñòè. Òàêàÿ çàäà÷à êðàéíåñëîæíà äëÿ ðåøåíèÿ è, â îáùåì ñëó÷àå, îíà ñðàâíèìà ñ ïîñòðîåíèåì âñåé èìïëèêàòèâíîé òåîðèè âðó÷íóþ. Êðîìå òîãî, ïðè ïîäîáíîìïîäõîäå íå ó÷èòûâàåòñÿ ñïåöèôèêà îïèñàíèÿ ïðåäìåòíîé îáëàñòè,ïðèíÿòàÿ â ÀÔÏ, à òàêæå óæå íàêîïëåííûå çíàíèÿ (îáúåêòû, êîòîðûå óæå ââåäåíû â êîíòåêñò). Ïî ýòîé ïðè÷èíå â ðàìêàõ äàííîéðàáîòû óïîìÿíóòûé ïîäõîä íå ðàññìàòðèâàåòñÿ.Ñóùíîñòè â ÀÔÏ çàäàþòñÿ ïðàãìàòè÷åñêèì îáðàçîì, à èìåííî20 ÷åðåç âçàèìîäåéñòâèå ñ äðóãèìè ñóùíîñòÿìè.
Ïî ýòîé ïðè÷èíå ëþáàÿ èíôîðìàöèÿ, ïîëó÷åííàÿ èç íàçâàíèÿ îáúåêòà, áóäåò âíåøíåéïî îòíîøåíèþ ê ÀÔÏ. Ëþáîé ïîäõîä, îñíîâàííûé íà èñïîëüçîâàíèè íàçâàíèÿ îáúåêòà, íå ìîæåò áûòü îáùåïðèìåíèìûì äëÿ âñåõôîðìàëüíûõ êîíòåêñòîâ. Òàêèì îáðàçîì, íå ìîæåò ñòàâèòüñÿ çàäà÷à íàõîæäåíèÿ âåðíîãî îïèñàíèÿ, èñõîäÿ èç íàçâàíèÿ îáúåêòà.Âñå, ÷òî ïðè òàêîì ïîäõîäå ìîæíî ãàðàíòèðîâàòü, ýòî îòñóòñòâèåòàêîé êîìáèíàöèè ôîðìàëüíûõ ïðèçíàêîâ â ñîäåðæàíèè ôîðìàëüíîãî îáúåêòà, êîòîðàÿ íå âñòðå÷àåòñÿ íè â îäíîì ðåàëüíîì îáúåêòåèç ïðåäìåòíîé îáëàñòè.
Òàêîãî óñëîâèÿ, îäíàêî, äîñòàòî÷íî äëÿ ïîñòðîåíèÿ èìïëèêàòèâíîé òåîðèè ïðåäìåòíîé îáëàñòè, òàê êàê ñàìèíàçâàíèÿ îáúåêòîâ íå èãðàþò äëÿ íåå íèêàêîé ðîëè.Ñ äðóãîé ñòîðîíû, êàê îòìå÷àëîñü â ðàçäåëå 2.2, ìíîæåñòâîâñåõ âåðíûõ èìïëèêàöèé ýêâèâàëåíòíûì îáðàçîì ïðåäñòàâëÿåò ôîðìàëüíûé êîíòåêñò. Êàê ñëåäñòâèå, äëÿ ó÷åòà óæå íàêîïëåííûõ çíàíèé ïðè íàõîæäåíèè îøèáîê ìîæíî èñïîëüçîâàòü ìíîæåñòâî âñåõâåðíûõ èìïëèêàöèé êîíòåêñòà. Êðîìå òîãî, ðàáîòà ñ èìïëèêàöèÿìèäëÿ ïîëüçîâàòåëÿ â îáùåì ïðîùå è èíòóèòèâíî ïîíÿòíåå, òàê êàêèçíà÷àëüíî èìïëèêàöèè ïðèçâàíû ñòðîãî ìàòåìàòè÷åñêè ôîðìàëèçîâàòü óñëîâíîå âûñêàçûâàíèå, ïðèâû÷íîå â îáû÷íîé æèçíè.
Äëÿïîëüçîâàòåëÿ ëåã÷å îòâåòèòü íà âîïðîñ, âûïîëíÿåòñÿ ëè èìïëèêàöèÿ â ïðåäìåòíîé îáëàñòè, ÷åì èñêàòü íåâåðíûå çíà÷åíèÿ â òàáëèöåèëè çàïèñûâàòü âñå âîçìîæíûå ïðàâèëà î òîì, ÷åãî íå ìîæåò áûòü. äðóãèõ îáëàñòÿõ íàóê, îòëè÷íûõ îò ÀÔÏ, çàäà÷à íàõîæäåíèÿ îøèáîê èìååò äëèííóþ èñòîðèþ èçó÷åíèÿ. Ê ñîæàëåíèþ, ðàçðàáîòàííûå ìåòîäû íåïðèìåíèìû â ÀÔÏ èç-çà ñïåöèôèêè ðàáîòûñ áèíàðíûìè òàáëèöàìè.
Êðàòêîå îïèñàíèå ñóùåñòâóþùèõ ïîäõîäîâ, à òàêæå îáîñíîâàíèå íåîáõîäèìîñòè ðàçðàáîòêè íîâîãî ìåòîäàâ ðàìêàõ ÀÔÏ, ïðèâåäåíî â ðàçäåëå 5.1. ïÿòîé ãëàâå âïåðâûå ïðèâîäèòñÿ êëàññèôèêàöèÿ âîçìîæíûõ îøèáîê â ñîäåðæàíèÿõ ôîðìàëüíûõ îáúåêòîâ ÷åðåç çàâèñèìîñòè ïðåäìåòíîé îáëàñòè (ðàçäåë 5.2.1). Âûäåëåíî ÷åòûðå âîçìîæíûõ òèïà îøèáîê, ÿâëÿþùèåñÿ ñëåäñòâèåì íàðóøåíèÿ çàâèñèìîñòåéïðåäìåòíîé îáëàñòè.211.A → b;2.A → b;3.A → b ∨ c;4.A → Φ,ãäåΦ- ëþáàÿ ëîãè÷åñêèå ôîðìóëà êðîìå ïðåäñòàâ-ëåííûõ âûøå, íàïðèìåð,Φ = a ∨ (b ∧ c).Äàëåå ðàññìàòðèâàþòñÿ òîëüêî òèïû 1 è 2, òàê êàê îíè ÿâëÿþòñÿ íàèáîëåå ïðîñòûìè è ÷àñòî âñòðå÷àþùèìèñÿ. ðàçäåëå 5.2.2 àâòîðîì íà îñíîâå ïðîâåäåííîé êëàññèôèêàöèèâîçìîæíûõ îøèáîê ïðåäëîæåíû äâà ðàçíûõ ïîäõîäà ê íàõîæäåíèþîøèáîê â ñîäåðæàíèÿõ ôîðìàëüíûõ îáúåêòîâ. Îäèí èç íèõ îñíîâàííà èñïîëüçîâàíèè áàçèñà èìïëèêàöèé ôîðìàëüíîãî êîíòåêñòà, äðóãîé íà âû÷èñëåíèè çàìûêàíèé ïîäìíîæåñòâ ñîäåðæàíèÿ îáúåêòà.Òàê êàê çàìûêàíèå ìîæåò áûòü âû÷èñëåíî áûñòðî, áîëüøåå âíèìàíèå óäåëåíî âòîðîìó ïîäõîäó.
Èçíà÷àëüíî îáà ïîäõîäà ïîçâîëÿþòíàõîäèòü òîëüêî îäèí òèï îøèáîê. Äëÿ ïîäõîäà, èñïîëüçóþùåãî çàìûêàíèÿ äëÿ âûÿâëåíèÿ îøèáîê, àâòîðó óäàëîñü ïðåäëîæèòü ìîäèôèêàöèþ, ïîçâîëÿþùóþ èñïîëüçîâàòü ïîäõîä äëÿ íàõîæäåíèÿ åùåîäíîãî òèïà îøèáîê. Ìîäèôèêàöèÿ, äîêàçàòåëüñòâî êîððåêòíîñòèïîëó÷àåìûõ ðåçóëüòàòîâ, à òàêæå àëãîðèòì ðàáîòû ïðåäñòàâëåíû âðàçäåëå 5.2.4.Óòâåðæäåíèå 5.2.1Ïóñòü K = (G, M, I), A ⊆ M .
ÌíîæåñòâîIA = {B → d | B ∈ MC A , d ∈ B 00 \ A ∪ A \ B},ãäå MC A = {B ∈ CA |@C ∈ CA : B ⊂ C} è CA = {A ∩ g 0 | g ∈ G}, ÿâëÿåòñÿ òàêèì ìíîæåñòâîì âñåõ àòîìàðíûõ èìïëèêàöèé (èëè èõñëåäñòâèé ñ íåêîòîðûìè ïðèçíàêàìè, äîáàâëåííûìè â ïîñûëêó),èìåþùèõ âèä çàâèñèìîñòåé Òèïîâ 1 è 2, ÷òî îíè âåðíû â êîíòåêñòå K, íå óäîâëåòâîðÿþòñÿ A è èìåþò íåíóëåâóþ ïîääåðæêó.Àëãîðèòì âûãëÿäèò ñëåäóþùèì îáðàçîì.22Input:K = (G, M, I), A ⊆ M .Output: Èìïëèêàöèè, êîòîðûå ïðîòèâîðå÷àò0012if34567CandidatesResult8return ResultA =AthenreturnCandidatesforA.∅= {object0 ∩ A | object ∈ G}= {C ∈ Candidates | @B ∈ Candidates: C ⊆ B}←∅CandidateCandidates doResult.add({Candidate → d |d ∈ (Candidate00 \ A ∪ A \ Candidate)})inÀëãîðèòì 2: inspect_directÓòâåðæäåíèå 5.2.2ëÿåò O(|G| × |M | ).22Âðåìåííàÿ ñëîæíîñòü àëãîðèòìà 2 ñîñòàâ- ðàçäåëå 5.2.5 ñðàâíèâàþòñÿ ðåçóëüòàòû ðàáîòû îáîèõ ïðåäëîæåííûõ âûøå ïîäõîäîâ íà ïðèìåðå èç ðàçäåëà 5.2.3, íà ñëó÷àéíûõ êîíòåêñòàõ è íà ðåàëüíûõ äàííûõ.
Ìåòîä íàõîæäåíèÿ îøèáîê,ïðåäëîæåííûé â íàñòîÿùåé ãëàâå, äîïóñêàåò äðóãîå áîëåå íàãëÿäíîåïðåäñòàâëåíèå ÷åðåç äèàãðàììó ðåøåòêè (ðàçäåë 5.3). ïÿòîé ãëàâå àâòîðîì òàêæå ïðåäëîæåíî îäíî èç âîçìîæíûõíåòðèâèàëüíûõ ïðèìåíåíèé ðàçðàáîòàííûõ ìåòîäîâ äëÿ îòëàäêè èñõîäíîãî ïðîãðàììíîãî êîäà. Ïîäõîä èçëàãàåòñÿ â ðàçäåëå 5.5, ïðèâîäèòñÿ ïðèìåð ïðèìåíåíèÿ ìåòîäà.Îñíîâíûìè ðåçóëüòàòàìè, ïðåäñòàâëåííûìè â ïÿòîé ãëàâû, ÿâëÿþòñÿ ðåøåíèÿ ñëåäóþùèõ çàäà÷.1. Ïðèâåäåíà êëàññèôèêàöèÿ âîçìîæíûõ îøèáîê â áèíàðíûõäàííûõ ñ ïîìîùüþ ïðåäñòàâëåíèÿ ýòèõ îøèáîê ÷åðåç çàâèñèìîñòè â ïðåäìåòíîé îáëàñòè.2. Íà îñíîâå ïðîâåäåííîé êëàññèôèêàöèè îøèáîê ïðåäëîæåíûäâà ìåòîäà íàõîæäåíèÿ îøèáîê.
Îòìå÷åíî, ÷òî îäèí èç íèõ íàõîäèò ðåçóëüòàòû çà ìåíüøåå âðåìÿ. Äîêàçàíî, ÷òî ýòîò ìåòîäïðèâîäèò ê íàõîæäåíèþ íàðóøåííûõ âçàèìîñâÿçåé, êîòîðûå23äî ýòîãî âûïîëíÿëèñü õîòÿ áû äëÿ îäíîãî îáúåêòà èç êîíòåêñòà.3. Ðàçðàáîòàíû ìîäèôèêàöèè áîëåå áûñòðîãî ìåòîäà, ïîçâîëÿþùèå íàõîäèòü îøèáêè äâóõ êëàññîâ. Äîêàçàíà êîððåêòíîñòüðåçóëüòàòîâ.4. Ðàçðàáîòàí è ïðîãðàììíî ðåàëèçîâàí èíòåðàêòèâíûé ïîëèíîìèàëüíûé àëãîðèòì íàõîæäåíèÿ îøèáîê â áèíàðíûõ äàííûõ.Ïîëó÷åíà õàðàêòåðèçàöèÿ â âèäå ìîäèôèöèðîâàííîãî ìåòîäàáëèæàéøèõ ñîñåäåé.5.
Ïðîâåäåíû ýêñïåðèìåíòû ïî îöåíêå êà÷åñòâà íàõîæäåíèÿ îøèáîê, à òàêæå ïî ñêîðîñòè ðàáîòû íà ñëó÷àéíûõ äàííûõ è íàðåàëüíûõ äàííûõ.6. Îñíîâûâàÿñü íà ìåòîäå íàõîæäåíèÿ îøèáîê ïðåäëîæåí ñïîñîáíàõîæäåíèÿ îøèáîê â èñõîäíîì ïðîãðàììíîì êîäå. ðàìêàõ èññëåäîâàíèÿ èìïëèêàòèâíîé òåîðèè ñâîéñòâ ôóíêöèé íà ìíîæåñòâàõ ðàçðàáîòàíû îáùèå ïîäõîäû ê àâòîìàòèçàöèèïðîöåññà òàêîãî èññëåäîâàíèÿ.  ðåçóëüòàòå äàëüíåéøåãî ðàçâèòèÿè óëó÷øåíèÿ ðàíåå ðàçðàáîòàííûõ ïîäõîäîâ â ðàìêàõ èññëåäîâàíèÿàëãåáðàè÷åñêèõ òîæäåñòâ àâòîðó óäàëîñü â àâòîìàòè÷åñêîì ðåæèìå ïîñòðîèòü èìïëèêàòèâíóþ òåîðèþ âñåõ 70 àëãåáðàè÷åñêèõ òîæäåñòâ äëèíû íå áîëåå 5.
Íåîáõîäèìî îòìåòèòü, ÷òî ðåçóëüòàò ïîëó÷åí çà ñ÷åò êîìáèíèðîâàíèÿ ïðàãìàòè÷åñêîãî ïîäõîäà, õàðàêòåðíîãîäëÿ ÀÔÏ, è ó÷åòà ñòðóêòóðû ïðåäìåòíîé îáëàñòè, ïîçâîëÿþùåé íàõîäèòü êîíòðïðèìåðû ê ïîëó÷àåìûì èìïëèêàöèÿì. Ðàçðàáîòàííûåìåòîäû íàõîæäåíèÿ îøèáîê â áèíàðíûõ äàííûõ ïîçâîëÿþò ðàñøèðèòü îáëàñòü ïðèìåíåíèÿ ðàçðàáîòàííûõ ìåòîäîâ àâòîìàòè÷åñêîãîïîñòðîåíèÿ èìïëèêàòèâíûõ òåîðèé íà òîò ñëó÷àé, êîãäà äîñòîâåðíîñòü äàííûõ íåëüçÿ ãàðàíòèðîâàòü, îäíàêî ñ äàííûìè ðàáîòàåò ýêñïåðò â ïðåäìåòíîé îáëàñòè. çàêëþ÷åíèè ïðåäñòàâëåíû îñíîâíûå ðåçóëüòàòû ðàáîòû.1.
Ðàçðàáîòàíû è ïðîãðàììíî ðåàëèçîâàíû ìåòîäû àâòîìàòèçèðîâàííîãî èçó÷åíèÿ èìïëèêàòèâíûõ âçàèìîñâÿçåé ìåæäó24ñâîéñòâàìè ôóíêöèé íà ìíîæåñòâàõ. Èñïûòàíèÿ ïðîãðàììíûõñðåäñòâ ïîäòâåðäèëè èõ ðàáîòîñïîñîáíîñòü.2. Ïîñòðîåíî ìíîæåñòâî èìïëèêàòèâíûõ âçàèìîñâÿçåé ìåæäóñâîéñòâàìè ôóíêöèé íà äâóõ-, òðåõ- è ÷åòûðåõýëåìåíòíûõìíîæåñòâàõ. Ïîëó÷åíû äîêàçàòåëüñòâà ÷àñòè èìïëèêàöèé èçáàçèñà èìïëèêàöèé, ñîñòàâëåí ñïèñîê íåäîêàçàííûõ è íå îïðîâåðãíóòûõ èìïëèêàöèé (îòêðûòûõ âîïðîñîâ).3.
Ðàçðàáîòàíû è ïðîãðàììíî ðåàëèçîâàíû: ìåòîäû àâòîìàòèçèðîâàííîãî ïîñòðîåíèÿ èìïëèêàòèâíûõ âçàèìîñâÿçåé ìåæäóàëãåáðàè÷åñêèìè òîæäåñòâàìè, àëãîðèòìû ïðîâåðêè âûïîëíåíèÿ àëãåáðàè÷åñêèõ òîæäåñòâ; íàõîæäåíèÿ àëãåáð íà áåñêîíå÷íîì íîñèòåëå, óäîâëåòâîðÿþùèõ íåêîòîðîìó ìíîæåñòâó òîæäåñòâ è íå óäîâëåòâîðÿþùèõ íåêîòîðîìó îäíîìó òîæäåñòâó.Èñïûòàíèÿ ïðîãðàììíûõ ñðåäñòâ ïîäòâåðäèëè èõ ðàáîòîñïîñîáíîñòü.4. Ïîñòðîåíî ìíîæåñòâî âñåõ èñòèííûõ èìïëèêàòèâíûõ âçàèìîñâÿçåé ìåæäó àëãåáðàè÷åñêèìè òîæäåñòâàìè äëèíû íå áîëååïÿòè. Ïîëó÷åíû äîêàçàòåëüñòâà âñåõ èìïëèêàöèé èç áàçèñàèìïëèêàöèé.5. Ðàçðàáîòàí ìåòîä íàõîæäåíèÿ îøèáîê â áèíàðíûõ äàííûõ.Ïîëó÷åíî äîêàçàòåëüñòâî òîãî, ÷òî ðàçðàáîòàííûé ìåòîä óäîâëåòâîðÿåò ïðåäúÿâëÿåìûì ê íåìó òðåáîâàíèÿì.
Ïðîãðàììíîðåàëèçîâàí èíòåðàêòèâíûé ïîëèíîìèàëüíûé àëãîðèòì íàõîæäåíèÿ îøèáîê â áèíàðíûõ äàííûõ. Ïðîâåäåííûå òåñòîâûå èñïûòàíèÿ ïîäòâåðäèëè åãî ðàáîòîñïîñîáíîñòü.ÁëàãîäàðíîñòèÀâòîð âûðàæàåò ãëóáîêóþ áëàãîäàðíîñòü íàó÷íîìó ðóêîâîäèòåëþ,äîêòîðó ôèçèêî-ìàòåìàòè÷åñêèõ íàóê Ñåðãåþ Îëåãîâè÷ó Êóçíåöîâó çà ïîñòàíîâêó çàäà÷, ïîñòîÿííîå âíèìàíèå è ïîìîùü â ðàáîòå.Àâòîð âûðàæàåò ãëóáîêóþ áëàãîäàðíîñòü ïðîôåññîðó Âàñåíèíó Âàëåðèþ Àëåêñàíäðîâè÷ó çà ïëîäîòâîðíûå îáñóæäåíèÿ, êðèòè÷åñêèå25çàìå÷àíèÿ è ïîìîùü â ðàáîòå. Àâòîð âûðàæàåò ãëóáîêóþ áëàãîäàðíîñòü ïðîôåññîðó Áåðíàðäó Ãàíòåðó çà ïëîäîòâîðíîå îáñóæäåíèå èâíèìàíèå ê ðàáîòå.Ñïèñîê ïóáëèêàöèé àâòîðà[1] A.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
