Minimal sets over a monotone predicate: Enumeration and counting /
V mnoha oblastech informatiky pracujeme s referenční množinou C a monotónním predikátem P : P(C) → Bool. Ona monotónnost znamená, že pokud if P(N) = True, pak P(M) = True pro každé N ⊆ M ⊆ C. Cílem je identifikovat minimální podmnožiny C které splňují predikát P; tyto podmnožiny jsou označovány zkra...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Angličtina |
| Vydáno: |
2021
|
| Témata: | |
| On-line přístup: | https://is.muni.cz/th/y4v8m/ |
| LEADER | 05238ctm a22007937i 4500 | ||
|---|---|---|---|
| 001 | MUB01006479362 | ||
| 003 | CZ BrMU | ||
| 005 | 20240522111653.0 | ||
| 008 | 210323s2021 xr ||||| |||||||||||eng d | ||
| STA | |a POSLANO DO SKCR |b 2023-04-17 | ||
| 035 | |a (ISMU-VSKP)291994 | ||
| 040 | |a BOD114 |b cze |d BOD018 |e rda | ||
| 072 | 7 | |a 004.4/.6 |x Programování. Software |2 Konspekt |9 23 | |
| 072 | 7 | |a 51 |x Matematika |2 Konspekt |9 13 | |
| 080 | |a 004.421 |2 MRF | ||
| 080 | |a 512 |2 MRF | ||
| 080 | |a 510.6:512 |2 MRF | ||
| 080 | |a 16 |2 MRF | ||
| 080 | |a 004.03 |2 MRF | ||
| 100 | 1 | |a Bendík, Jaroslav |% UČO 396057 |* [absolvent FI MU] |4 dis | |
| 242 | 1 | 0 | |a Minimal sets over a monotone predicate: Enumeration and counting |y eng |
| 245 | 1 | 0 | |a Minimal sets over a monotone predicate: Enumeration and counting / |c Jaroslav Bendík |
| 264 | 0 | |c 2021 | |
| 300 | |a 201 stran : |b ilustrace | ||
| 336 | |a text |b txt |2 rdacontent | ||
| 337 | |a bez média |b n |2 rdamedia | ||
| 338 | |a svazek |b nc |2 rdacarrier | ||
| 500 | |a Vedoucí práce: Ivana Černá | ||
| 502 | |a Dizertace (Ph.D.)--Masarykova univerzita, Fakulta informatiky, 2021 | ||
| 520 | 2 | |a V mnoha oblastech informatiky pracujeme s referenční množinou C a monotónním predikátem P : P(C) → Bool. Ona monotónnost znamená, že pokud if P(N) = True, pak P(M) = True pro každé N ⊆ M ⊆ C. Cílem je identifikovat minimální podmnožiny C které splňují predikát P; tyto podmnožiny jsou označovány zkratkou MSMP z anglického Minimal Sets over a Monotone Predicate. Například, uvažme že C je nesplnitelná množina Booleovských klauzulí a P(N) = True právě když N ⊆ C je nesplnitelná. V tomto případě jsou ony MSMP nazývány minimální nesplnitelné podmnožiny C, krátce MUSes z anglického Minimal Unsatisfiable Subsets. V této disertační práci řešíme několik výpočetních problémů, které lze formulovat pomocí terminologie MSMP. V první části práce navrhujeme dva doménově univerzální algoritmy pro enumeraci MSMP, tj. algoritmy které mohou být použity pro libovolnou konkrétní instanci MSMP. Přirozenou rolí doménově univerzálních algoritmů je složit jako „ready-to-use“ řešení pro každou novou instanci MS |% cze | |
| 520 | 2 | 9 | |a In many areas of computer science, we are given a reference set C and a monotone predicate P : P(C) → Bool. The monotonicity means that if P(N) = True then P(M) = True for every N ⊆ M ⊆ C. The goal is to identify the Minimal Subsets of C satisfying the Monotone Predicate (MSMPs). For instance, assume that C is an unsatisfiable set of Boolean clauses and P(N) = True iff N ⊆ C is unsatisfiable. In this case, the MSMPs are the minimal unsatisfiable subsets (MUSes) of C which are often used during an analysis of unsatisfiable Boolean formulas. The contribution of the thesis is the following. In the first part, we propose two domain agnostic algorithms for MSMP enumeration, i.e. algorithms that can be applied for any particular instance of MSMPs. A natural role of domain agnostic algorithms is to serve as ready-to-use solutions for any new instance of MSMPs that might arise. In the second part, we focus on the particular instance of MSMPs where the input set C is a set of Boolean clauses |9 eng |
| 650 | 0 | 7 | |a algoritmy (programování) |7 ph131788 |2 czenas |
| 650 | 0 | 7 | |a algebra |7 ph114025 |2 czenas |
| 650 | 0 | 7 | |a algebraická logika |7 ph249426 |2 czenas |
| 650 | 0 | 7 | |a logika |7 ph122436 |2 czenas |
| 650 | 0 | 7 | |a počítačové systémy |7 ph115866 |2 czenas |
| 650 | 0 | 9 | |a computer algorithms |2 eczenas |
| 650 | 0 | 9 | |a algebra |2 eczenas |
| 650 | 0 | 9 | |a algebraic logic |2 eczenas |
| 650 | 0 | 9 | |a logic |2 eczenas |
| 650 | 0 | 9 | |a computer systems |2 eczenas |
| 655 | 7 | |a disertace |7 fd132024 |2 czenas | |
| 655 | 9 | |a dissertations |2 eczenas | |
| 658 | |a Informatika |b Technologie a metodologie počítačových systémů |c FI D-INF DIIA (DIIA) |2 CZ-BrMU | ||
| 700 | 1 | |a Černá, Ivana, |d 1963- |7 mub2011658599 |% UČO 1419 |4 ths | |
| 710 | 2 | |a Masarykova univerzita. |b Katedra teorie programování |4 dgg | |
| 856 | 4 | 1 | |u https://is.muni.cz/th/y4v8m/ |
| CAT | |c 20210323 |l MUB01 |h 0420 | ||
| CAT | |a POSPEL |b 02 |c 20210327 |l MUB01 |h 0026 | ||
| CAT | |a POSPEL |b 02 |c 20210327 |l MUB01 |h 0026 | ||
| CAT | |a POSPEL |b 02 |c 20210912 |l MUB01 |h 2335 | ||
| CAT | |a POSPEL |b 02 |c 20210912 |l MUB01 |h 2336 | ||
| CAT | |a POSPEL |b 02 |c 20211010 |l MUB01 |h 2218 | ||
| CAT | |a HANAV |b 02 |c 20211116 |l MUB01 |h 0031 | ||
| CAT | |a POSPEL |b 02 |c 20220629 |l MUB01 |h 0104 | ||
| CAT | |a POSPEL |b 02 |c 20221019 |l MUB01 |h 2326 | ||
| CAT | |a POSPEL |b 02 |c 20221101 |l MUB01 |h 0840 | ||
| CAT | |a VESELA |b 02 |c 20230109 |l MUB01 |h 1335 | ||
| CAT | |c 20230417 |l MUB01 |h 1117 | ||
| CAT | |a POSPEL |b 02 |c 20230629 |l MUB01 |h 0037 | ||
| CAT | |a POSPEL |b 02 |c 20240405 |l MUB01 |h 2124 | ||
| CAT | |a VESELAX |b 02 |c 20240522 |l MUB01 |h 1114 | ||
| CAT | |a VESELAX |b 02 |c 20240522 |l MUB01 |h 1115 | ||
| CAT | |a VESELAX |b 02 |c 20240522 |l MUB01 |h 1116 | ||
| CAT | |a VESELAX |b 02 |c 20240522 |l MUB01 |h 1116 | ||
| LOW | |a POSLANO DO SKCR |b 2023-04-17 | ||
| 994 | - | 1 | |l MUB01 |l MUB01 |m BOOK |1 FI |a Fakulta informatiky |2 SKLAD |b sklad |3 Diz. práce 2020 |5 42005D2744 |8 20230109 |f 72 |f Týdenní |r 20230109 |
| AVA | |a INF50 |b FI |c sklad |d Diz. práce 2020 |e available |t K dispozici |f 1 |g 0 |h N |i 0 |j SKLAD | ||