Egy NSUCRYTPO 2019 versenyfeladat algoritmikus továbbgondolása
A TDK dolgozat témája az NSUCRYPTO Nemzetközi Kriptográfia Olimpia 2019-es versenyfeladatának algoritmikus továbbgondolása (https://nsucrypto.nsu.ru/archive/). A feladat a következőképpen szólt. Mutassuk meg, hogy az alábbi algoritmus véges sok lépésben megáll: A vi 1024 hosszú bitsorozatban kiválasztunk két 0-t, például a k és m indexűt (k ≤ m), majd a k, k+1, ..,m indexű biteket invertáljuk, így kapva a vi+1 bitsorozatot. A dolgozatban nem triviális pontos értéket adunk ezen eljárás maximális iterációszámára, és különbözőféle általánosításokkal is vizsgálódunk. Megmutatjuk, hogy a maximális iterációszámra adott felső korlát az algoritmus bármely olyan variációjában, mely megtartja azt a tulajdonságot, hogy a kiválasztott két szélső bitből 1-es lesz, igaz marad. A bizonyítás kulcslépése egy, a bitsorozatokon értelmezett F(u) lineáris funkcionál megkonstruálása.
A feladatra tekinthetünk úgy, hogy az n hosszú bitsorozatok egy irányított gráf csúcsai, és egy u csúcsból pontosan akkor mutat él egy v csúcsba, ha az algoritmus egy lépésében el tudunk jutni u-ból v-be. Ekkor a maximális iterációszám megfeleltethető a gráfban a csupa 0 csúcsból a csupa 1 csúcsba vezető leghosszabb irányított út hosszának, jelöljük ezt l(n)-nel. A problémát általánosíthatjuk, ha nem a csupa 0 csúcsból keressük a leghosszabb irányított utat, hanem egy tetszőleges, véletlenszerűen kiválasztott u csúcsból. Az ilyen utak hosszára felső korlátot adhatunk a megkonstruált lineáris funkcionálunk segítségével. Az F(u) linearitását kihasználva meghatározzuk F(u) várható értékét random u esetén. Tetszőleges, véletlenszerűen kiválasztott u csúcsból kiindulva a maximális út hosszára felső korlátot az l(n)-F(u) kifejezés. Megmutatjuk, hogy mely csúcsok esetén tudunk olyan utat konstruálni, amely ehhez az értékhez közel marad.
szerző
-
Pintér József
Matematikus mesterképzési szak (MSc)
mesterképzés (MA/MSc)
konzulens
-
Dr. Nagy Gábor Péter
egyetemi tanár, Algebra Tanszék
