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

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

חישובים בחבורות אבסטרקטיות

עריכה

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

חישובים בחבורה הסימטרית

עריכה

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

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

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

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