Iti0210lab72 - Redigeerimiste ajalugu

PriitJ – 15. november 2019, kell 08:04

2019-11-15T08:04:46Z

←Vanem redaktsioon		Redaktsioon: 15. november 2019, kell 10:04
39. rida:		39. rida:

	Kuidas genereerida disjunktide jaoks ''n'' Boole'i muutuja väärtustusi, nii et kindel arv muutujaid oleks tõesed? Üks viis on loendada numbreid kuni 2**n - 1. Binaarkujul annavad need numbrid kõik vajalikud kombinatsioonid, millest tuleb sobivad välja valida. Teine variant on kasutada rekursiivset funktsiooni.		Kuidas genereerida disjunktide jaoks ''n'' Boole'i muutuja väärtustusi, nii et kindel arv muutujaid oleks tõesed? Üks viis on loendada numbreid kuni 2**n - 1. Binaarkujul annavad need numbrid kõik vajalikud kombinatsioonid, millest tuleb sobivad välja valida. Teine variant on kasutada rekursiivset funktsiooni.
	~~<!--~~
	[[Iti0120lab72cnf\|~~Harjutustunni kood~~]]		[[Iti0120lab72cnf\|CNF genereerimise näide]]
	~~-->~~

	== Algoritm ==		== Algoritm ==

PriitJ: /* Sisendandmete genereerimine */

2019-10-31T09:30:27Z

Sisendandmete genereerimine

←Vanem redaktsioon		Redaktsioon: 31. oktoober 2019, kell 11:30
39. rida:		39. rida:

	Kuidas genereerida disjunktide jaoks ''n'' Boole'i muutuja väärtustusi, nii et kindel arv muutujaid oleks tõesed? Üks viis on loendada numbreid kuni 2**n - 1. Binaarkujul annavad need numbrid kõik vajalikud kombinatsioonid, millest tuleb sobivad välja valida. Teine variant on kasutada rekursiivset funktsiooni.		Kuidas genereerida disjunktide jaoks ''n'' Boole'i muutuja väärtustusi, nii et kindel arv muutujaid oleks tõesed? Üks viis on loendada numbreid kuni 2**n - 1. Binaarkujul annavad need numbrid kõik vajalikud kombinatsioonid, millest tuleb sobivad välja valida. Teine variant on kasutada rekursiivset funktsiooni.
			<!--
	[[Iti0120lab72cnf\|Harjutustunni kood]]		[[Iti0120lab72cnf\|Harjutustunni kood]]
			-->

	== Algoritm ==		== Algoritm ==

PriitJ: /* Sisendandmete genereerimine */

2019-03-22T11:50:30Z

Sisendandmete genereerimine

←Vanem redaktsioon		Redaktsioon: 22. märts 2019, kell 13:50
40. rida:		40. rida:
	Kuidas genereerida disjunktide jaoks ''n'' Boole'i muutuja väärtustusi, nii et kindel arv muutujaid oleks tõesed? Üks viis on loendada numbreid kuni 2**n - 1. Binaarkujul annavad need numbrid kõik vajalikud kombinatsioonid, millest tuleb sobivad välja valida. Teine variant on kasutada rekursiivset funktsiooni.		Kuidas genereerida disjunktide jaoks ''n'' Boole'i muutuja väärtustusi, nii et kindel arv muutujaid oleks tõesed? Üks viis on loendada numbreid kuni 2**n - 1. Binaarkujul annavad need numbrid kõik vajalikud kombinatsioonid, millest tuleb sobivad välja valida. Teine variant on kasutada rekursiivset funktsiooni.

	~~<!--~~
	[[Iti0120lab72cnf\|Harjutustunni kood]]		[[Iti0120lab72cnf\|Harjutustunni kood]]
	~~-->~~

	== Algoritm ==		== Algoritm ==

PriitJ – 14. märts 2019, kell 12:02

2019-03-14T12:02:56Z

@@ 7. rida: / 7. rida: @@
 Teeme resolutsioonimeetodil loogika järeldusmootori. Rakendame seda [https://en.wikipedia.org/wiki/Minesweeper_(Windows) Minesweeper] mängus järelduste tegemiseks - tõestame, kas mingi peidetud ruudu all on miin või ei ole.
-Resolutsioonimeetod eeldab konjunktiivsel normaalkujul (KNK, i.k. CNF) sisendit. Leiame viisi, kuidas ''Minesweeperi'' mängulaua osa CNF kujul esitada ning implementeerime [''AIMA''] õpiku versiooni resolutsiooni algoritmist. See sobib väiksemate ülesannete lahendamiseks ja eelkõige algoritmi idee illustreerimiseks. Oluline on algoritm ise implementeerida, et selle tööpõhimõttest aru saada.
+Resolutsioonimeetod eeldab konjunktiivsel normaalkujul (KNK, i.k. CNF) sisendit. Leiame viisi, kuidas ''Minesweeperi'' mängulaua osa CNF kujul esitada ning implementeerime resolutsiooni algoritmi, mis on pisut optimeeritud võrreldes õpiku kirjeldusega. Tööpõhimõttest aru saamiseks tasub lugeda ka õpiku kirjeldust ([''AIMA''] ''Figure 7.12'' ja juuresolev jutt).
 == Minesweeper CNF kujul ==
@@ 40. rida: / 40. rida: @@
 Kuidas genereerida disjunktide jaoks ''n'' Boole'i muutuja väärtustusi, nii et kindel arv muutujaid oleks tõesed? Üks viis on loendada numbreid kuni 2**n - 1. Binaarkujul annavad need numbrid kõik vajalikud kombinatsioonid, millest tuleb sobivad välja valida. Teine variant on kasutada rekursiivset funktsiooni.
 [[Iti0120lab72cnf|Harjutustunni kood]]
-== Õpiku algoritm ==
+== Algoritm ==
-Vaata slaididelt ''Pl-Resolution'' algoritmi või õpikust ''Figure 7.12''. Implementeeri see algoritm (näide on Pythonis nagu alati, keele võid valida oma suva järgi). Kui kasutad slaide, siis [[Iti0210lab72_resolve|''Pl-Resolve'']] funktsioon annab tagasi kõik võimalikud resolutsioonireegli rakendamise tulemused disjunktide C1 ja C2 puhul (neid võib olla mitu või ka mitte ühtegi).
+Implementeeri järgnev algoritm. Põhimõte on sama mis õpikus, resolutsioonireegli rakendamine disjunktidele paarikaupa, siis paarikaupa tekkinud uute disjunktidega ning uutele disjunktidele omavahel jne. Algoritm lõpetab kahel juhul - kui vastuolu leitakse, või kui uusi disjunkte ei õnnestu genereerida.
 '''Pseudokood'''
@@ 97. rida: / 79. rida: @@
 </pre>
-Siin funktsioon <code>resolve()</code> teeb sama asja, mis õpiku algoritmis: kõik võimalikud resolutsioonireegli rakendamise viisid kahele disjunktile.
+Algoritm kasutab järgnevat optimisatsiooni: kui meil on disjunktid ''A v B v C v D'' ja ''A v B v C'' siis neist esimese võib ära jätta - miks, seda saab hästi aru lühema näite pealt: ''a & (a v b)'' on ekvivalentne ''a''-ga. Resolutsioonimeetodi kontekstis nimetatakse seda tehnikat ''forward subsumption'', ehk neeldumine.
-Resolutsioonireegli produktid, mis on tautoloogiad (esineb sama muutuja positiivse ja negatiivse literaalina), võib kohe ära visata, mis annab ka kiirust juurde.
+Resolutsioonireegli produktid, mis on tautoloogiad (esineb sama muutuja positiivse ja negatiivse literaalina), võib kohe ära visata.
 Veel üks lihtsalt rakendatav nipp proovimiseks: sorteeri alguses kandidaatide list, nii et lühemad disjunktid läheksid enne kasutusse.

PriitJ: /* Õpiku algoritm */

2018-11-06T10:16:56Z

Õpiku algoritm

←Vanem redaktsioon		Redaktsioon: 6. november 2018, kell 12:16
44. rida:		44. rida:
	== Õpiku algoritm ==		== Õpiku algoritm ==

	Vaata slaididelt ''Pl-Resolution'' algoritmi või õpikust ''Figure 7.12''. Implementeeri see algoritm (näide on Pythonis nagu alati, keele võid valida oma suva järgi). Kui kasutad slaide, siis [[''Pl-Resolve''~~\|Iti0210lab72_resolve~~]] funktsioon annab tagasi kõik võimalikud resolutsioonireegli rakendamise tulemused disjunktide C1 ja C2 puhul (neid võib olla mitu või ka mitte ühtegi).		Vaata slaididelt ''Pl-Resolution'' algoritmi või õpikust ''Figure 7.12''. Implementeeri see algoritm (näide on Pythonis nagu alati, keele võid valida oma suva järgi). Kui kasutad slaide, siis [[Iti0210lab72_resolve\|''Pl-Resolve'']] funktsioon annab tagasi kõik võimalikud resolutsioonireegli rakendamise tulemused disjunktide C1 ja C2 puhul (neid võib olla mitu või ka mitte ühtegi).

	def resolution_entails(kb, alpha):		def resolution_entails(kb, alpha):

PriitJ: /* Õpiku algoritm */

2018-11-06T10:16:17Z

Õpiku algoritm

←Vanem redaktsioon		Redaktsioon: 6. november 2018, kell 12:16
44. rida:		44. rida:
	== Õpiku algoritm ==		== Õpiku algoritm ==

	Vaata slaididelt ''Pl-Resolution'' algoritmi või õpikust ''Figure 7.12''. Implementeeri see algoritm (näide on Pythonis nagu alati, keele võid valida oma suva järgi). Kui kasutad slaide, siis ''Pl-Resolve'' funktsioon annab tagasi kõik võimalikud resolutsioonireegli rakendamise tulemused disjunktide C1 ja C2 puhul (neid võib olla mitu või ka mitte ühtegi).		Vaata slaididelt ''Pl-Resolution'' algoritmi või õpikust ''Figure 7.12''. Implementeeri see algoritm (näide on Pythonis nagu alati, keele võid valida oma suva järgi). Kui kasutad slaide, siis [[''Pl-Resolve''\|Iti0210lab72_resolve]] funktsioon annab tagasi kõik võimalikud resolutsioonireegli rakendamise tulemused disjunktide C1 ja C2 puhul (neid võib olla mitu või ka mitte ühtegi).

	def resolution_entails(kb, alpha):		def resolution_entails(kb, alpha):

PriitJ: /* Natuke kiirem algoritm */

2018-11-06T10:15:11Z

Natuke kiirem algoritm

←Vanem redaktsioon		Redaktsioon: 6. november 2018, kell 12:15
98. rida:		98. rida:

	Siin funktsioon <code>resolve()</code> teeb sama asja, mis õpiku algoritmis: kõik võimalikud resolutsioonireegli rakendamise viisid kahele disjunktile.		Siin funktsioon <code>resolve()</code> teeb sama asja, mis õpiku algoritmis: kõik võimalikud resolutsioonireegli rakendamise viisid kahele disjunktile.

			Resolutsioonireegli produktid, mis on tautoloogiad (esineb sama muutuja positiivse ja negatiivse literaalina), võib kohe ära visata, mis annab ka kiirust juurde.

	Veel üks lihtsalt rakendatav nipp proovimiseks: sorteeri alguses kandidaatide list, nii et lühemad disjunktid läheksid enne kasutusse.		Veel üks lihtsalt rakendatav nipp proovimiseks: sorteeri alguses kandidaatide list, nii et lühemad disjunktid läheksid enne kasutusse.

PriitJ: /* Sisendandmete genereerimine */

2018-10-30T13:34:31Z

Sisendandmete genereerimine

←Vanem redaktsioon		Redaktsioon: 30. oktoober 2018, kell 15:34
39. rida:		39. rida:

	Kuidas genereerida disjunktide jaoks ''n'' Boole'i muutuja väärtustusi, nii et kindel arv muutujaid oleks tõesed? Üks viis on loendada numbreid kuni 2**n - 1. Binaarkujul annavad need numbrid kõik vajalikud kombinatsioonid, millest tuleb sobivad välja valida. Teine variant on kasutada rekursiivset funktsiooni.		Kuidas genereerida disjunktide jaoks ''n'' Boole'i muutuja väärtustusi, nii et kindel arv muutujaid oleks tõesed? Üks viis on loendada numbreid kuni 2**n - 1. Binaarkujul annavad need numbrid kõik vajalikud kombinatsioonid, millest tuleb sobivad välja valida. Teine variant on kasutada rekursiivset funktsiooni.

			[[Iti0120lab72cnf\|Harjutustunni kood]]

	== Õpiku algoritm ==		== Õpiku algoritm ==

PriitJ: /* Natuke kiirem algoritm */

2018-10-14T13:17:18Z

Natuke kiirem algoritm

←Vanem redaktsioon		Redaktsioon: 14. oktoober 2018, kell 15:17
97. rida:		97. rida:
	Siin funktsioon <code>resolve()</code> teeb sama asja, mis õpiku algoritmis: kõik võimalikud resolutsioonireegli rakendamise viisid kahele disjunktile.		Siin funktsioon <code>resolve()</code> teeb sama asja, mis õpiku algoritmis: kõik võimalikud resolutsioonireegli rakendamise viisid kahele disjunktile.

	Veel üks lihtsalt rakendatav nipp proovimiseks: sorteeri alguses kandidaatide list, nii et lühemad disjunktid ~~oleksid eespool~~.		Veel üks lihtsalt rakendatav nipp proovimiseks: sorteeri alguses kandidaatide list, nii et lühemad disjunktid läheksid enne kasutusse.

PriitJ: /* Natuke kiirem algoritm */

2018-10-14T13:13:55Z

Natuke kiirem algoritm

←Vanem redaktsioon		Redaktsioon: 14. oktoober 2018, kell 15:13
97. rida:		97. rida:
	Siin funktsioon <code>resolve()</code> teeb sama asja, mis õpiku algoritmis: kõik võimalikud resolutsioonireegli rakendamise viisid kahele disjunktile.		Siin funktsioon <code>resolve()</code> teeb sama asja, mis õpiku algoritmis: kõik võimalikud resolutsioonireegli rakendamise viisid kahele disjunktile.

	Veel üks lihtsalt rakendatav nipp proovimiseks: alguses kandidaatide ~~listi sorteerimine~~, nii et lühemad disjunktid oleksid eespool.		Veel üks lihtsalt rakendatav nipp proovimiseks: sorteeri alguses kandidaatide list, nii et lühemad disjunktid oleksid eespool.