הבדלים בין גרסאות בדף "ריצוף של המישור"

מ
מ (r2.6.4) (בוט משנה: pl:Parkietaż)
===בעיות החלטה ואריחי ואנג===
 
השאלה האם יש קבוצה של אריחים בעזרתם ניתן לרצף את המישור, אך לא ניתן לרצפו בצורה מחזורית התעוררה לראשונה בהמשך ל[[הבעיה ה-18 של הילברט|בעיה ה-18]] מ-[[23 הבעיות של הילברט]], ופעם נוספת בשנת [[1961]] כאשר הלוגיקאי [[האו ואנג]] (Hao Wang) עסק ב'''[[בעיית הדומינו]]'''. בעיית הדומינו היא [[בעיית החלטה]], הדורשת לזהות האם סט נתונהנתון של אריחים יכולהיכול לרצף את המישור או לא. ואנג הראה כי ישנו [[אלגוריתם]] הפותר בעיה זו, בתנאי שכל סט סופי של אריחים המרצף את המישור יכול לרצף אותו בצורה מחזורית. החל משנת [[1966]] החלו להתגלות סטים של אריחים שמהווים דוגמאות נגדיות: הם מסוגלים לרצף את המישור רק בצורה לא מחזורית, ואלו נקראים על שמו [[אריחי ואנג]]. קרובה לזה '''בעיית הגרעין''', השואלת אם אפשר לרצף את המישור בסט נתון של אריחים, כשמתחילים מתצורה מסוימת של האריחים.
 
[[תמונה:Robinson tiles.svg|שמאל|ממוזער|250px|אריחי רובינסון]]
3,175

עריכות