Proiecte la disciplina Inteligenţă ArtificialăInformatică 3, Sem. 2, anul 1999-2000

Există două tipuri de proiecte: individuale şi colective. În plus, mai multe proiecte (individuale ori colective) pot să fie integrate în grupuri de proiecte, deci orientate către o funţionalitate globală – de sistem. Prin aceasta se urmăreşte ca studenţii să colaboreze în vederea realizării unor aplicaţii complexe. În cadrul unui grup, proiectele se vor realiza în ideea de a schimba informaţii între ele. Arhitectura recomandată este aceea în care fiecare modul realizează o funcţie dată, fiind cuplat în sistem prin intermediul a trei tipuri de porţi: de intrare, de ieşire şi de acces la resurse (v. Figura 1).

Figura 1: Interfaţa unui modul cu sistemulIntrările şi ieşirile vor fi compatibilizate prin intermediul unor standarde care trebuiesc precizate cu exactitate. Descrierea standardelor de intrare/resurse/ieşire urmăreşte şi obişnuirea studentului cu elaborarea documentaţiei. Predarea fiecărui proiect va consta din:

- o prezentare a codului sursă cu un dialog asupra soluţiilor adoptate,- documentaţia care să descrie:

o intrările/resursele/ieşirile şi standardele lor;

o funcţionalitatea modulului;

o comentarea funcţiilor.

- demonstraţia de funcţionare.Fiecare proiect colectiv trebuie „apărat” de fiecare membru al echipei, pe zonele contribuţiei fiecăruia. Prestaţia individuală în momentul predării este deci importantă, dv. trebuind a convinge că aţi avut o contribuţie activă la realizarea lui. Acest lucru poate să ducă inclusiv la notări diferite a membrilor echipei. În plus, o componentă în notarea proiectelor ce sînt integrate în grupuri o va constitui funcţionarea ansamblului. Este deci important ca dv. să abordaţi problema realizării aplicaţiei în întregul ei, să vă organizaţi, să vă întîlniţi şi să discutaţi periodic pentru rezolvarea problemelor de interfaţă dintre dv., iar în anumite cazuri chiar să daţi o mînă de ajutor echipelor care au dificultăţi.

modul

resurse

standardeintrări

standardeieşiri

ieşiriintrări

Grupul de proiecte ADNOTARE – îndrumător Dan CristeaANNO1 – Marcator de expresiiNr. studenţi: 2

Veţi scrie un program capabil a marca într-un format ca cel de mai jos, expresiile cuprinse într-un text dat ce sînt găsite după diferite scheme de adnotare (criterii). Marcajele generate vor fi de forma:

<tag ID=ident ...>expresie</tag>unde: tag este o etichetă, ident este un identificator unic, iar expresie este expresia de adnotat. Se vor implementa două scheme de adnotare:

- expresii cheie: se consideră o listă dată de expresii în limba română. Marcarea va trebui să nu fie sensibilă la forma flexionară a cuvintelor (în cazul cuvintelelor din listă ce sînt variabile). Cîmpul tag va fi în acest caz cw (o simplificare a sintagmei engleze cue-word). În lista de atribute a marcajului va apare atributul type cu o valoare care este dată în lista iniţială pentru fiecare expresie în parte.

- Expresia de adnotat, printr-o pereche de doi indecşi (de început şi de sfîrşit) ai literelor din text, este dată de un un alt proces împreună cu tag şi perechile atribut=valoare ce trebuiesc incluse în marcaj.

Indicaţii şi bibliografieVeţi colabora cu proiectele: Marcator de propoziţii, Marcator interactiv de clauze, Operator de marcaje SGML.Resursele vor fi constituite în acest caz din lista de expresii şi tipuri.

ANNO2 – Marcator de propoziţiiNr. studenţi: 2

Se consideră un text în limba română în intrare. Să se scrie un program capabil a găsi graniţele dintre propoziţii. Ieşirea va fi constituită din textul iniţial îmbogăţit cu marcaje (SGML) de forma:

<seg ID=ident>propoziţie</seg>unde ident este un identificator unic, iar propoziţie este propoziţia de marcat. Programul va trebui să implementeze doar criteriile de adnotare, adnotarea propriu-zisă fiind realizată de proiectul Marcator de expresii, cu care veţi colabora.

Indicaţii şi bibliografieMirela Petrea

ANNO3 – Marcator interactiv de clauzeNr. studenţi: 2

Se va scrie un program care va asista un proces manual de marcare a limitelor de clauze într-un text. O clauză este în general o propoziţie, dar poate fi şi o construcţie sub-propoziţională în care există un predicat. Utilizatorul va trebui să poată introduce, într-o

manieră grafică atractivă, semne grafice care vor denota limite de clauze, în locurile indicate de el în text prin mişcări de mouse şi click-uri. Programul va comunica cu proiectul Marcator de expresii pentru ca acesta să opereze marcarea efectivă a clauzelor, în maniera SGML:

<unit ID=ident>clauză</unit>unde ident este un identificator unic. Textul originar nu poate fi afectat în nici un fel, dar programul va trebui să-i sugereze utilizatorului pe ecran locurile unde aceste clauze au fost înscrise. Programul va trebui de asemena să ofere posibilitatea ştergerii unor marcaje deja înscrise.

Indicaţii şi bibliografie

ANNO4 – Operator de marcaje SGMLNr. studenţi: 2

Se va scrie un program care să poată opera asupra unor texte marcate SGML. Operaţiile ce vor trebui realizate sînt:

- elimin toate marcajele de tipul m;- elimin toate segmentele de text marcate cu tipul m (operaţie distructivă

asupra textului);- extrag într-o listă, toate segmentele de text din textul original, marcate cu

tipul m;- combin două fişiere ce conţin marcaje asupra aceluiaşi text original într-

unul singur. Marcajele rezultate trebuie să satisfacă condiţia de ne-încrucişare. Ele pot însă fi cuprinse unele în altele (vezi figura). Marcajele care nu respectă condiţia de neîncrucişare vor trebui semnalate. Utiilizatorul ar trebui să aibă controlul pentru a hotărî modificările ce trebuiesc realizate în marcaje pentru corectarea acestor erori.

Indicaţii şi bibliografieProgramul va trebui să comunice obligatoriu cu proiectul Marcator de expresii pentru stabilirea în comun a structurii fişierului de marcaje. Orice operaţii asupra marcajelor se realizează asupra unui fişier de acest tip şi nu asupra textului original, care nu trebuie să fie afectat în nici un fel. Puteţi consulta: Cristea, Dan; Ide, Nancy; Romary, Laurent (1998). Marking-up Multiple view of a text. Discourse and Reference. In Proceedings of ELRA, Granada (postcript file and PowerPoint presentation)

ANNO5 – Învăţare reguli de delimitare a clauzelorNr. studenţi: 4

marcaje încrucişate - invalide

marcaje încuibărite - valide

Evidenţierea limitelor de clauze se va face pe baza unor cuvinte-cheie ce sînt marcate în text. Exemplele următoare pun în evidenţă cîteva astfel de cazuri:

Deşi afară ploua, am plecat de acasă fără umbrelă. Cînd omul a ajuns pe faleză, fiind înghesuit de reporteri, a plecat în mare grabă.Cu toate că ceasul arăta că nu mai e timp pentru o interogare completă, totuşi, rumegînd toată ziua o cale de a-l face pe Walker să se dea de gol, Colombo îi strecură subtil un motiv care să-l facă să se gîndească că o bănuială planează asupra lui, astfel ajutîndu-l să facă o greşeală.

În exemplele de mai sus cuvintele cheie care ajută la delimitarea clauzelor sînt subliniate. Alte indicatoare de limite de clauze pot fi verbele la gerunziu (marcate aici în italic) şi (uneori) semnele de punctuaţie. Să mai reţinem că o clauză conţine cel puţin un verb la un timp finit.

Să se scrie un program care, plecînd de la un text în care sînt marcate expresii cheie (deşi, cînd, cu toate că etc.), verbele (cu timpul la care apar), semnele de punctuaţie, şi limitele de demarcare a clauzelor, învaţă reguli de găsire a acestor limite. Pentru experimentare se va folosi un text de o pagină de carte în care se vor marca în SGML toate elementele considerate importante pentru procesul de învăţare. Programul va trebui să se comporte la fel pe orice alt text marcat corespunzător.

Indicaţii: Articolele sunt disponibile aici.

Grupul de proiecte OPERAŢII PE ARBORI – îndrumător Dan CristeaTREE1 – Stiva de arboriNr. studenţi: 2

Se consideră o listă conţinînd un şir de simboluri şi o stivă ale cărei intrări sînt arbori. Un ghicitor dictează la fiecare pas una din două operaţii de efectuat asupra listei şi stivei:

- shift: simbolul curent din listă este luat de acolo şi introdus în stivă ca un arbore trivial format dintr-un singur nod;

- reduce r: primele două elemente din stivă sînt scoase şi un nou element este introdus. Acesta este un arbore avînd ca nod rădăcină simbolul r şi ca fii pe cei doi arbori eliminaţi din stivă.

Programul dumneavoastră trebuie să permită simularea unui proces de acest tip, pas cu pas. Un anumit tip de ghicitor va trebui să fie generatorul de secvenţe shift-reduce, cu care proiectul dv. va trebui să se poată interfaţa. Ieşirea programului dv. – arborele realizat după consumarea simbolurilor din listă şi a şirului de operaţii, va trebui să poată fi folosit ca intrare de acelaşi program menţionat.

Indicaţii şi bibliografieDaniel Marcu (1999). A Decision-Based Approach to Rhetorical Parsing, In Proceedings of ACL 1999.

TREE2 – Generator de secvenţe shift-reduce

Nr. studenţi: 2

Se va scrie un program care, plecînd de la un arbore dat va genera şirul unic de secvenţe shift-reduce care poate duce la generarea arborelui (vezi proiectul Stiva de arbori). Ieşirea programului dv. trebuie să poată fi transmisă ca intrare proiectului stivei de arbori, după cum arborele folosit în intrare trebuie să poată fi şi unul furnizat de acelaşi proiect.

TREE3 – Interfaţă vizualăNr. studenţi: 2

Veţi scrie un program capabil a vizualiza arbori cît şi alte structuri de date (stive, cozi etc.). Această interfaţă va fi cuplată cu simulatorul de stivă din proiectul Stiva de arbori pentru a urmări desfăşurarea unei simulări.

TREE4 – Calculul expresiilor nervurăNr. studenţi: 2

Un arbore polarizat este unul în care fiecare nod este etichetat N sau S, după cum este considerat nucleu sau satelit. Nodurile frunză sînt, în plus, numerotate în ordinea de la stînga la dreapta. La orice nivel al arborelui, printre fiii unui nod părinte există cel puţin un nod nuclear. Se va scrie un program care va ataşa fiecărui nod al unui arbore binar polarizat două expresii, head şi nervură, după cum urmează.Expresia head este o secvenţă de etichete de noduri terminale, astfel:

1. expresia head a unui nod terminal este eticheta sa; 2. expresia head a unui nod neterminal este concatenarea în ordinea apariţiei lor de la

stînga la dreapta a expresiilor head ale descendenţilor săi nucleari.

Expresia nervură este secvenţă de etichete de noduri terminale, astfel

1. nervura rădăcinii este expresia sa head;2. pentru fiecare nod nuclear al cărui părinte are nervura v, expresia nervurii este:

- dacă nodul are un frate nenuclear în stînga de head h, atunci seq(mark(h), v), în care: mark() este o funcţie care marchează fiecare simbol din şirul (de exemplu, prin plasarea lui între paranteze, sau prim), iar seq(, ) este o funcţie de secvenţiere care întoarce acea permutare a concatenării simbolilor din şi dată de citirea de la stînga la dreapta a nodurilor corespunzătoare simbolilor din şi pe frontiera terminală a arborelui. Funcţia menţine marcajele asupra simbolurilor, dacă acestea există şi seq(nil, ) = ;

- altfel, v;3. pentru fiecare nod nenuclear de head h al cărui părinte are nervura v, expresia

nervurii este: - dacă nodul este descendentul stîng al părintelui său, atunci seq(h, v);- altfel, seq(h, simpl(v)), unde simpl() elimină toţi simbolii marcaţi din expresia

argumentului .

Să observăm că expresiile head se calculează de jos în sus (bottom-up) în timp ce expresiile nervură – de sus în jos (top-down).

Grupul de proiecte ROBO – îndrumător Dan Cristea

Se are în vedere proiectarea unui sistem a cărui comportare să fie similară cu activitatea unui robot capabil a se orienta în spaţiu. "Robotul" va primi o hartă (cuprinzînd planul unui etaj al unei clădiri), va fi plasat într-un anumit punct şi i se va indica un alt punct în care trebuie să ajungă. Un alt tip de activităţi vizează trasarea unor sarcini mai complexe, ca de exemplu plasarea mai multor obiecte în diverse puncte ale clădirii şi indicarea unei configuraţii finale a acestor obiecte. Robotul în acest caz va trebui să-şi planifice mişcările în vederea realizării planului, după care va trece la execuţia lui. Deplasarea robotului va fi facilitată de existenţa unui radar plasat pe robot care-l va ajuta să descopere configuraţia locurilor pe care le vizitează, pentru a le compara cu harta şi a-şi verifica astfel poziţia în plan la fiecare moment.Resursă comună iniţială dar actualizabilă:

- "harta" – reprezentînd planul clădirii.Resurse comune permanent actualizate:

- "clădirea" – o altă hartă reprezentînd situaţia reală a clădirii. Între "hartă" şi "clădire" pot exista diferenţe datorate existenţei unor obstacole (sau spargerii unor uşi);

- "poziţia" – reprezentînd poziţia reală a robotului în clădire.Cele ce urmează reprezintă o descriere sumară şi aproximativă a arhitecturii acestui sistem. Corecţii pot oricînd fi operate de voi, cu condiţia ca rezultatul să fie superior celui imaginat de mine, din cel puţin unul din următoarele puncte de vedere: mai elegant, mai general (adică permite luarea în calcul a mai multor posibilităţi de comportament ale robotului). Nu mă interesează o simplificare a arhitecturii descrise care să ducă la o execuţie mai eficientă pentru un/unele cazuri dar care să micşoreze generalitatea.Îmi imaginez acest sistem ca o arhitectură avînt următoarele module şi interacţiuni în comunicare între ele:

ochi

picioare

comparare hartă-teren

imagine virtuală

imagine reală

creierplanificator

evenimente externe

perspectivă ochi

readucerea în plan

ROBO1 – sistemul radarNumăr studenţi: 1

Se va construi un modul capabil a simula răspunsul radarului plasat pe robot, cînd robotul se găseşte în clădire într-un anumit loc şi are o anumită orientare. Simularea va avea la bază „clădirea”, care este o hartă a cărei formă va fi aproximativ egală cu cea memorată de robot („harta”). „Clădirea” va fi sursa răspunsurilor radarului la impulsurile emise – reprezentînd distanţa pînă la cel mai apropiat obstacol în direcţia "înainte" faţă de plasarea robotului. Diferenţele care pot interveni între „hartă” şi „clădire” va reprezenta diferenţa dintre plan şi realitatea la acel moment. Aceste diferenţe sînt generate de: greşeli de reprezentare pe „hartă”, obstacole ce se află la un moment dat în calea robotului, modificări în constituţia clădirii.Modulul va primi în intrare o poziţie în plan şi o direcţie şi va întoarce o distanţă (ce reprezintă răspunsul radarului la spotul de raze emis). ROBO1 va comunica cu comparatorul hartă-clădire.

ROBO2 – sistemul de comparare hartă-clădireNumăr studenţi: 2

Se va construi un modul capabil a lua decizii asupra configuraţiei terenului comparativ cu harta memorată. Intrare: harta memorată („harta”), o poziţie, o direcţie reprezentînd orientarea spre „înainte” a robotuluiIeşire: o decizie a încadrării în hartă şi a locului unde se află robotul, respectiv a apariţiei unui obstacol. Comportamentul sistemului de comparare poate fi diferit funcţie de punctul în care se află robotul faţă de un perete, sau de un obstacol aflat în cale. El trebuie să aplice euristici cară să decidă că în anumite cazuri diferenţele constatate sînt nesemnificate şi pot proveni din erori de apreciere ale radarului, ori aproximaţii ale hărţii, pe cînd în alte cazuri, cînd erorile sînt mari – ele pot provini din existenţa unor obstacole. ROBO2 va trebui să comunice cu radarul, creierul şi sistemul de readucere în plan.

ROBO3 – sistemul de generare a planuluiNumăr studenţi: 4

Se va construi un modul capabil a genera un plan de mişcare a robotului. Pentru generarea planulu pot fi luate în considerare mai multe strategii de căutare într-un spaţiu al stărilor. În acest caz fiecare membru al echipei se poate ocupa de implementarea unei strategii anume, putînd rezulta astfel un număr de module de planificare interşanjabile. Se pot folosi coduri realizate de studenţi din anii precedenţi. Intrări: punctul în clădire în care se află robotul (START) şi punctul în plan în care se doreşte el a ajunge (FINIŞ).Ieşiri: un plan, reprezentînd un şir de mişcări ce trebuiesc executate pentru deplasarea de la START la FINIŞ.

Resurse: „harta” actualizată de creier.Planificatorul comunică cu creierul şi cu sistemul de readucere în plan. Informaţii la Amalia Todiraşcu.

ROBO4 – sistemul de readucere în planNumăr studenţi: 2

În cazul unui incident, care aici ar putea consta în apariţia neaşteptată a unui obstacol pe traseu, robotul ar trebui să fie capabil să plaseze din nou în plan starea curentă sau, în cazuri extreme, să recalculeze planul. Modulul trebuie deci să implementeze diagrama triangulară (v. cursul) pe care să decidă dacă noua stare se găseşte în planul vechi şi deci se sare în acea stare a vechiului plan, sau nu exista în planul vechi, caz în care va apela la planificator pentru calcularea unu nou plan. Comunicaţii: cu planificatorul şi comparatorul hartă-teren, de unde trebuie să primească informaţii despre obstacole.

ROBO5 – sistemul mecanicNumăr studenţi: 1

Acest modul simulează sistemul de înaintare şi de rotire al robotului. În principiu, robotul înaintează astfel: ştie că se află într-un anumit punct şi trebuie să execute o mişcare pe o distanţă dată într-o anumită direcţie, sau să execute o rotire de un anumit unghi. Ca urmare el va face un număr de paşi în acea direcţie sau va executa o rotire. Sistemul mecanic este cel care "propulsează" robotul spre înainte cu un pas. Acest lucru se va manifesta printr-o actualizare a poziţiei reale a robotului în "clădire" – dacă comanda a fost de mişcare înainte, sau a orientării sale – dacă comanda a fost de rotire cu un anumit unghi. Comunicaţii: cu creierul, cu sistemul de vizualizare pe hartă şi cu sistemul de vizualizare a ceea ce vede robotul.

ROBO6 – sistemul de vizualizare a perspectivei de „deasupra”Număr studenţi: 2

Modului va plasa într-o fereastră "clădirea" şi poziţia robotului în ea, dintr-o perspectivă de "deasupra". Aceasta reprezintă situaţia REALĂ.O altă fereastră, în aceeaşi perspectivă va figura "harta" şi poziţia robotului pe hartă. Aceasta reprezintă situaţia IMAGINATĂ de robot, proiecţia în mintea robotului a realităţii şi plasarea lui într-însa.În marea parte cele două configuraţii trebuie să coincidă, dar din compararea celor două imagini un observator ar trebui să înţeleagă motivele pentru care robotul se înşeală în anumite cazuri, prin luarea unor decizii greşite, sau măsura în care imaginea sa asupra realităţii diferă de cea reală.Odată cu deplasarea sau rotirea robotului această imagine se va schimba corespunzător. Comunicări: cu creierul pentru proiectarea viziunii imaginare, cu sistemul de mişcare şi generatorul de evenimente externe pentru actualizarea imaginii reale.

ROBO7 – sistemul de vizualizare din perspectiva ochilor robotuluiNumăr studenţi: 2

Modului va plasa într-o fereastră ceea ce "vede" robotul prin intermediul radarului său într-un unghi de G (parametru) grade stînga şi dreapta faţă de direcţia "înainte". Odată cu deplasarea sau rotirea robotului această imagine se va schimba corespunzător. Comunicare: cu radarul, posibil şi cu creierul.

ROBO8 – creierulNumăr studenţi: 4

"Creierul" este sistemul care integrează informaţiile primite de la diversele module pe care le are la dispoziţie. El ştie că se poate baza pe următoarele module:

- ROBO2 : comparatorul hartă/teren – care îi confirmă sau infirmă plasarea într-un anumit punct, cît şi existenţa unor obstacole (sau modificări ale configuraţiei clădirii). Acest sistem obţine deciziile prin folosirea lui ROBO1: ochi – sistemul radar;

- ROBO3 : un generator de plan (în realitate tot o parte a creierului, pe care preferăm să o vedem ca o componentă separată a sistemului);

- ROBO5 : picioare – sistemul mecanic care propulsează robotul înainte un pas, sau îl roteşte într-o parte cu un anumit unghi.

Dacă la un anumit moment în faţa robotului apare un obstacol, acesta trebuie să fie capabil a-l ocoli. Ca urmare "creierul" va afla de la ROBO2 că în faţă are un obstacol şi va intra într-o fază de scanare a terenului pentru a afla forma obstacolului. Cînd realizează că are suficientă informaţie asupra formei şi plasamentului obstacolului în hartă, va plasa obstacolul pe hartă şi va apela ROBO3 pentru o actualizare a planului. "Creierul" trebuie gîndit ca un fel de rege care acţionează legat la ochi. El cere şi obţine de la sclavii săi orice informaţie de care are nevoie, comandă anumite sarcini şi aşteaptă rezultatul execuţiei lor, pentru ca pe baza corelării tuturor acestor informaţii să hotărască ce va face la fiecare moment în vederea realizării planului primordial. În anumite situaţii "creierul" poate decide abandonarea temporară a planului curent pentru realizarea unui plan auxiliar, care să ajute realizării planului major. De exemplu, robotul poate intra într-un subplan de "scanare" a unui obstacol, pe care apoi să-l plaseze pe hartă. "Creierul" actualizează cu informaţii "imaginea virtuală" afişată de ROBO6. El nu poate şi nu trebuie să cunoască "imaginea reală". Plasarea în realitate este o consecinţă a interacţiunilor mecanice ale robotului cu lumea, iar acestea reprezintă un rezultat al reprezentării lumii în mintea sa.

ROBO9 – sistemul de generare a evenimentelor externeNumăr studenţi: 2

Utilizatorul trebuie să poată interveni în planul „clădirii” pentru a face modificări, constînd din plasarea de obstacole, sau deschiderea unor uşi. Modificările se fac interactiv în fereastra care prezintă situaţia din teren în perspectiva de deasupra. Comunicări: cu modulul de afişare a perspectivei de deasupra (în fereastra situaţiei REALE).

Grupul de proiecte JOCURI – îndrumător Amalia Todiraşcu

Proiectele din acest grup vor utiliza algoritmul minimax sau alfa-beta. Sursele LISP vor fi disponibile aici. Pentru fiecare proiect din acest grup, trebuie definite :

- stările problemei (starea iniţială şi starea finală);- funcţia de evaluare ;- eventual se va colabora cu autorul proiectului Alfa-beta probabilist.De asemenea, se va realiza interfaţa grafică, care să permită utilizatorului să joace cu calculatorul.

JOC1 - Turn-a-blockNr. studenţi : 1

Să se scrie un program care să joace Turn-a-block cu calculatorul (se vor respecta indicaţiile de la începutul secţiunii). Pe o tabla nxn (n=3..8) sînt plasate în fiecare poziţie piese albe şi negre. Ficare jucător poate selecta o zonă dreptunghiulară (unul sau mai multe pătrate), şi în zona selectată piesele îşi schimbă culoarea.

Jucătorul care reuşeşte să obţină toate piesele albe pe toată tabla cîştigă. O interfaţă grafică va prezenta evoluţia jocului.

Indicaţii despre joc: http://www.righto.com/java/turnablock.html

Stare iniţială

Zona selectată

Rezultatul obţinut după selecţie

JOC2 - Stop-Gate

Nr. studenţi: 1

Să se scrie un program care să joace Stop-Gate cu calculatorul (se vor respecta indicaţiile de la începutul secţiunii). Pe o tablă de şah 8x8 se vor folosi piese de domino, plasate pe două pătrate alăturate. Ele nu pot fi plasate în diagonală.

Primul jucător va alege una din cele doua direcţii acceptate, iar celălalt jucător va plasa toate piesele orientate invers. Pierde jucătorul care nu mai are loc pe tablă. O interfaţă grafică prezintă evoluţia jocului.

Indicaţii despre joc: http://www.cs.uidaho.edu/~casey931/conway/stopg.html

JOC3 - 4-in-linie

Studenţi: 1

Să se scrie un program (se vor respecta indicaţiile de la începutul secţiunii) care să joace o versiune modificată a jocului tic-tac-toe. Pe o tablă nxn, se vor utiliza doua feluri de piese. Diferenţa faţă de jocul clasic este că fiecare jucator încearcă să plaseze piesa pe una din coloane, dar piesa va fi plasată automat pe prima linie pentru care celula corespunzătoare coloanei este liberă. Scopul jocului este de a obţine 4 piese de acelaşi tip pe linie, pe coloane sau pe diagonală.

O interfaţă grafică prezintă evoluţia jocului.

JOC4 -Neutron

Nr. studenţi: 1

Să se scrie un program (se vor respecta indicaţiile de la începutul secţiunii) care să joace Neutron cu calculatorul. Pe o tablă 5x5 fiecare jucător plasează piesele în linie, iar neutronul este în mijloc. Toate piesele rămîn în joc. Fiecare piesă poate fi mutată pe linie, pe coloana sau în diagonală în limita spaţiului disponibil. Fiecare jucător mută mai intîi neutronul şi apoi piesa. Strategia pe care o aplică fiecare jucător este de a-l împiedica pe adversar să mute neutronul.Scopul jocului este ca neutronul să ajunga în cîmpul său.

{} - neutronulX - piesele unui jucatorO - piesele celuilalt jucator

O interfaţă grafică prezintă evoluţia jocului.

Jucătorul încearcă să plaseze piesa în coloana 3

piesa va fi plasată pe prima linie liberă

--------------------------------! O ! O ! O ! O ! O !--------------------------------! ! ! ! ! !--------------------------------! ! ! {} ! ! !--------------------------------! ! ! ! ! !--------------------------------! X ! X ! X ! X ! X !--------------------------------

JOC5 - All King's horses

Nr. studenţi: 1

Să se scrie un program (se vor respecta indicaţiile de la începutul secţiunii) care joacă All King's horses cu calculatorul. Jocul foloseşte o tablă de şah obişnuită şi un număr de piese de acelaşi fel care vor fi caii. Un pătrat poate conţine două piese. Cele 4 pătrate din colţul stînga sus al tablei joacă rol de grajd. Scopul jocului este de a plasa toţi caii în grajd. Jucătorul care pune ultimul cal în hambar pierde.Piesele se pot muta în felul următor:- întotdeauna direcţia este spre grajd;- mutările posibile sînt cele posibile calului.O interfaţă grafică prezintă evoluţia jocului.

Indicaţii despre joc: http://www.cs.uidaho.edu/~casey931/conway/horse.html

JOC6 - Monede

Nr. studenţi: 1

Să se scrie un program (se vor respecta indicaţiile de la începutul secţiunii) care joacă următorul joc cu calculatorul. Se grupează o serie de monede ca în figură:

--------------------------------------------------------------------------------------0 0000 00 000 0 0 0--------------------------------------------------------------------------------------Un exemplu de stare a problemei.

Fiecare jucător poate înlatura un grup format dintr-o singură monedă sau poate înlatura o singură piesă dintr-un grup astfel încît să se formeze două alte grupuri mai mici. Jocul se termină cînd un jucător înlătură ultimul grup şi în acest caz jucătorul pierde.

O interfaţă grafică prezintă evoluţia jocului.

Indicaţii despre joc: http://www.cs.uidaho.edu/~casey931/conway/kayles.html

JOC7 - Alfa-beta probabilist

Nr. studenţi:2

Să se implementeze variante ale algoritmului minimax şi alfa-beta astfel încît acesta să se poată aplica unor jocuri în care intervine parţial şansa. Un exemplu de aplicaţie al acestui algoritm este jocul de table.

Indicaţie : capitolele corespunzătoare din cărţile « Artificial Intelligence » - E.Knight şi « Artificial Intelligence – A Modern Approach» - S.Russell şi P.Norvig

Grupul de proiecte : Algoritmi de căutare în spaţiul stărilor SEARCH – îndrumător Amalia Todiraşcu

Aceste proiecte folosesc un set de algoritmi de căutare descrişi în LISP. Se cere să se descrie :

- stările problemei ;- regulile care se aplică pentru a trece dintr-o stare în alta.

SEARCH1 - Teste de inteligenţă (Russell&Norvig95)

Nr. studenţi: 2

Testele de inteligenţă conţin adesea probleme de predicţie a secvenţelor. In acest tip de probleme trebuie să se prezică care este numărul următor al secvenţei, presupunînd că numărul aflat pe poziţia n este generat prin aplicarea unei funcţii secvenţă s(n), unde primul element al secvenţei corespunde lui n=0. De exemplu funcţia s(n)=2n generează secvenţa [1,2,4,8,16...].Să se implementeze un sistem capabil să rezolve acest tip de probleme. Sistemul va căuta în spaţiul funcţiilor posibile pînă cînd se găseşte una care să se potrivească. Spaţiul funcţiilor posibile va fi alcătuit din toate expresiile posibile formate cu operatorii +,/,* şi exponenţi şi numerele de la 1 la n. Să se adapteze unul dintre algoritmii de căutare descrişi la curs (vezi indicaţiile de la începutul secţiunii Search).

SEARCH2 - Studentul întîrzîiat

Nr. studenţi: 1

Un student oarecare de la o universitate A are probleme şcolare din cauză că ajunge mereu în întîrzîiere la cursuri. El trebuie să treacă în fiecare zi prin diferite puncte ale campusului: la asociaţia studenţească, la laboratorul de informatică, la sala de sport, la cantină pentru masa de prînz, la bibliotecă (pentru a citi articole), pe terenul de tenis, în dormitor pentru a mînca seara. Să se scrie un program care calculează drumul ce trebuie parcurs astfel încît distanţa pe care o parcurge studentul să fie minimă (vezi indicaţiile de la începutul secţiunii Search).

SEARCH3 - Probleme de satisfacere a restricţiilor

Nr. studenţi: 2

Să se implementeze un algoritm care să permită rezolvarea unor probleme de propagare a restricţiilor. Să se aduca îmbunătăţiri algoritmului de backtracking obişnuit pentru a se aplica într-o astfel de problemă particulară (verificarea nodurilor care pot fi expandate, propagarea restricţiilor). Un exemplu pentru testarea acestui proiect este problema celor 8 regine.

Indicaţie: să se studieze capitolul corespunzator din Rich&Knight sau din Russell&Norvig

SEARCH4 - Counselor

Nr. studenţi:2

Folosind algoritmul general de propagare a restricţiilor, să se implementeze un modul counselor care ajută studenţii din primul an să îşi aleagă cursurile opţionale pentru cei 4 ani de studiu. Fiecare student trebuie să-şi stabilească ce cursuri îşi alege pentru fiecare semestru. Variabilele sînt reprezentate de fiecare curs, iar domeniul fiecărei variabile va fi reprezentat de semestrele în care este posibil să fie programate, iar restricţiile sînt următoarele:- cerinţele fiecărui curs (ce cursuri trebuie urmate în prealabil);- suprapunerile de cursuri;- numărul total de ore pe semestru.

Indicaţie: sa se studieze capitolul corespunzator din Rich&Knight sau din Russell&Norvig

SEARCH5 - OrarNr. studenţi: 4

Folosind algoritmul general de propagare a restricţiilor, să se implementeze un program care propune un orar al facultăţii. Restricţiile care se aplică în acest caz sînt:- restricţii de săli (laboratoarele vor fi programate în săli echipate cu calculatoare);- restricţii de timp (anumiţi profesori nu vor fi disponibili la anumite ore, trebuie

prevăzută o pauză de prînz etc.).

Grupul de proiecte : Sisteme de reguli RULES – îndrumător Amalia Todiraşcu

RULES1 - Problema lanţurilor(Russell&Norvig95)

Nr studenţi: 1

O serie de lanţuri de diferite lungimi trebuie reconfigurate pentru a obţine noi aranjamente. Operaţiile care pot schimba o stare pot înlătura o za sau pot adăuga o za. In starea iniţială avem 4 siruri, fiecare din acestea fiind formate din 3 zale. Starea finală constă dintr-un singur lanţ format din 12 zale.

Stare iniţială Stare finală

Indicaţie: se va implementa un algoritm de căutare în spaţiul stărilor (vezi sectiunea Search)

RULES2 - Mangusta, şarpele şi şoricelulNr. studenţi: 1

Vă aflaţi într-un campus universitar şi sînteţi obligat să luaţi autobuzul pînă în oraş. Sînteţi însoţit de animalele preferate: o mangustă, un şarpe de casă şi un şoricel. Regulamentul campusului interzice să luaţi autobuzul fiind însoţit de mai mult de un animal. In absenţa Dvs., mangusta va mînca şarpele, sau şarpele va mînca şoricelul. Scopul este să ajungeţi în oraş împreună cu toate animalele favorite. Să se formalizeze această problema ca un sistem de reguli şi să se simuleze pas cu pas (interfaţa grafică) aplicarea algoritmului de căutare în spaţiul stărilor.

Indicaţie: se va folosi unul din algoritmii de căutare disponibili (vezi sectiunea Search).

RULES3 - Ceaiul indian

Nr. studenţi : 1

In ceremonia ceaiului la hinduşi participă un copil un servitor şi un bătrîn. Cele 4 task-uri care trebuiesc îndeplinite sunt : alimentarea focului, servirea prăjiturilor, strecurarea ceaiului şi citirea poeziilor (în ordinea importanţei acestora). La începutul ceremoniei, copilul realizează toate task-urile. El le transferă pe rînd servitorului şi bătrînului astfel că la sfîrşitul ceremoniei bătrînul le va face pe toate. Task-urile se transferă una cîte una şi nimeni nu poate face un task mai puţin important decît cel pe care le are în sarcină. Să se descrie această problemă cu ajutorul sistemelor de reguli, folosind unul din algoritmii de căutare cunoscuţi (vezi sectiunea Search)..

RULES4 - Rolling Cubes

Nr studenţi: 1

Să se scrie un program care să caute soluţii, aplicînd algoritmi de căutare în spaţiul stărilor (vezi secţiunea Search) pentru jocul Rolling Cubes. Rolling Cubes este o versiune tridimensionala a jocului 8-puzzle. Pe o tablă 3x3 sînt plasate 8 piese, fiecare piesă este un cub vopsit pe jumătate în negru şi pe jumătate în alb ca în figura:

Starea iniţială este:

Starea finală este:

O stare intermediară:

O interfaţă grafică prezintă evoluţia jocului.

Indicaţii despre joc: http://www.righto.com/java/rollingcubes.html

RULE5 – Cuvinte gresite

Nr. Studenti: 1

Sa se scrie un program care corecteaza erorile ortografice aparute intr-un cuvint. Problema se va modela cu ajutorul sistemelor de reguli, o stare a sistemului este un cuvint, starea finala este un cuvint care se gaseste intr-un dictionar, iar regulile de transformare sunt urmatoarele: inserarea unei litere, inlocuirea unei litere cu o alta, stergerea unei litere, inversarea a doua litere. Se vor folosi algoritmii de cautare de la SEARCH.

Grupul de proiecte Planificare PLAN – îndrumător Amalia Todiraşcu

PLAN1 - Rubik

Nr. studenţi: 2

Să se implementeze reguli STRIPS aplicate cubului Rubik. Acest proiect se va rezolva in legatura cu proiectele ROBO – generarea planului, readucerea în plan după incident, etc. Să se realizeze o interfaţă grafică care să permită urmărirea desfăşurării jocului.

PLAN2 - Ierarhii de planuri

Nr. studenţi: 4

Să se modifice algoritmii de generare a planului şi de readucere în plan după incident în următoarele ipoteze suplimentare:a) regulile au asociate probabilităţi;b) formalismul STRIPS permite folosirea unor operatori speciali pentru înlocuirea unei

secvenţe de acţiuni prea lungi cu operatorul dat. Pe lîngă regulile date, sistemul poate consulta o bibliotecă de astfel de operatori.Exemplu: move_car(X,Y) = open_car(X,W,Z), get_in_car(W,Z), start_engine(W,Z), drive(W,Z,Y).

Să se implementeze un algoritm de creare a unei ierarhii de astfel de operatori, fiind dată o mulţime de perechi <stare_initiala, stare_finala>.

Grupul de proiecte : Limbaj natural LN – îndrumător Amalia Todiraşcu

LN1 - Interfaţă în limbaj natural

Nr. studenţi: 4

Să se creeze o interfaţă în limbaj natural care să permita utilizatorului să descrie planuri scurte în limbaj natural pentru lumea blocurilor: "mută blocul A peste blocul C", "mută blocul B pe masă". Se va defini un sub-limbaj care să aiba drept corespondent o regulă din lumea blocurilor. Analiza comenzii se face avînd la dispoziţie un mic dicţionar de corespondenţe <cuvînt, regulă/obiect> şi o colecţie de pattern-uri posibile. Se va obţine o descriere în lumea blocurilor a comenzii respective. Se va aplica regula respectivă şi se urmăresc efectele acesteia pentru starea dată (interfaţa grafică).

Problema se va rezolva în colaborare cu echipele care implementează algoritmul de generare a planului si reducere după un incident din grupul de proiecte ROBO. De asemenea, algoritmul de pattern-matching este disponibil.

LN2 - TRIE

Numar studenţi: 2

Se dă o colecţie de pattern-uri (pattern-urile conţin fie cuvinte, fie categorii lexicale, fie variabile).Exemple de pattern-uri:

(pe ?x <verb>)

unde ?x este o variabilă (poate fi înlocuit cu orice cuvînt sau categorie lexicală). Variabilele încep cu semnul întrebării. <verb> este o categorie lexicală (partea de vorbire a cuvîntului)

Pattern-urile vor fi asociate cu un şir (secvenţă de cuvinte sau categorii lexicale). Ele vor fi identificate într-un şir de intrare, iar secvenţa de entităţi din text care corespunde pattern-ului va fi înlocuită cu şirul asociat pattern-ului.Să se construiască o structură TRIE pentru reprezentarea mulţimii de pattern-uri (structura va fi folosită de proiectul LN3). O structură TRIE permite păstrarea în mod eficient a pattern-urilor disponibile. TRIE are nodul rădăcină etichetat cu şirul vid. Cînd se adaugă un nou pattern în arbore se caută dacă următorul element al pattern-ului există în structură ca nod fiu al nodului curent (şi dacă există nu se mai adaugă în arbore, ci se trece la următorul element din pattern). În plus, se defineşte o funcţie eşec, care corespunde situaţiei în care o secvenţă

de elemente componente ale pattern-ului pot fi identificate într-un şir de intrare şi s-a obţinut o eroare. Funcţia eşec se poate calcula în momentul în care se adaugă pattern-uri noi în structură astfel:

- se caută dacă elementul urmator al pattern-ului este nod fiu al nodului curent;- se caută dacă restul pattern-ului există deja în structură.

Exemplu: Avem un pattern (a b d) si (b c). In sirul de intrare avem “babce”. Primul pattern nu coincide cu sirul de intrare. In schimb, am identificat elementul b si putem continua cautarea din nodul b (si vom constata ca pattern-ul (b c) se potriveste peste sirul de intrare).

Pattern-urile (a b c)/A1 si (b c)/A2 se reprezintă ca în figura:

LN3 - Identificare pattern-matching

Nr. studenţi : 2

Folosind o colecţie de pattern-uri (în reprezentarea propusă la proiectul LN2 - TRIE), să se scrie un program care să înlocuiască toate şirurile de entităţi care se potriveşte pattern-urilor cu şirul asociat fiecărui pattern. Intrarea acestui program va fi un text adnotat cu categorii lexicale (textul de intrare şi colecţia de pattern-uri vor fi obţinute, în română şi franceză de la Amalia Todiraşcu). Se va folosi un algoritm de pattern matching disponibil aici.

Exemplu. Pattern-ul (?x/<substantiv> ?y/<adjectiv>) are asociat şirul [?x ?y]/<grup_nominativ>. Secvenţa din text care se potriveşte cu pattern-ul se înlocuieşte cu textul asociat:

« Calul/<substantiv> alb/<adjectiv> aleargă/<verb> pe dealul/<substantiv> verde/<adjectiv>» se transformă « [calul alb]/<grup_nominativ> aleargă/<verb> [dealul verde]/<grup_nominativ>»

LN4 - Trigger words

Nr. studenţi : 2 Se consideră o listă de cuvinte trigger care au asociate o serie de reguli de forma (pattern, acţiune), precum şi o probabilitate de aplicare a regulii. Un cuvînt trigger face parte din pattern-ul asociat. Un pattern conţine cuvinte, variabile şi fiecare cuvînt sau variabilă poate fi marcat cu informaţie lexicală şi cu informaţie semantică. Pattern-urile sunt formate din cuvinte, variabile şi marcheri lexicali şi semantici. Fiecare pattern are asociat un şir de cuvinte, marcheri şi funcţii.

Exemplu. Pattern: (?x/<substantiv>/<concept1> ?y/<adjectiv>/<concept2>)

aaa

a aaa

b

aaa

c

aaa

Functia esec

Acţiune: [?x ?y]/combine(<concept1>, <concept2>)

combine(<concept1>, <concept2>) este o funcţie care trebuie evaluată

Marcheri lexicali: <substantiv>, <adjectiv>

Marcheri semantici: <concept1>, <concept2>

Acţiunea asociată acestui pattern este acţiunea de marca o secvenţă de cuvinte cu combinaţia rezultată prin gruparea marcherilor (lexicali sau semantici) ale părţilor componente.

Programul primeşte la intrare un set de tuple de forma <trigger_word, probabilitate, (pattern, acţiune)> şi un text adnotat cu marcheri lexicali şi semantici. Un trigger_word este fie un cuvînt, fie un marcher lexical sau semantic.

Cînd un trigger_word_ex a fost identificat în text, atunci se extrage din mulţimea de tuple o listă de tuple <trigger_word_ex, _,_,_>, ordonată după probabilitate. Pentru fiecare trigger_word_ex identificat în textul de intrare, se caută în vecinătatea lui o secvenţă care se potriveşte cu pattern-ul dat. Dacă s-a identificat un pattern, atunci se efectuează acţiunea corespunzătoare (evaluînd funcţiile din acţiune).

Exemplu. Se identifică trigger_word = <prepoziţie>.

Un tuplu asociat este (<prepozitie>, 0.69, (?x/<substantiv>/?concept1 ?y/<prepozitie> ?z/<adjectiv>/?concept2),

[?x ?y ?z]/combine(?concept1, ?concept2))

Şirul de intrare este

Piticul/<substantiv>/<PITIC> din/<prepoziţie> grădină/<adjectiv>/<GRADINA> ?x = Piticul?concept1 = <PITIC>?y = din?z = grădină?concept2 = <GRADINA>

Rezultatul evaluării funcţiei combine(<PITIC>, <GRADINA>) = (<PITIC> hasPlace <GRADINA>)

Rezultatul acţiunii este adnotarea textului cu

[Piticul din grădină]/(<PITIC> hasPlace <GRADINA>)

LN5 - Extragerea unei ierarhii de concepte

Nr. Studenţi : 2

Se consideră texte în format XML (Extended Markup Language). XML permite definirea de marcaje utilizator pentru structurarea anumitor porţiuni din document. Definiţiile sunt date într-un fişier separat DTD (Document Type Definiton). Fiecare document XML poate folosi unul sau mai multe fişiere DTD. Se pot defini marcaje pentru identificarea conceptelor din text.

Un exemplu de marcaje din DTD:

< !ATTLIST tag attribute type definition >

<!ENTITY top>< !ATTLIST person name CDATA inherited CDATA>

Tag-ul person are două atribute: name şi inherited. Top este o entitate.

Corespunzător acestei definiţii în fişierul XML vom întîlni marcaje:

<doctor name=”popescu” job=”doctor” inherited=”person”> dr. Ion Popescu</doctor>

Exemple de fişiere XML şi DTD le veţi cere la Amalia Todiraşcu.

Să se scrie un modul care învaţă o ierarhie de concepte şi instanţele acestora plecînd de la un document XML adnotat. Modulul primeşte la intrare un text în format XML adnotat cu tag-uri definite de utilizator care marchează în text instanţe ale unor concepte.

Din exemplul de mai sus, algoritmul învaţă că <doctor> este un concept derivat din <person>, avînd un atribut suplimentar <job> cu valoarea “doctor”.

LN6 - Un sistem de filtrare a mesajelor

Nr. Studenţi:2

Să se implementeze un algoritm de învăţare care va fi destinat achiziţiei de cunoştinţe în vederea filtrării mesajelor electronice. Mesajele electronice sunt caracterizate de autor, subiect, adresa electronică. Subiectul va fi format din cuvinte cheie. Algoritmul va primi un set de exemple pozitive şi negative şi va putea extrage o mulţime de caracteristici care să îi permită să filtreze mesajele noi: cele care se încadrează în categoria mesajelor negative vor fi aruncate la coş.

Indicaţii: algoritmi de învăţare supervizată Russell&Norvig, Luger & Stubblefield