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.
![[img]](http://publikacio.uni-eszterhazy.hu/style/images/fileicons/text.png) |
pdf
321_330_Rajna.pdf Download (1MB) |
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 | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| 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 |
 |
Tétel nézet |
