Artificial Intelligence techniques for searching paths and cycles in hypercubes
Thesis title in Czech: | Techniky umělé inteligence pro hledání cest a kružnic v hyperkrychli |
---|---|
Thesis title in English: | Artificial Intelligence techniques for searching paths and cycles in hypercubes |
Academic year of topic announcement: | 2023/2024 |
Thesis type: | diploma thesis |
Thesis language: | angličtina |
Department: | Department of Theoretical Computer Science and Mathematical Logic (32-KTIML) |
Supervisor: | RNDr. Jiří Fink, Ph.D. |
Author: | hidden - assigned and confirmed by the Study Dept. |
Date of registration: | 26.11.2023 |
Date of assignment: | 27.11.2023 |
Confirmed by Study dept. on: | 27.11.2023 |
Opponents: | Torsten Mütze, Ph.D. |
Guidelines |
The goal of the thesis is to study paths and cycles in the hypercubes with additional properties presented in [1].
The student will use alpha-beta pruning to reduce the number of cases needed to verify a variant of Ruskey-Savage conjecture in small dimensions. Then, student will compare different methods to find a path in the hypercube with special properties (e.g. order-preserving paths) based on backtracking, SAT/CSP, genetic programming or machine learning. |
References |
[1] Mütze, Torsten. "Combinatorial Gray codes-an updated survey." arXiv preprint arXiv:2202.01280 (2022).
[2] Zulkoski, Edward, Vijay Ganesh, and Krzysztof Czarnecki. "MathCheck: A math assistant via a combination of computer algebra systems and SAT solvers." Automated Deduction-CADE-25: 25th International Conference on Automated Deduction, Berlin, Germany, August 1-7, 2015, Proceedings 25. Springer International Publishing, 2015. [3] Fink, Jiří. "Perfect matchings extend to Hamilton cycles in hypercubes." Journal of Combinatorial Theory, Series B 97.6 (2007): 1074-1076. |