A kommunikációs gráfok és a fekete-fehér SAT probléma közti összefüggések vizsgálata

Rajna, Franciska (2021) A kommunikációs gráfok és a fekete-fehér SAT probléma közti összefüggések vizsgálata In: Agria Média 2020. Eger, Eszterházy Károly Egyetem Líceum Kiadó. pp. 321-330.

[thumbnail of 321_330_Rajna.pdf] pdf
321_330_Rajna.pdf

Download (1MB) [error in script]
Hivatalos webcím (URL): https://doi.org/10.17048/AM.2020.321

Absztrakt (kivonat)

Ebben a cikkben a kommunikációs gráfok és a fekete-fehér SAT probléma közötti összefüggéseket vizsgálom. A kommunikációs gráfok olyan speciális hurokélmentes irányított gráfok, amelyeknek csúcsai logikai változók, az élei pedig a kommunikációt reprezentálják. Ilyen típusú gráfokkal lehet többek között vezeték nélküli szenzorhálózatokat is modellezni. A cikkben bemutatom a fekete-fehér SAT problémát. A fekete-fehér SAT problémák olyan logikai formulák, amelyek majdnem kielégíthetetlenek, csak két megoldásuk van, az úgynevezett fehér hozzárendelés, ahol minden változó igaz, és a fekete hozzárendelés, amelyben minden változó hamis. A fekete-fehér SAT problémák ekvivalensek az olyan konjunktív normálformában lévő logikai formulákkal, amelyekben minden klózban pozitív és negatív literálok vegyesen szerepelnek (például ilyen 3SAT klózok a -++, --+), de sem a fehér klóz, amelyben minden literál pozitív, sem a fekete klóz, amelyben minden literál negatív, nem vezethető le. Továbbá ismertetem, és hatékonyság szempontjából elemzem a kommunikációs gráfok különböző logikai modelljeit (Erős modell, Balatonboglár modell, Egyszerűsített BB modell, Gyenge modell). ----- Investigation of the relationship between communication graphs and the black and white sat ----- In this article, I examine the relationships between communication graphs and the black-andwhite SAT problem. Communication graphs are special loop-free directed graphs whose vertices are logical variables and whose edges represent communication. These types of graphs can be used to model wireless sensor networks (WSNs), among other things. I present the black-and-white SAT problem. Black-and-white SAT problems are logical formulas that are almost unsatisfiable, they have only two solutions, the so-called white assignment, where all variables are true, and the black assignment, in which all variables are false. Black-and-white SAT problems are equivalent to logical formulas in a conjunctive normal form in which positive and negative literals are mixed in each clause (e.g., such 3-SAT clauses are - ++, - +), but not the white clause in which all literals are positive, nor the black clause in which all literals are negative cannot be deduced. I also describe and analyze the different logical models of communication graphs (Strong model, Balatonboglár model, Simplified BB model, Weak model) in terms of efficiency.

Mű típusa: Könyvrészlet - Book section
Szerző:
Szerző neve
Email
MTMT azonosító
ORCID azonosító
Közreműködés
Rajna, Franciska
NEM RÉSZLETEZETT
NEM RÉSZLETEZETT
NEM RÉSZLETEZETT
Szerző
Kapcsolódó URL-ek:
Kulcsszavak: fekete-fehér SAT probléma, kommunikációs gráf, Erős modell, Gyenge modell, Balatonboglár modell, Egyszerűsített Balatonboglár modell ----- black-and-white SAT problem, communication graph, Strong model, Weak model, Balatonboglár model, Simplified Balatonboglár model
Nyelv: magyar
DOI azonosító: 10.17048/AM.2020.321
ISBN: 978-963-496-199-4
Felhasználó: Tibor Gál
Dátum: 02 Szep 2021 15:13
Utolsó módosítás: 02 Szep 2021 15:13
URI: http://publikacio.uni-eszterhazy.hu/id/eprint/7056
Műveletek (bejelentkezés szükséges)
Tétel nézet Tétel nézet