الگوریتم تاد

الگوریتم تاد – کاکستر

از ویکیپدیا، دانشنامه آزاد

در تئوری گروه ، الگوریتم تاد-کوکستر ، که توسط JA Todd و HSM Coxeter در سال 1936 ایجاد شد، الگوریتمی برای حل مسئله شمارش هم مچموعه است . با ارائه یک گروه G توسط مولدها و روابط و یک زیرگروه H از G ، الگوریتم مجموعه‌های H در G را برمی‌شمارد و نمایش جایگشت G را در فضای هم‌زیستی‌ها (که با عمل ضرب چپ به دست می‌آید) توصیف می‌کند. اگر ترتیب یک گروه G نسبتا کوچک باشد و زیرگروه H بدون پیچیدگی شناخته شود (مثلاً یک گروه چرخه ای )، آنگاه الگوریتم را می توان با دست انجام داد و توصیف معقولی از گروه G ارائه می دهد . کاکستر و تاد با استفاده از الگوریتم خود نشان دادند که سیستم های خاصی از روابط بین مولدهای گروه های شناخته شده کامل هستند، یعنی سیستم های تعریف روابط را تشکیل می دهند.

الگوریتم Todd-Coxeter را می توان برای گروه های نامتناهی اعمال کرد و مشخص است که در تعداد محدودی از مراحل به پایان می رسد، مشروط بر اینکه شاخص H در G محدود باشد . از سوی دیگر، برای یک جفت عمومی متشکل از یک ارائه گروهی و یک زیر گروه، زمان اجرای آن با هیچ تابع قابل محاسبه شاخص زیرگروه و اندازه داده های ورودی محدود نمی شود.

توضیحات الگوریتم [ ویرایش ]

یکی از پیاده سازی الگوریتم به صورت زیر پیش می رود. فرض کنید که $G=\langle X\mid R\rangle$ ، جایی که $ایکس$ مجموعه ای از مولدها و $آر$ مجموعه ای از روابط است و با" $ایکس'$ مجموعه مولدها $ایکس$ و معکوس آنها اجازه دهید $H=\langle h_{1},h_{2},\ldots ,h_{s}\rangle$ جایی که $سلام}$ کلمات عناصر هستند" $ایکس'$ . سه نوع جدول وجود دارد که مورد استفاده قرار خواهند گرفت: جدول هم مچموعه، جدول رابطه برای هر رابطه در $آر$ و یک جدول زیر گروه برای هر مولد $سلام}$ از $اچ$ . اطلاعات به تدریج به این جداول اضافه می شود و پس از پر شدن آنها، تمام هم مچموعه ها شمارش شده و الگوریتم خاتمه می یابد.

جدول هم مچموعه برای ذخیره روابط بین هم مچموعه های شناخته شده هنگام ضرب در یک مولد استفاده می شود. دارای ردیف‌هایی است که نشان‌دهنده هم مجموعه هستند $اچ$ و یک ستون برای هر عنصر از" $ایکس'$ . اجازه دهید $ج_{i}$ علامت هم مچموعه ردیف i از جدول هم مچموعه، و اجازه دهید $g_{j}\در X'$ مولد ستون j را نشان می دهد. ورودی جدول هم مچموعه در ردیف i ، ستون j به صورت k (در صورت شناخته شدن) تعریف می شود ، جایی که k به گونه ای است $C_{k}=C_{i}g_{j}$ .

جداول رابطه برای تشخیص اینکه برخی از هم مچموعه هایی که پیدا کرده ایم واقعاً معادل هستند استفاده می شود. یک جدول رابطه برای هر رابطه در $آر$ نگهداری می شود. اجازه دهید1تی $1=g_{{n_{1}}}g_{{n_{2}}}\cdots g_{{n_{t}}}$ یک رابطه در $آر$ ، جایی که" $g_{{n_{i}}}\در X'$ . جدول رابطه دارای ردیف هایی است که نشان دهنده هم مجموعه هستند $اچ$ مانند جدول هم مچموعه. دارای t ستون است و ورودی در ردیف i و ستون j به صورت k (در صورت شناخته شدن) تعریف می شود ، جایی که $C_{k}=C_{i}g_{{n_{1}}}g_{{n_{2}}}\cdots g_{{n_{j}}}$ . به طور خاص، $(آی تی)$ 'امین ورودی در ابتدا من است ، از آنجا که1 $g_{{n_{1}}}g_{{n_{2}}}\cdots g_{{n_{t}}}=1$ .

در نهایت، جداول زیر گروه مشابه جداول رابطه هستند، با این تفاوت که آنها روابط احتمالی مولدهای را دنبال می کنند. $اچ$ . برای هر مولد $h_{n}=g_{{n_{1}}}g_{{n_{2}}}\cdots g_{{n_{t}}}$ از $اچ$ ، با" $g_{{n_{i}}}\در X'$ ، یک جدول زیر گروه ایجاد می کنیم. فقط یک ردیف دارد که مربوط به هم مچموعه است $اچ$ خود دارای t ستون است و ورودی در ستون j (در صورت شناخته شدن) به صورت k تعریف می شود ، جایی کهسیک=12⋯ $C_{k}=Hg_{{n_{1}}}g_{{n_{2}}}\cdots g_{{n_{j}}}$ .

هنگامی که یک ردیف از یک رابطه یا جدول زیرگروه تکمیل می شود، یک قطعه اطلاعات جدید $C_{i}=C_{j}g$ ،" $g\در X'$ ، یافت می شود. این به عنوان کسر شناخته می شود . از کسر، ممکن است بتوانیم ورودی های اضافی جداول رابطه و زیرگروه را پر کنیم، که منجر به کسرهای اضافی احتمالی می شود. می توانیم ورودی های جدول هم مچموعه مربوط به معادلات را پر کنیم $C_{i}=C_{j}g$ و-1 $C_{j}=C_{i}g^{{-1}}$ .

با این حال، هنگام پر کردن جدول هم مچموعه، ممکن است قبلاً یک ورودی برای معادله داشته باشیم، اما ورودی مقدار متفاوتی داشته باشد. در این مورد، ما کشف کرده‌ایم که دو تا از مجموعه‌های ما در واقع یکسان هستند، که به عنوان تصادف شناخته می‌شود . فرض کنید $C_{i}=C_{j}$ ، با $i<j$ . همه نمونه های j را در جداول با i جایگزین می کنیم . سپس، تمام ورودی‌های ممکن جداول را پر می‌کنیم، که احتمالاً منجر به کسر و تصادفات بیشتر می‌شود.

اگر پس از بررسی همه کسرها و تصادفات، ورودی های خالی در جدول وجود داشت، یک هم مچموعه جدید به جداول اضافه کنید و این روند را تکرار کنید. ما مطمئن می شویم که هنگام اضافه کردن هم مچموعه ها، اگر Hx یک هم مچموعه شناخته شده باشد، Hxg در یک نقطه برای همه اضافه می شود." $g\در X'$ . (این مورد برای تضمین خاتمه الگوریتم ارائه شده مورد نیاز است $|G:H|$ محدود است.)

وقتی همه جداول پر شدند، الگوریتم خاتمه می یابد. سپس ما تمام اطلاعات مورد نیاز در مورد عمل را داریم $جی$ بر روی هم مجموعه از $اچ$ .

همچنین ببینید [ ویرایش ]

گروه کوکستر

منابع [ ویرایش ]

تاد، جی . Coxeter، HSM (1936). "روشی کاربردی برای شمارش مجموعه های یک گروه انتزاعی محدود" . مجموعه مقالات انجمن ریاضی ادینبورگ . سری دوم. 5 : 26-34. doi : 10.1017/S0013091500008221 . JFM 62.1094.02 . Zbl 0015.10103 .
Coxeter، HSM ; موزر، WOJ (1980). مولدها و روابط برای گروه های گسسته . Ergebnisse der Mathematik und ihrer Grenzgebiete . جلد 14 (ویرایش چهارم). Springer-Verlag 1980. ISBN 3-540-09212-9. MR 0562913 .
سرس، آکوس (1997). "مقدمه ای بر نظریه گروه محاسباتی" (PDF) . اعلامیه های انجمن ریاضی آمریکا . 44 (6): 671-679. MR 1452069 .

https://en.wikipedia.org/wiki/Todd%E2%80%93Coxeter_algorithm

+ نوشته شده در جمعه ششم بهمن ۱۴۰۲ ساعت 14:34 توسط علی رضا نقش نیلچی |

ریاضیات

آموزش ریاضی