תורת החבורות החישובית

מתוך ויקיפדיה, האנציקלופדיה החופשית

תורת החבורות החישובית היא ענף של מתמטיקה חישובית העוסק באלגוריתמים לפתרון בעיות הנובעות מתורת החבורות.

חישובים בחבורות אבסטרקטיות[עריכת קוד מקור | עריכה]

בעיות רבות בחבורות נתונות על ידי יוצרים ויחסים אינן ניתנות לחישוב אלגוריתמי (ראו תכונת מרקוב ובעיות דן). עם זאת, יש שיטות (שאינן מבטיחות עצירה) לחישוב האינדקס של תת-חבורה בחבורה נתונה: ראו אלגוריתם טוד-קוקסטר ואלגוריתם קנות'-בנדיקס.

חישובים בחבורה הסימטרית[עריכת קוד מקור | עריכה]

חישובים רבים בחבורות סופיות אפשר לממש בחבורת התמורות . החבורה נתונה בדרך כלל על ידי קבוצת יוצרים.

החישובים נעזרים בתת-חבורות המייצבים של החבורה . למשל, את סדר החבורה אפשר לחשב על ידי הכפלת האינדקסים בשרשרת תת-החבורות .

את החישוב הנאיבי אפשר להאיץ באמצעות שימוש בבסיסים: בסיס לחבורה הוא קבוצת נקודות המקיימת (ולכן איבר מוגדר היטב על ידי הפעולה שלו על ). בסיס חזק לקבוצת יוצרים הוא בסיס, המקיים את התנאי לכל תת-קבוצה . אלגוריתם שרייר-סימס מקבל קבוצת יוצרים לחבורת תמורות, ומחזיר קבוצת יוצרים טובה יותר ובסיס חזק ביחס אליה.

P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.