Prax 2: lausearvutuse lahendajatega eksperimenteerimine: erinevus redaktsioonide vahel
Mine navigeerimisribale
Mine otsikasti
Resümee puudub |
Resümee puudub |
||
| (ei näidata sama kasutaja 4 vahepealset redaktsiooni) | |||
| 2. rida: | 2. rida: | ||
Selle ülesande sisuks on: | Selle ülesande sisuks on: | ||
* Pane endal käima vähemalt kaks erinevat olemasolevat, tuntud ja võimsat lausearvutuse lahendajat. Võid valida mõne tuntudm veidi vanema, aga selle sajandi tõestaja (SATO, Grasp, zChaff) ja/või mõne uuema (neid otsi võistluse lehtedelt http://www.satcompetition.org/ ja http://baldur.iti.uka.de/sat-race-2010/) | * Katsetada veidi [http://dijkstra.cs.ttu.ee/~tammet/proplogic.html] lehel olevate erinevate algoritmidega: leia iga kolme algoritmi jaoks (naiivseid pole vaja kasutada) mittetriviaalne ülesanne, mida see algoritm teeb oluliselt kiiremini, kui teised algoritmid. Eeskätt siis leia tabeli ja resolutsioonimeetodi jaoks ülesanded, mis nende puhul lahenduvad oluliselt kiiremini kui dpll-ga. Võibolla see ei õnnestu. | ||
* Pane endal käima vähemalt kaks erinevat olemasolevat, tuntud ja võimsat lausearvutuse lahendajat. Võid valida mõne tuntudm veidi vanema, aga selle sajandi tõestaja (SATO, Grasp, zChaff, [http://minisat.se/ Minisat]) ja/või mõne uuema (neid otsi wiki lõpust http://en.wikipedia.org/wiki/Boolean_satisfiability_problem ja võistluse lehtedelt http://www.satcompetition.org/ ja http://baldur.iti.uka.de/sat-race-2010/). | |||
* Otsi erinevaid ülesande-näidete komplekte. | * Otsi erinevaid ülesande-näidete komplekte. | ||
* Proovi lahendajaid keerukamatel näidetel: | * Proovi lahendajaid keerukamatel näidetel: | ||
| 12. rida: | 14. rida: | ||
*** ja siis googeldada | *** ja siis googeldada | ||
** leia mõned näited, mida üks lahendaja suudab, aga teine ei suuda ntx 10 sekundi jooksul lahendada (mõned võiks olla SAT ja mõned mitte-sat näited) | ** leia mõned näited, mida üks lahendaja suudab, aga teine ei suuda ntx 10 sekundi jooksul lahendada (mõned võiks olla SAT ja mõned mitte-sat näited) | ||
** katseta, kas mõni [http://dijkstra.cs.ttu.ee/~tammet/proplogic.html] lehel lahendaja suudab eelmist liiki ülesannet lahendada (tõenäoliselt ei suuda). | |||
** vaata, kas lahendajal on mingid valitavad otsingustrateegiad: kui jah, siis proovi lahendaja strateegiat sättida, nii et ta suudaks sättimise järel lahendada mõne ülesande, mida ta ilma sättimata ei suutnud | ** vaata, kas lahendajal on mingid valitavad otsingustrateegiad: kui jah, siis proovi lahendaja strateegiat sättida, nii et ta suudaks sättimise järel lahendada mõne ülesande, mida ta ilma sättimata ei suutnud | ||
* Hea mõte - ei ole otse kohustuslik - on genereerida ise ülesandeid, mida lahendaja ei suudaks ntx 10 sek jooksul lahenda. Näiteks nii, et genereerid lihtsamaid, siis keerulisemaid jne kuni lahendajal läheb liiga kaua aega. Kui ülesandeid ise genereerid, siis ei ol vaja mujalt näiteid otsida. | * Hea mõte - ei ole otse kohustuslik - on genereerida ise ülesandeid, mida lahendaja ei suudaks ntx 10 sek jooksul lahenda. Näiteks nii, et genereerid lihtsamaid, siis keerulisemaid jne kuni lahendajal läheb liiga kaua aega. Kui ülesandeid ise genereerid, siis ei ol vaja mujalt näiteid otsida. | ||
Tee tulemustest väike presentatsioon ja kanna praksis ette, aega selleks ca 5 minutit. | Tee tulemustest väike presentatsioon ja kanna praksis ette, aega selleks ca 5 minutit. | ||
Viimane redaktsioon: 12. märts 2015, kell 14:39
Selle ülesande sisuks on:
- Katsetada veidi [1] lehel olevate erinevate algoritmidega: leia iga kolme algoritmi jaoks (naiivseid pole vaja kasutada) mittetriviaalne ülesanne, mida see algoritm teeb oluliselt kiiremini, kui teised algoritmid. Eeskätt siis leia tabeli ja resolutsioonimeetodi jaoks ülesanded, mis nende puhul lahenduvad oluliselt kiiremini kui dpll-ga. Võibolla see ei õnnestu.
- Pane endal käima vähemalt kaks erinevat olemasolevat, tuntud ja võimsat lausearvutuse lahendajat. Võid valida mõne tuntudm veidi vanema, aga selle sajandi tõestaja (SATO, Grasp, zChaff, Minisat) ja/või mõne uuema (neid otsi wiki lõpust http://en.wikipedia.org/wiki/Boolean_satisfiability_problem ja võistluse lehtedelt http://www.satcompetition.org/ ja http://baldur.iti.uka.de/sat-race-2010/).
- Otsi erinevaid ülesande-näidete komplekte.
- Proovi lahendajaid keerukamatel näidetel:
- leia mõned näited, mida kumbki lahendaja ei suuda ntx 10 sekundi jooksul lahendada. Näiteid võid leida:
- http://people.sc.fsu.edu/~jburkardt/data/cnf/cnf.html (enamasti lihtsamad näited)
- http://en.wikipedia.org/wiki/Boolean_satisfiability_problem lõpust
- http://www.satlib.org/ (suur näidete kogu)
- võistlused http://www.satcompetition.org/ ja http://baldur.iti.uka.de/sat-race-2010
- ja siis googeldada
- leia mõned näited, mida üks lahendaja suudab, aga teine ei suuda ntx 10 sekundi jooksul lahendada (mõned võiks olla SAT ja mõned mitte-sat näited)
- katseta, kas mõni [2] lehel lahendaja suudab eelmist liiki ülesannet lahendada (tõenäoliselt ei suuda).
- vaata, kas lahendajal on mingid valitavad otsingustrateegiad: kui jah, siis proovi lahendaja strateegiat sättida, nii et ta suudaks sättimise järel lahendada mõne ülesande, mida ta ilma sättimata ei suutnud
- leia mõned näited, mida kumbki lahendaja ei suuda ntx 10 sekundi jooksul lahendada. Näiteid võid leida:
- Hea mõte - ei ole otse kohustuslik - on genereerida ise ülesandeid, mida lahendaja ei suudaks ntx 10 sek jooksul lahenda. Näiteks nii, et genereerid lihtsamaid, siis keerulisemaid jne kuni lahendajal läheb liiga kaua aega. Kui ülesandeid ise genereerid, siis ei ol vaja mujalt näiteid otsida.
Tee tulemustest väike presentatsioon ja kanna praksis ette, aega selleks ca 5 minutit.