Úvod do umělé inteligence (léto 99)
 

Zadání úlohy I - Prohledávání stavového prostoru

Implementujte některou z metod slepého prohledávání stavového prostoru pro řešení jedné z následujících úloh. Následně navrhněte a implementujte heuristické funkce vhodné pro řešení této úlohy. Řešení vyhodnoťte a porovnejte s ohledem na počet expanzí nutných k nalezení řešení.
 

1. 8 dam na šachovnici
Rozmístěte 8 dam na šachovnici 8x8 tak, aby se navzájem neohrožovaly.

2. Hra se 6 kameny
Je dána deska o 7 polích (7x1). Tři levá pole jsou obsazena bílými kameny, tři pravá pole jsou obsazena černými kameny. Pole uprostřed je prázdné. Cílem úlohy je přesunout všechny bílé kameny vpravo od černých tak, aby byly všechny bílé i černé kameny na sousedních polích. Lze použít následujících tahů:

3. Piškvorky
Nalezněte optimální herní strategii při hře dvou hráčů na plánu 3x3. Vitězem se stává ten, kdo první dosáhne trojice v řadě, sloupci či uhlopříčce. Vyhrává ten kdo začíná? Zobecněte pro větší herní plány.

4. Tahy jezdcem
Na šachovnici 4x4 ověřte, zda lze jezdcem vstoupit na všechna pole právě jednou. Pokuste se zobecnit pro větší šachovnici. Nalezněte takovou posloupnost tahů, kterými navštíví jezdec každé pole právě jednou.

5. Přelévání vody
Nádoby mají obsah 7, 5 a 3 litry. Sedmilitrová nádoba je plná, ostatní jsou prázdné. Přeléváním naplňte nádoby tak, aby obsahovaly 6, 1 a 0 litrů. Úlohu optimalizujte jednak z hlediska nejmenšího počtu přelití a dále z hlediska nejmenšího objemu přelitých litrů.

6. Lišák
Implementujte hru Lišák. Na čtvercové hrací desce s 9 poli (3x3) je celkem osm kamenů očíslovaných 1 až 8. Úkolem je dosáhnout definovaného cílového stavu z libovolného náhodného uspořádání kamenů. Výstupem programu je posloupnost akcí vedoucích k dosažení cíle.

7. Svět kostek
Sestrojte systém který bude plánovat akce ve svetu kostek. Vstupem systému bude počáteční a cílový stav světa kostek. Jsou povoleny pouze přesuny vrcholových kostek. Výstupem systému bude opět posloupnost přesunů kostek vedoucích k dosažení cíle.
 

Zadání úlohy II - Ulohy na rezoluci

Provedte dukaz metodou rezolucniho zamitnuti pro jednu z nasledujicich uloh.
Vypracovani odevzdejte na papire, kde bude
1.    Zadani
2.    Definice pouzitych predikatu
3.    Mnozina formuli predikatove logiky, popisujici svet pro danou ulohu + negace dokazovaneho tvrzeni
4.    Formule prevedene do klauzalni formy
5.    Vlastni postup odvozeni prazdne klauzule
 

1. Vlkodlaci 1
Je dan ostrov, jehoz obyvatele jsou bud poctivci nebo lhari, pricemz poctivci vzdy mluvi pravdu a lhari naopak vzdy lzou. Navic kazdy obyvatel muze byt vlkodlak.
Mame tri obyvatele A, B, C a plati, ze
- alespon jeden z nich je vlkodlak,
- nikdo neni zaroven poctivec a vlkodlak.
Tvrzeni:
A: "Alespon jeden z nas je poctivec."
B: "Alespon jeden z nas je padouch."
Dokazte, ze C je vlkodlak.

2. Vlkodlaci 2
Je dan ostrov viz predchozi uloha.
Opet potkame tri obyvatele, kde prave jeden z nich je vlkodlak a toto jsou jejich tvrzeni:
A: "C je vlkodlak."
B: "Ja nejsem vlkodlak."
C: "Aspon dva z nas jsou padousi."
Dokazte, ze vlkodlak je padouch a ze A neni vlkodlak.

3. Prolhany lev
Lev lze kazde pondeli, utery a stredu a ostatni dny v tydnu mluvi pravdu.
Dokazte, ze vyrok "Vcera jsem lhal a zitra budu zase." muze prohlasit jen v pondeli nebo stredu.

4. Inspektor Craig
V ustavu jsou pacienti a lekari, normalni a sileni. Sileni maji pravdu za lez a lez za pravdu. Na dotaz "Jste pacient?" odpovi
A: "Verim, ze ano."
B: "Ano."
Dokazte, ze
- A je normalni pacient nebo sileny pacient,
- B je sileny doktor nebo normalni pacient.

5. Ostrov Baraha
Na ostrove Baraha ziji poctivci, padousi a normalni. Poctivec si muze vzit pouze padoucha, padouch poctivce, normalni normalniho.
Tvrzeni:
A: "Moje zena je normalni."
B: "Muj muz neni normalni."
Dokazte, ze manzele A a B jsou normalni.

6. Drakula
Na ostrove jsou lide a upiri. Lide mluvi pravdu, upiri lzou. Navic mohou byt lide upiri bud rozumni (to co si mysli je pravda) nebo pomateni (pravdu maji za lez a lez za pravdu). Pravdu tedy mluvi pouze rozumni lide a pomateni upiri.
Na otazku "Je B clovek?" odpovi A "Myslim, ze ano". Co odpovi B na otazku "Myslite si, ze A je clovek?". Dokazte.

7. Porciiny skrinky
Jsou dve rodiny vyrobcu skrinek, Bellini a Cellini. Kazdy Bellini pise na skrinky pravdive napisy, kazdy Cellini nepravdive. Jedini vyrobci skrinek jsou Bellini mladsi a starsi a Cellini mladsi a starsi. Dokazte, ze nasledujici skrinky vyrobili:
Bellini starsi zlatou a
Cellini starsi stribrnou,
kdyz na skrinkach jsou napisy:
Zlata: Jestlize tuto skrinku zhotovil Bellini, pak stribrnou zhotovil Cellini starsi.
Stribrna: Zlatou skrinku zhotovil Bellini mladsi.

8. Tydlitak a Tydlitek
V ramecku jsou vepsany tri vyroky.
(1) Tydlitak neexistuje
(2) Tydlitek neexistuje
(3) Alespon jeden vyrok v tomto ramecku je pravdivy
Dokazte, ze existuje aspon jeden z nich (Tydlitak nebo Tydlitek).
 
9. Poctivci a padousi 1
Zase mame tri A, B, C a kazdy je bud poctivec nebo padouch. A a B prohlasi:
A: "Vsichni jsme padousi."
B: "Prave jeden z nas je poctivec."
Co jsou A, B a C?

10. Poctivci a padousi 2
Zase mame tri A, B, C a kazdy je bud poctivec nebo padouch. A a B prohlasi:
A: "B je padouch."
B: "A i C maji stejnou povahu."
Co je C?
 

Cvičí:
        Ing. Karel Malý {maly@labe.felk.cvut.cz}
        Ing. Jiří Kubalík {kubalik@labe.felk.cvut.cz}