Inteligenta Artificiala

Nu esti logat.

Model test recapitulativ algoritmi

Testul va cuprinde

  1. problema din arbori cu 2 subpuncte (unul cu arbori binari si unul cu arbori oarecare)
  2. problema folosind o tehnica de cautare
  3. problema folosind un algoritm din teoria jocurilor

Se vor da bonusuri pentru comentariile cu interogari, specificatii si explicatii. Se vor da bonusuri pentru rezolvari deosebite.

Model 1

  1. Exercitii cu arbori (15min + 15min)

    1. Consideram niste arbori binari memorati in baza de cunostinte cu ajutorul predicatului arbore_bin(nume, structura_arb), respectiv arbori oarecare memorati sub forma arbore_oarecare(nume, structura_arb), asa cum se vede si in exemplul din teoria laboratorului.

      Nodurile arborilor vor avea drept informatii structuri de forma n(id, nr), unde id-urile sunt unice iar elementele nr sunt numere naturale.

      Vor exista minim 3 exemple de arbori binari, respectiv minim 3 exemple de arbori oarecare in baza de cunostinte.

      Sa se scrie un predicat lista_noduri(+NumeArboreBin,+N, -ListaNoduri), care primeste un nume de arbore binar si un numar natural N si calculeaza lista id-urilor nodurilor cu proprietatea ca suma informatilor (sau mai bine zis a parametrilor de pe pozitia 2 din informatie) pentru parinte, fiul stang si fiul drept este egala cu N. In cazul in care unul dintre noduri lipseste (fie nu are parinte pentru ca e chiar radacina, fie nu are ambii fii, sau e frunza), se vor aduna informatiile doar nodurile existente pentru a testa ca suma lor e egala cu N.

    2. Consideram niste arbori oarecare memorati sub forma arbore_oarecare(nume, structura_arb), asa cum se vede si in exemplul din teoria laboratorului.

      Nodurile arborilor vor avea drept informatii numere naturale.

      Sa se scrie un predicat aduga_noduri(+NumeArboreO, +ListaNoduri, -StructArboreNouO), care primeste un nume de arbore oarecare si o lista de numere naturale. Predicatul va adauga in arborele intial numerele din lista de noduri astfel: pentru fiecare numar N de adaugat cu paritatea P, se va cauta un nod NA in arbore cu proprietatea ca nodurile cu paritate P sunt mai putine decat nodurile de paritate opusa lui P si va adauga nodul N ca fiu al nodului NA. Modul de gasire a nodurilor NA e la alegerea voastra (poate fi gasit de exemplu cu ajutorul unei parcurgeri in preordine sau postordine).

  2. Exercitiu cu tehnici de cautare (50min)

    Se considera o multime de oameni fiecare om avand o submultime dintre acestia trecuti pe un contact-list (de exemplu de mail sau messenger). Se presupune ca fiecare nume e format din doar 2 cuvinte separate printr-un spatiu : 'Prenume Nume' Se considera ca oamenii nu stiu ce prieteni au altii pe contact-list-ul lor. Unul dintre ei isi cauta un fost prieten din copilarie, din al carui nume nu-si mai aminteste decat initialele. El scrie un mesaj in care ii roaga pe toti cei care il primesc sa il trimita mai departe catre prietenii lor si apoi il trimite catre toti prietenii pe care ii are in contact list. Cei care primesc mesajul vad toata lista de forwarduri si nu vor trimite mesajul celor care l-au primit deja (ca sa nu ii enerveze pe cei pe la care a mai trecut mesajul). Totusi daca primesc acelasi mesaj din surse diferite nu se vor mai uita pe lista de forward al celuilalt mesaj (se considera ca nu se mai complica si cu a revedea un mesaj anterior ci se uita doar pe mesajul curent). Deci practic conteaza doar calea urmata de mesajul curent.

    Unii oameni care primesc mesajul insa pot fi ocupati, motiv pentru care nu se vor lasa convinsi sa trimita mai departe mesajul decat dupa ce il vor primi de mai multe ori. Cei liberi trebuie sa il primeasca doar o data. Cei ocupati de cel putin 2 ori. Cei foarte ocupati de cel putin 3 ori. Se considera ca a ajuns un mesaj in momentul in care a fost generat un succesor in graf.

    Predicatul principal va avea forma:
    pred_principal(+FisierIntrare,+Initiala1,+Initiala2,+NumeCautator)

    In final, pentru fiecare persoana cu acele initiale se va arata lantul de e-mailuri prin care a ajuns prima oara (cronologic) mesajul la el.
    Fisierul de intrare va contine urmatoarele informatii pentru fiecare persoana in parte: nume, cat de ocupat este, lista de prieteni care se termina cu un 0. Ultima inregistrare de acest fel nu se va mai termina cu un 0, ci direct cu sfarsitul de fisier.
    Solutiile vor fi scrise sub forma Nume1->Nume2->....NumeK unde Nume1 e cel care a expediat prima oara mesajul, Nume 2 l-a primit de la Nume 1 si l-a trimis la Nume 3, NumeK e ultimul care a primit mesajul.
    Precizari: Pentru fisierul:
    'Ion Popescu'. liber. 'George Danescu'. 'Dan Georgescu'. 'Ion Costescu'. 0.
    'George Danescu'. foarte_ocupat. 'Ion Popescu'. 'Ion Costescu'. 'Dan Georgescu'. 'Lia Dobrescu'. 'Diana Gigescu'. 0.
    'Dan Georgescu'. liber. 'Ion Popescu'. 'George Danescu'. 0.
    'Ion Costescu'. liber. 'Ion Popescu'. 'Daria Geescu'. 'Lia Dobrescu'. 'George Danescu'. 0.
    'Lia Dobrescu'. ocupat. 'George Danescu'. 'Ion Costescu'. 'Daniel Gegescu'. 0.
    'Diana Gigescu'. liber. 'George Danescu'. 0.
    'Daniel Gegescu'. liber. 'Lia Dobrescu'. 0.
    'Daria Geescu'. liber. 'Ion Costescu'. 'Teodor Andreescu'. 0.
    'Teodor Andreescu'. liber. 'Daria Geescu'.
    avem rezultatul:
    | ?- pred_principal('test_recapitulativ_2_vbf.txt','D','G','Ion Popescu').
    Ion Popescu->Dan Georgescu
    Ion Popescu->Ion Costescu->Daria Geescu
    Ion Popescu->George Danescu->Diana Gigescu
    Ion Popescu->Ion Costescu->Lia Dobrescu->Daniel Gegescu
    yes
    Pentru fisierul: (unde am sters relatia de prietenie dintre Ion Costescu si George Danescu)
    'Ion Popescu'. liber. 'George Danescu'. 'Dan Georgescu'. 'Ion Costescu'. 0.
    'George Danescu'. foarte_ocupat. 'Ion Popescu'.  'Dan Georgescu'. 'Lia Dobrescu'. 'Diana Gigescu'. 0.
    'Dan Georgescu'. liber. 'Ion Popescu'. 'George Danescu'. 0.
    'Ion Costescu'. liber. 'Ion Popescu'. 'Daria Geescu'. 'Lia Dobrescu'. 0.
    'Lia Dobrescu'. ocupat. 'George Danescu'. 'Ion Costescu'. 'Daniel Gegescu'. 0.
    'Diana Gigescu'. liber. 'George Danescu'. 0.
    'Daniel Gegescu'. liber. 'Lia Dobrescu'. 0.
    'Daria Geescu'. liber. 'Ion Costescu'. 'Teodor Andreescu'. 0.
    'Teodor Andreescu'. liber. 'Daria Geescu'.
    avem rezultatul:
    | ?- pred_principal('test_recapitulativ_2_vbf1.txt','D','G','Ion Popescu').
    Ion Popescu->Dan Georgescu
    Ion Popescu->Ion Costescu->Daria Geescu
    yes
    | ?-
    Observati ca desi ar fi existat cai posibile de ajungere si la Diana Gigescu si la Daniel Gegescu lantul de mesaje trecea pe la cineva foarte ocupat care nu a mai primit destule mesaje pentru a fi convins sa trimita mesajul mai departe.
  3. Exercitiu cu jocuri (40min)

    Sa se implementeze jocul hare and hounds.

    Predi

    | ?- hare_hounds(3).                                                  
    Vrei sa fii catelus sau iepure? (raspunde c sau i)
    |: c.
    Unde vrei sa faci mutarea (alege un nr)?
      1-4-7  
     /|\|/|\
    0-2-5-8-10
    \|/|\|/
      3-6-9 Starea curenta:
      c-*-*  
     /|\|/|\
    c-*-*-*-i
    \|/|\|/
      c-*-*  
    Pozitie catel de mutat:|: