Celočíselné body v konvexní mnohostěně - Integer points in convex polyhedra - Wikipedia

Červené tečky jsou celočíselné mřížkové body v modrém mnohoúhelníku, druhý představuje dvojrozměrný lineární program

Studium celočíselné body v konvexní mnohostěně^[1] je motivován otázkami typu „kolik je nezáporných celé číslo hodnotná řešení dělá a soustava lineárních rovnic s nezápornými koeficienty mají „nebo“ kolik řešení má celočíselný lineární program počítání celých bodů v mnohostěn nebo o nich vyvstávají další otázky teorie reprezentace, komutativní algebra, algebraická geometrie, statistika, a počítačová věda.^[2]

Sada celočíselných bodů nebo obecněji sada bodů an afinní mříž, v mnohostěnu se nazývá Z-mnohostěn,^[3] z matematické notace ${ displaystyle mathbb {Z}}$ nebo Z pro množinu celých čísel.^[4]

Vlastnosti

Pro mřížku Λ, Minkowského věta souvisí číslo d (Λ) a objem symetrického konvexní sada S na počet mřížových bodů obsažených v S.

Počet mřížkových bodů obsažených v a polytop všechny jejichž vrcholy jsou prvky mřížky jsou popsány polytopem Ehrhartův polynom. Vzorce pro některé koeficienty tohoto polynomu zahrnují také d (Λ).

Aplikace

Optimalizace smyčky

V určitých přístupech k optimalizace smyčky, sada provádění těla smyčky je považována za sadu celočíselných bodů v mnohostěn definovaných omezeními smyčky.

Viz také

Odkazy a poznámky

^ V některých kontextech se konvexní mnohostěny nazývají jednoduše „mnohostěn“.
^ Celočíselné body v mnohostěnech. Geometrie, teorie čísel, teorie reprezentace, algebra, optimalizace, statistika, ACM - Společná letní výzkumná konference SIAM, 2006
^ Termín "Z-mnohostěn" se také používá jako synonymum k konvexní příhradový polytop, konvexní obal konečně mnoha bodů v afinní mříži.
^ „Výpočty na iterovaných prostorech“ v: Příručka pro návrh kompilátoru: Optimalizace a generování strojového kódu, CRC Press 2007, 2. vydání, ISBN 1-4200-4382-X, s. 15-7

Další čtení

Barvinok, Alexander; Beck, Matthias; Haase, Christian; Reznick, Bruce; Welker, Volkmar (2005), Integer Points In Polyhedra: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference pořádané v Snowbird, UT, 13. – 17. Července 2003, Současná matematika, 374, Providence, RI: American Mathematical Society, doi:10.1090 / conm / 374, ISBN 0-8218-3459-2, PAN 2134757
Barvinok, Alexander (2008), Celočíselné body v mnohostěnách, Curych Lectures in Advanced Mathematics, Zürich: European Mathematical Society, doi:10.4171/052, ISBN 978-3-03719-052-4, PAN 2455889
Beck, Matthias; Haase, Christian; Reznick, Bruce; Vergne, Michèle; Welker, Volkmar; Yoshida, Ruriko (2008), Celočíselné body v mnohostěnách: geometrie, teorie čísel, teorie reprezentace, algebra, optimalizace, statistika (PDF), Současná matematika, 452, Providence, RI: American Mathematical Society, doi:10.1090 / conm / 452, ISBN 978-0-8218-4173-0, PAN 2416261

[1] V některých kontextech se konvexní mnohostěny nazývají jednoduše „mnohostěn“.

[2] Celočíselné body v mnohostěnech. Geometrie, teorie čísel, teorie reprezentace, algebra, optimalizace, statistika, ACM - Společná letní výzkumná konference SIAM, 2006

[3] Termín "Z-mnohostěn" se také používá jako synonymum k konvexní příhradový polytop, konvexní obal konečně mnoha bodů v afinní mříži.

[4] „Výpočty na iterovaných prostorech“ v: Příručka pro návrh kompilátoru: Optimalizace a generování strojového kódu, CRC Press 2007, 2. vydání, ISBN 1-4200-4382-X, s. 15-7

[1]

[2]

[3]

[4]