פרמננטה – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בוט משנה: fr:Permanent (mathématiques) |
אלגוריתמיקאי (שיחה | תרומות) ,יקונים שונים (יש אלגוריתם מהיר יותר מהמצוין) ותוספות. |
||
שורה 3:
כאשר הסכום הוא על-פני התמורות <math>\ \sigma \in S_n</math> ב[[חבורת התמורות]]. בפרט, הפרמננטה של מטריצה שרכיביה חיוביים, גם היא חיובית.
בעוד שלדטרמיננטה יש משמעות גאומטרית והיא קשורה ישירות בפתרון [[מערכת משוואות לינארית|משוואות לינאריות]] (על-פי [[נוסחת קרמר]]), הפרמננטה שימושית בהקשרים שונים לחלוטין, כגון חישובי הסתברויות וספירת מסלולים בגרפים. שימוש נוסף הוא בעיית מציאת מספר ה[[שידוך מושלם|שידוכים המושלמים]] ב[[גרף דו צדדי]]. הבדל בולט אחר הוא העבודה שנדרש להשקיע בכל חישוב. למרות שבשני המקרים התוצאה תלויה ב-n [[עצרת]] מכפלות, את הדטרמיננטה אפשר לחשב בכ- <math>\ n^3</math> פעולות
בערכים שיכולה הפרמננטה לקבל עוסקת '''השערת ואן דר ורדן''', שהוצגה ב- [[1926]]. לפי ההשערה, הפרמננטה של [[מטריצה דו-סטוכסטית]] שרכיביה חיוביים נמצאת בין <math>\ \frac{n!}{n^n}</math> (שהוא הערך שלה עבור מטריצה שכל רכיביה <math>\ 1/n</math>) ל- 1. את ההשערה הצליחו להוכיח רק ב- [[1981]], ופותריה זכו בשנה שלאחר מכן ב[[פרס פולקרסון]].
==לקריאה נוספת==
*H. Minc, '''Permanents''', Addison-Wesley, Reading, MA, 1978
* Leslie G. Valiant (1979). "The Complexity of Computing the Permanent". Theoretical Computer Science 8: 189-201
* Mark Jerrum, Alistair Sinclair, Eric Vigoda (2004) [http://doi.acm.org/10.1145/1008731.1008738 "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries"], ''Journal of the ACM,'' Volume 51, Pages 671--697
[[קטגוריה:קומבינטוריקה]]
|