משתמש:Marmor/אלגוריתם אונגר
אלגוריתם אונגר, הומצא על ידי אמיר אונגר בתחילת המאה ה-21, פותר את תשבצי הסודוקו הפופולריים בזמן ליניארי. כלומר, בהינתן תשבץ סודוקו עם N משבצות, ניתן לפתורו בזמן . פרסום אלגוריתם זה חולל מהפכה בתחום הסיבוכיות והחישוביות, ובין היתר דירדר את אלן טיורינג לקחת את חייו.
פעולת האלגוריתם
האלגוריתם פועל על חידת סודוקו המכיל מספר כלשהו של משבצות ריקות.
בתמצית ניתן לסכם את פעולת האלגוריתם כך:
אתחול : הכנס את העט לפה, והיראה חושב.
לולאת האלגוריתם:
- עבור כל משבצת ריקה בתשבץ הסודוקו:
- הגרל מספר בין 1 ל-9.
- רשום את המספר במשבצת הריקה.
- מדי פעם היראה חושב, רצוי על ידי בהייה עמוקה בחלל הריק.
- הבט על התשבץ המלא.
- היראה מרוצה מעצמך, אך לא מרוצה מדי.
- העבר דף מהר, לפני שמישהו יחקור את תשובותיך.
רעיון האלגוריתם
מטרת פתירת תשבץ הסודוקו להראות כי אתה חכם יותר משאר האנשים באוטובוס/רכבת/כו', לכן, כל חוקי שיבוץ המספרים בטלים בשישים.
השלכות בעולם המדעי
מעבר ללקיחת חייו של אלן טיורינג כאמור, פרסום אלגוריתם זה הוכיח כי ניתן למיין מערך כלשהו בסיבוכיות קטנה מ- , מה שגרם לסערה בכל תחומי הסיבוכיות, החישוביות ומבני הנתונים. עשרות פרופסורים בעלי שם מרחבי תבל פוטרו ונודו מהחברה האקדמית עקב הטעויות המצטברות שהוכחו לאחר פרסום עבודתו של אונגר.
השפעת האלגוריתם על אונגר
לאחר פרסום האלגוריתם בריאותו הנפשית של אונגר התדרדרה, והוא כיום משקיע את רוב מרצו בפיתוח קפיצת אונגר במשחק הפריזבי, יש הטוענים כי יש לכך קשר לכמויות האדירות של אססולפם K שאונגר נוהג לבלוע מדי יום.