cofiprt / a2-s1-aa-t2-polynomial-reduction Goto Github PK
View Code? Open in Web Editor NEWJava program to apply SAT reductions
Java program to apply SAT reductions
---------------------------------------- --------- Analiza Algoritmilor --------- ----- Tema 2. Reduceri polinomiale ----- ---------------------------------------- Cuprinsul: 1. Pachetul 'atoms'.................................Linia 20 1.1. Clasa 'Atom'...............................Linia 21 1.2. Enum-ul 'AtomType'.........................Linia 29 2. Pachetul 'reduction'.............................Linia 33 2.1. Clasa 'Graph'..............................Linia 34 2.2. Clasa 'GraphOperator'......................Linia 41 2.3. Clasa 'MainClass'..........................Linia 100 3. Demonstratie de reducere polinomiala.............Linia 144 4. Alte precizari...................................Linia 205 === atoms === ------ Atom - Un astfel de obiect reprezinta un atom(o variabila) ce poate fi de doua tipuri: muchie, caz in care argumentele reprezinta capetele ei, sau distanta, caz in care primul argument reprezinta distanta de la nodul intai la nodul din al doilea argument. - Utilizez un astfel de obiect pentru a fi clar in cod cand se lucreaza cu un atom, pentru a i se intelege argumentele si tipul. ------ AtomType - Un simplu enum ce defineste doua tipuri de atomi: muchie (EDGE) si distanta (DISTANCE) === reduction === ------ Graph - Un simplu graf neorientat ce retine numarul de noduri si o matrice de adiacenta - Sunt prezente metode uzuale pentru un graf: - 'addEdge' adauga o muchie intre cele 2 noduri primite ca parametru - 'hasEdge' testeaza daca exista o muchie intre 2 noduri ------ GraphOperator - Aceasta clasa incapsuleaza un graf si prezinta o multitudine de metode ce servesc la rezolvarea cerintei. - Sunt prezente, in primul rand, metode ce servesc la manipularea String-urilor cu ajutorul functiilor boolene. - 'AND' si 'OR' ce pot primi ori 2 parametri ori o lista cu mai multi parametri, intre care se va aplica (sub forma de String) functia aplicata - 'NOT' ce primeste un singur string caruia ii adauga simbolul de negatie "~" - 'XNOR' ce se foloseste de toate cele 3 pentru a realiza operatia XNOR asupra a doua string-uri. - 'noParanthesis' este o metoda ce "taie" (daca este cazul) perechea cea mai exterioara de paranteze dintr-un string (foloseste doar la afisare) - tin sa precizez ca la un anumit numar de paranteze "inofensive" (de exemplu, "((expresie))") programul 'main' (ce banuiesc ca verifica echivalenta a doua expresii) ori intra in loop infinit ori dureaza execrabil de mult (halting problem) incepand de la testul 4 inclusiv (primele 3 teste nu prezinta acest defect) - Metode principale pentru rezolvarea cerintei: - 'pathsAndDistances' se ocupa cu clauza ce reprezinta caile unui drum printr-un nod. De exemplu, dintre toate muchiile unui nod, printr-una trebuie sa se ajunga in el si prin alta trebuie sa se paraseasca nodul, restul muchiilor fiind astfel neatinse. Metoda, astfel, itereaza prin fiecare nod si ii gaseste fiecare muchie. La acest pas, se genereaza posibilitatile de alegere a cate 2 muchii (combinari de N - noduri - luate cate 2). Totodata, pentru fiecare nod, se genereaza toate distantele posibile de la primul nod la acesta (anume, cum este precizat si in enunt, distante in intervalul [1, N/2+1] - 'twoByTwo' primeste o lista de muchii si genereaza, in maniera prezentata mai sus, un numar de (combinari de N luate cate 2) clauze - 'possibleDistances' este o metoda simpla ce genereaza, in maniera antepusa, distantele posibile ce pot fi parcurse catre un nod - 'twoWayPaths' se ocupa de generarea clauzelor ce reprezinta directia printr-o muchie. Avand in vedere ca graful este neorientat, o muchie poate fi traversata in ambele sensuri. - 'pathsFromFirstNode' genereaza alegerile posibile pornind din primul nod, avand in vedere ca distanta spre oricare alt nod ce poate fi "atins" instant este 1. - 'pathsToEveryNode' incearca fiecare distanta posibila pentru un un nod si ii afla metodele de intrare in acesta (muchiile care intra in el, tinand cont ca trebuie sa se realizeze o distanta anume de la primul nod la acesta). - 'possibleNodeEntries' genereaza aceste posibilitati de intrare intr-un nod in functie de o anumita distanta, presupunand totodata (si generand clauzele aferente) faptul ca nu se ajunge in nod intr-o distanta mai mica decat cea aleasa. ------ MainClass - Clasa ce contine metoda 'main' - Serveste mai multe functionalitati IO: Un Scanner pentru citirea din fisier 'inputStream' Redirectionarea output-ului se face in fisierul de output prin System.setOut asupra stream-ului aferent fisierului. Se face un backup al consolei (out-ul initial) in cazul in care se doreste reutilizarea ei la sfarsitul programului. Obiecte principale: Programul va lucra cu un graf orientat principal 'graph' si un 'graphOperator' ce va actiona asupra lui Metoda setupIO: Face modificarile necesare pentru input si output pentru a se putea lucra cu aceste stream-uri Metoda restoreIO: Restaureaza modificarile facute de 'setupIO' Metoda registerGraph: > Se citeste din fisier numarul de noduri din graf urmat de muchiile pe care acesta le prezinta > Se genereaza un astfel de graf Metoda convertToSAT: > Aplica metodele generatoare de clauze din 'GraphOperator' asupra grafului: - pathsAndDistances - twoWayPaths - pathsFromFirstNode - pathsToEveryNode > Se aplica AND asupra clauzelor generate de metodele antepuse > In cazul in care s-a descoperit devreme (pathsAndDistances) ca nu poate exista un ciclu hamiltonian (s-a gasit un nod cu o singura muchie) se ignora alte metode si programul se incheie cu afisarea unei expresii ce este mereu falsa. Metoda main: > Se stabilesc stream-urile de input si de output si se incepe executia programului === Demonstratie de reducere polinomiala === Avand in vedere ca transformarea se produce in 'convertToSAT', analizam fiecare instructiune repetitiva de la apelul ei. - pathsAndDistances: for (1 -> N) => N for (1 -> N) (fara un caz) => N - 1 twoByTwo: pentru un numar N de noduri, orice nod poate avea maximum N-1 muchii combinari de N-1 luate cate 2 possibleDistances: (de N-1 ori) for (1 -> N/2 + 1) => N/2 + 1 TOTAL: N * (N-1) * (N-1)! / 2! / (N-3)! + (N-1) * (N/2 + 1) = = N * (N-1) * (N-2) * (N-1) / 2 + (N-1) * (N/2 + 1) APARTINE: O(N^4) - twoWayPaths: for (1 -> N) => N for (1 -> N) => N TOTAL: N*N = N^2 APARTINE: O(N^2) - pathsFromFirstNode: for (1 -> N) => N for (1 -> N) => N TOTAL: N + N = 2N APARTINE: O(N) - pathsToEveryNode: for (2 -> N/2 + 1) => N/2 for (2 -> N) => N - 1 possibleNodeEntries: for (2 -> N) => N - 1 for (1 -> N/2 + 1 - 1) => N/2 TOTAL: ((N-1) + N/2) * (N-1) * (N/2) APARTINE: O(N^3) *** PRECIZARE *** Functiile AND si OR asupra unor ArrayList-uri au si ele un 'for' in ele dar care functioneaza intotdeauna O(N). Aceasta complexitate nu schimba rezultatul final, fiind mai "mica" decat restul complexitatilor principale. TOTAL PROGRAM: O(N^4) + O(N^2) + O(N) + O(N^3) APARTINE: O(N^4), prin urmare transformarea este polinomiala === Alte precizari === - Deja precizat, incepand cu testul 4 exista cazuri in care programul 'main' folosit de checker dureaza prea mult. Nu am reusit sa gasesc exact cauza, dar un indiciu poate fi ca un numar prea mare de paranteze inofensive (exemplu "((expresie))") poate provoca acest lucru. O alta presupunere este adaugarea parantezelor in maniera "(a & b) & c" sau "a & (b & c)" in loc de "a & b & c". Confuzia vine de la faptul ca am eliminat ambele "greseli" inainte sa testez din nou si nu stiu daca una dintre ele, sau ambele in combinatie, reprezinta problema.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.