Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# Problem S. 11. (October 2005)

S. 11. We often categorize things according to various properties and look for relations among them. Write a program to make logical deductions among properties.

The program should read the input from the keyboard (or standard input): each line will contain a proposition or a question. The program should answer them in the next line on the screen (or standard output).

Propositions or questions refer to various properties. An elementary property consists of a single word, e.g., small or red. Every word is considered as an elementary property, except for the following ones: NOT EXIST, EXIST, AND, OR, NOT, IF and THEN.

Negation of an elementary property is formed by attaching the prefix NOT, e.g., the negation of red is NOT RED.

Compound properties are formed by joining some elementary properties or negations of elementary properties using the words AND or OR, e.g., small AND NOT red. However, mixing these conjunctive words, as in big AND red OR blue, is not allowed.

Three types of propositions are allowed with the following syntax:

EXIST (property)

NOT EXIST (property)

IF (property) THEN (property)

A question is formed by putting a question mark at the end of a proposition.

The program should give any of the following answers to a given proposition:

UNDERSTOOD if the proposition corresponds to a new piece of information

I KNOW if the proposition is a consequence of earlier ones

CONTRADICTION (the program should ignore these propositions)

I DO NOT UNDERSTAND if the input is syntactically incorrect

The program should reply to a question with

YES, or NOT EXIST if the question referred to a true proposition

NO, or BUT EXIST if the question referred to a false proposition

I DO NOT KNOW if the answer might be true or false

The program runs until the user aborts it. You may assume that the number of elementary properties is at most 8 and the input consists of at most lines. Upper and lower case letters should be considered equal. Every character which is not a letter or question mark should be considered as space''.

Example (answers of the computer are in italics):

 IF dog OR cat OR horse THEN hairy AND fourlegged UNDERSTOOD IF dachshund OR foxterrier THEN dog UNDERSTOOD IF foxterrier THEN fourlegged I KNOW IF mosquito THEN sixlegged UNDERSTOOD IF dachshund THEN hairy? YES EXIST dachshund? I DO NOT KNOW EXIST dachshund UNDERSTOOD NOT EXIST hairy AND dog? BUT EXIST IF fourlegged THEN NOT sixlegged UNDERSTOOD EXIST horse AND mosquito? NOT EXIST NOT EXIST sixlegged AND dachshund? NO EXIST fourlegged OR sixlegged AND NOT hairy? I DO NOT UNDERSTAND

The source code (s11.pas, s11.c, ...) of the program should be submitted.

(10 pont)

Deadline expired on November 15, 2005.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Először is megjegyezzük, hogy a feladatbeli példában kilencféle elemi tulajdonság szerepel. A rugalmasság kedvéért a programunkat úgy valósítjuk meg, hogy az elemi tulajdonságok maximális számát egy makróban definiáljuk.

A program működési elve

A programban 10-féle elemi tulajdonságot engedünk meg. Egy tetszőleges dologra, objektumra mindegyik tulajdonság vagy teljesül, vagy pedig nem teljesül; ebből a szempontból egy objektum legfeljebb 210=1024-féle lehet. Ezért definiálunk 1024-féle tulajdonság atomot, amelyek megfelelnek az elemi tulajdonságok részhalmazainak. Minden elemi és összetett tulajdonságot az atomok egy részhalmazaként képzelünk el. A részhalmazban szereplő elemi tulajdonságok igazak az adott atomra, a részhalmazon kívüli elemi tulajdonságok pedig nem teljesülnek rá.

A HA-AKKOR és a NINCS alakú állítások bizonyos atomokról azt állítják, hogy olyan tulajdonságú dolog nincs. Ezek az állítások tehát a lehetséges atomok halmazát szűkítik; az ilyen állításokat szűkítésnek fogjuk nevezni. A LÉTEZIK állítások pedig atomok halmazairól állítják, hogy legalább az egyikük létezik. Ezek az egzisztencia állítások.

A program tárolja a lehetséges atomok halmazát, és ezt minden egyes elfogadott szűkítéskor módosítja. Azokat a nem üres halmazokat pedig, amelyekről valamelyik LÉTEZIK állításból tudjuk, hogy nem lehetnek üresek, külön-külön eltároljuk. Szűkítéskor a nem üres halmazokból is töröljük a meg nem engedett elemeket.

A szűkítések ellenőrzése két részből áll. A szűkítés mindig azt állítja, hogy atomok csak egy bizonyos A halmazban lehetnek. Ha az A halmaz diszjunkt valamelyik nem üres B halmazzal, az ellentmondás. Az ilyen szűkítés nem megengedett, illetve kérdés esetén a válasz NEM. Az ellenőrzés második részeként ellenőrizzük a megengedett atomok M halmazát. Ha MA, akkor a szűkítés nem jelent új információt; a válasz IGEN, illetve TUDOM. Ha a szűkítés új információt jelent, akkor M-et és az összes nem üres halmazt elmetsszük A-val.

Az egzisztencia állítások ellenőrzése szintén két részből áll. Egy egzisztencia állítás azt mondja, hogy egy bizonyos A halmaz nem üres. Ha A diszjunkt a megengedett atomok halmazával, akkor ez ellentmondás. Ha pedig valamelyik korábbi nem üres halmaz részhalmaza A-nak, akkor az információ nem új.

A program felépítése

A példaprogramot C++-ban írtuk, és Linux alatt, GCC 3.3.3 fordítóval fordítottuk.

A program elején az ETN makróban definiáltuk az elemi tulajdonságok maximális számát, az ATN makróban pedig az atomokét.

Az atomokat megszámozzuk 0-tól 1023-ig. A tulajdonságokat egészekből álló halmazokkal reprezentáljuk:

typedef std::set<int> Tulajdonsag;

Az uresHalmaz és a teljesHalmaz változókat a részletszámolásoknál használjuk; az egyik halmaz üres, a másik a teljes {0,1,2,...,1023} halmaz.

A tulajdonságok legfontosabb műveleteit és relációit a * (metszet), + (unió), - (különbség, illetve komplementer), << és >> (részhalmaz) operátorok valósítják meg.

Az elemi tulajdonságokat is kódolnunk kell. A tulajdonsagKod függvény egy tulajdonságnevet alakít számmá; a visszaadott számok a 2-hatványok (1,2,4,8,...). Az elemiTulajdonsag függvény pedig tulajdonságnevet tulajdonsággá konvertál; a visszadott halmaz azokat az atomokat tartalmazza, amelyek sorszáma tartalmazza a tulajdonságkódnak megfelelő bitet, pl. a 2 kódú tulajdonsághoz tartozó halmaz: {2,3,6,7,10,11,...}

A lehetsegesHalmaz változó tartalmazza azokat az atomokat, amelyeket egyik szűkítés sem zárt még ki; értéke kezdetben a teljes halmaz. A nemUresHalmazok vektorban pedig azokat a halmazokat soroljuk fel, amelyek valamelyik egzisztencia állítás alapján nem lehetnek üresek.

A SzukitesEllenorzes ellenőrzi, hogy egy szűkítő állítás a korábbiak alapján igaz, hamis vagy új információ. A függvény paramétere azon atomok halmaza, amiket az állítás megenged. A SzukitesBejegyzes az új szűkítő információ bejegyzésére szolgál; az új megengedett halmazzal elmetszi a lehetsegesHalmaz-t és a nemUresHalmazok mindegyik elemét.

A Nincs és a HaAkkor függvények értelemszerűen a NINCS, illetve HA-AKKOR alakú állításokat és kérdéseket dolgozzák fel. Mindkét függvényben a kerdes argumentum mondja meg, hogy új állításról, vagy csak kérdésről van szó. Mindkét program meghívja a SzukitesEllenorzes függvényt, szükség esetén a Szukitesbejegyzes-t, és kiírja a képernyőre a választ.

Hasonlóan, az EgzisztenciaEllenorzes, EgzisztenciaBejegyzes és Letezik függvények dolgozzák fel a LETEZIK állátásokat és kérdéseket.

Az állítások és kérdések interpretációját további részekre bontottuk. A programban nem használtunk kivételeket (excpetionöket); helyette a voltHiba változóban jelezzük, ha az interpretáció nem sikerült.

Az osszetettTulajdonsag függvény szavak egy sorozatát alakítja atomok halmazává. A szavakat a szavak vektorban kapjuk, az átalakítandó tartomány első és utolsó elemének indexe elso, illetvet utso. Ez a függvény kezeli a NEM, az ÉS és a VAGY relációkat.

A SzavakraTordeles függvény egy stringet bont szavakra. A kérdőjel önálló szó.

Végül az EgySorFeldolgozasa függvény egy stringet szavakra bont, megvizsgálja az első szót és hogy az utolsó szó kérdőjel-e, és meghívja a HaAkkor, Nincs vagy a Letezik függvényt.

A sorok beolvasása végtelen ciklusban a main függvényben történik.

 // S. 10.// Mekk Elek 11. o. t.// Nekeresd, Ezermesterképző Intézet// kaposzta@nekeresd.hu// Ezt a programot Linux alatt, GCC 3.3.3 fordítóval teszteltük.// --------------------------------------------------------------------#include #include #include #include #include #define ETN 10        // Az elemi tulajdonságok maximális száma#define ATN (1 << 10) // Az atomi tulajdonságok max. száma// ====================================================================// Összetett tulajdonságok kezelése. Az összetett tulajdonságok// tulajdonságatomok halmazai. Az atomokat megszámozzuk, az összetett// tulajdonságokat reprezentáló "Tulajdonsag" tipus ezért egészek egy// halmaza lesz.typedef std::set Tulajdonsag;Tulajdonsag uresHalmaz;Tulajdonsag teljesHalmaz;     // Az összes atom halmaza. Értéket a main-ben kap// --------------------------------------------------------------------// VAGY művelet -- két tulajdonsághalmaz uniójaTulajdonsag operator + ( const Tulajdonsag &A, const Tulajdonsag &B ){  Tulajdonsag C;  std::set_union( A.begin(), A.end(), B.begin(), B.end(),                  std::inserter( C, C.begin() ));  return C;}// --------------------------------------------------------------------// ÉS művelet -- két tulajdonsághalmaz metszeteTulajdonsag operator * ( const Tulajdonsag &A, const Tulajdonsag &B ){  Tulajdonsag C;  std::set_intersection( A.begin(), A.end(), B.begin(), B.end(),                         std::inserter( C, C.begin() ));  return C;}// --------------------------------------------------------------------// KülönbséghalmazTulajdonsag operator - ( const Tulajdonsag &A, const Tulajdonsag &B ){  Tulajdonsag C;  std::set_difference( A.begin(), A.end(), B.begin(), B.end(),                       std::inserter( C, C.begin() ));  return C;}// --------------------------------------------------------------------// Tagadás -- komplementum képzésTulajdonsag operator - ( const Tulajdonsag &A ){  return teljesHalmaz - A;}// --------------------------------------------------------------------// Részhalmaz ellenőrzésebool operator << ( const Tulajdonsag &A, const Tulajdonsag &B ){  return ( (A-B).size() == 0 );}bool operator >> ( const Tulajdonsag &A, const Tulajdonsag &B ){  return ( B << A );}// ====================================================================// Elemi tulajdonságok kezelése// Tulajdonság kódjának kikeresése. A függvény egy elemi tulajdonság// nevét kapja, és visszaadja a kódot. Ha a tulajdonság még nem// szerepelt, a következő szabad kódot kapja. Ha az elemi// tulajdonságok száma túl nagy, kilép a programból.int tulajdonsagKod( const std::string nev ){  // A korábbi név-kód párok  static std::map kodTabla;  // Kikeressük a nevet a táblázatból  std::map::const_iterator it;  it = kodTabla.find( nev );  // Ha szerepel a táblázatban, akkor megvan a kód  if (it != kodTabla.end())  {    return it->second;  }  // Nem szerepel a táblázatban. Ellenőrizzük, tele-e a táblázat  if ( kodTabla.size() >= ETN )  {    std::cout << "Túl sok elemi tulajdonság!" << std::endl;    exit( 1 );  }  // A kód a tábla mérete-edik 2-hatvány  int kod = 1 << kodTabla.size();  kodTabla.insert( std::make_pair( nev, kod ));  return kod;}// --------------------------------------------------------------------// Elemi tulajdonság (szó) tulajdonsággá konvertálásaTulajdonsag elemiTulajdonsag( const std::string &nev ){  int kod = tulajdonsagKod( nev );  // A tulajdonság kódja  int i;  Tulajdonsag T;  for (i=0; i nemUresHalmazok;  // Azon tulajdonságok felsorolása,                                           // amiknek a kapott információ                                           // alapján létezniük kell.// --------------------------------------------------------------------// Szűkítő jellegű állítások és kérdések (HA .. AKKOR, NINCS)// ellenőrzése és feldolgozása. Egy szűkítés azt állítja vagy kérdezi,// hogy atomok csak egy bizonyos halmazban vannak(-e). Pl. a "NINCS A"// azt állítja, hogy csak az A tulajdonságban felsorolt atomok// létezhetnek.// A függvény bemenete tehát egy tulajdonság, és az a kérdés, hogy// létezik-e ezen kívül atom. Az eredmény háromféle lehet:// 0 = az eddigi információ alapján nem tudjuk// 1 = biztosan nem létezik -- az új állítás a korábbiakból következik// 2 = biztosan létezik -- az új állítás a korábbiaknak ellentmondint SzukitesEllenorzes( const Tulajdonsag &A ){  uint i;  // Ha valamelyik biztosan nem üres halmazzal diszjunkt, akkor  // ellentmond az eddigi információnak  for (i=0; i> nemUresHalmazok[i]) return 1;  return 0;}// ---------------------------------------------------------------------// Egzisztencia állítás bejegyzésevoid EgzisztenciaBejegyzes( const Tulajdonsag &A ){  // Az újabb nem üres halmazt hozzávesszük a listához  nemUresHalmazok.push_back( A * lehetsegesHalmaz );}// ---------------------------------------------------------------------// "LÉTEZIK A" feldolgozása. Ha kerdes=true, akkor csak kérdezzükvoid Letezik( const Tulajdonsag &A, bool kerdes ){  switch (EgzisztenciaEllenorzes( A ))  {  case 0: // Új információ    if (kerdes)      std::cout << "NEM TUDOM" << std::endl;    else    {      EgzisztenciaBejegyzes( A );      std::cout << "ÉRTEM" << std::endl;    }    break;  case 1: // Következik a korábbiakból    if (kerdes)      std::cout << "IGEN" << std::endl;    else      std::cout << "TUDOM" << std::endl;    break;  case 2: // Ellentmond a korábbiaknak    if (kerdes)      std::cout << "NEM" << std::endl;    else      std::cout << "EZ ELLENTMOND A KORÁBBIAKNAK" << std::endl;    break;  }}// ====================================================================// Az input sorok interpretálása.// Ha valamikor hiba volt (pl. az ÉS és VAGY keverése), itt jelezzükbool voltHiba;// --------------------------------------------------------------------// Szavak egy sorozatának tulajdonsággá konvertálása. A szavak tömbb// elso-edik szavától az utso-adik szaváigTulajdonsag osszetettTulajdonsag( const std::vector &szavak,                                  int elso, int utso ){  Tulajdonsag osszeg;  int tipus = 0;    // 1 = a tagok VAGY-gyal vannak kapcsolva.                    //  2 = ÉS-sel. 0 = Még nem tudjuk  int i;  // A tulajdonságnak legalább egy szóból kell állnia  if (elso > utso) { voltHiba=true; return uresHalmaz; }  // Sorban megyünk a tagokon  i=elso; while (i<=utso)  {    // Ha ez nem az első tag, relációjelnek kell következnie.    if (i>elso)    {      if (szavak[i]=="VAGY")      {        // Ha már volt ÉS, az hiba        if (tipus == 2) { voltHiba = true; return uresHalmaz; }        tipus = 1;      }      else if (szavak[i]=="ÉS")      {        // Ha már volt VAGY, az hiba        if (tipus == 1) { voltHiba = true; return uresHalmaz; }        tipus = 2;      }      else { voltHiba = true; return uresHalmaz; } // Nem relációjel :-(      ++i; // feldolgoztuk a relációjelet    }    // Ellenőrizzük, a végére értünk-e    if (i>utso) { voltHiba=true; return uresHalmaz; }    // A következő tag ami csak XXX vagy NEM XXX alakú lehet    int tagadjuk=0;    if (szavak[i]=="NEM") {      tagadjuk=1;      ++i; if (i>utso) { voltHiba=true; return uresHalmaz; }    }    // A tulajdonság neve nem lehet védett szó    if ( szavak[i]=="NEM" || szavak[i]=="VAGY" || szavak[i]=="ÉS" ||         szavak[i]=="HA" || szavak[i]=="AKKOR" || szavak[i]=="VAGY" ||         szavak[i]=="LÉTEZIK" || szavak[i]=="NINCS" || szavak[i]=="?" )    { voltHiba = true; return uresHalmaz; }    // Az új tag kiszámítása és hozzáadása az öüsszeghez    Tulajdonsag ujTag = tagadjuk ?      - elemiTulajdonsag( szavak[i] ) : elemiTulajdonsag( szavak[i] );    switch (tipus)    {    case 0: osszeg = ujTag;          break;    case 1: osszeg = osszeg + ujTag; break;    case 2: osszeg = osszeg * ujTag; break;    }    ++ i;  }  return osszeg;}// ---------------------------------------------------------------------// Egy teljes sor szavakra tördelése. A kérdőjel önálló szóstd::vector szavakraTordeles( const std::string &sor ){  std::vector eredmeny;  std::string ujSzo;  int i,n;  n = sor.length();  for (i=0; i szavak = szavakraTordeles( sor );  int n = szavak.size();  bool kerdes;  voltHiba = false;  // Üres sorokat nem értünk  if (n==0)  {    std::cout << "NEM ÉRTEM" << std::endl;    return;  }  // Ha az utolsó szó egy kérdőjel, akkor kérdés  if (szavak[n-1]!="?") kerdes = false; else { kerdes = true; --n; }  if (szavak[0]=="HA")  {    // Megkeressük az AKKOR szót    int k=0; while (k

A dolgozatok tanulságai

A hibátlanul működő programokra 7 pont járt, a dokumentációra pedig legfeljebb a programra kapott pontszám fele, így gyűlhetett össze a maximális 7+3 pont.

A dokumentáció hiányosságai

Továbbra is nagyon hiányosak a programok dokumentációi. Ennek egyik oka talán az is lehet, hogy az elvárásaink nem elég világosak. Ezért most újra szeretnénk összefoglalni, hogy az S-jelű feladatok esetében egy jó leírás milyen részekből állhat. Mindenekelőtt a legfontosabb cél, hogy a javító vagy akárki más -- akár maga a program írója bizonyos idő elteltével -- könnyen megérthesse a program működését, és akár a programban előforduló hibákat is kijavíthassa.

- Az algoritmus működési elve. Elmagyarázzuk, hogy a program mit csinál, és miért működik. Az algoritmust többnyire érdemes külön fájlban leírni; a dokumentációnak ez a része egyrészt terjedelemesebb, másrészt olyan eszközöket (képletek, ábrák) is tartalmazhat, amiket a program szövegében nehéz elhelyezni.

- Áttekintés a program megvalósításáról. Ebben szerepel, hogy milyen programnyelven használtok, milyen operációs rendszeren és milyen fordítóval fordítottátok, a program milyen fontosabb részekből áll, és a használatához milyen esetleges változtatások szükségesek stb. Ez szerepelhet a forráskód elején is.

- A fontosabb változók és eljárások jelentése. Ez egy fontos összekötő kapocs az algoritmus leírása és a programkód között; elmagyarázza, hogy az adott változó vagy eljárás az algoritmus melyik részét valósítja meg. Ez részben a program áttekintésében, részben a forráskódban érdemes leírni.

- A forráskódban elhelyezett kommentek. Ezek célja a közvetlen forráskód megértése; ha valamelyik részlet értelme nem derülne ki azonnal az olvasó számára, akkor teszünk mellé egy rövid megjegyzést.

A legtöbb dolgozatból teljesen hiányzott az algoritmus és a program áttekintése. A kódban elhelyezett kommentek pedig csak egy-egy részletet próbáltak megmagyarázni, a program globális bemutatása nélkül. Így pedig nagyon nehéz megérteni, hogy a program maga hogyan működik.

Típushibák

Több versenyző nem bontotta az elemi tulajdonságokat atomokra. Emiatt a programjuk nem is működhetett helyesen. Ha a programjuk erre a leegyszerűsített esetre hibátlanul működött volna, 2+1 pontot kaphattak ... volna.

Az ékezetes karakterek kezelésa sajnos nagyon szorosan kapcsolódik az operációs rendszer által használt karakterkódoláshoz, és nagyon nehéz lenne a programot úgy megírni, hogy minden gépen egyformán jól működjön. A kódolásból származó problémákat nem tekintettük hibának, nem vontunk le érte pontot. Azokat a programokat, amiknél az ékezetes betűk kezelése gondot okozott, a forráskód módosításával, ékezetes betűk nélkül teszteltük.

Sajnos többeknél érzékelhető volt, hogy nem hagytak maguknak elegendő időt a feladat megoldására. Leginkább ez az oka a sok 0 pontos dolgozatnak. Pedig egy ilyen összetett feladat esetében a program tesztelésére és dokumentálására is időt kell hagyni.

Letölthető fájlok

C++ forráskód: s11.cpp