קורס זה עוסק בתרחיש הבא: נניח שאנחנו מעוניינים לוודא האם הקלט שבידנו מקיים תכונה מסויימת, אולם מותר לנו לקרוא רק חלק קטן מאוד מתוכו. האם עדיין ניתן לתת קירוב מסויים של בעיית ההחלטה? התשובה היא במקרים רבים חיובית – ניתן להבדיל בהסתברות גבוהה בין קלטים שמקיימים את התכונה, לבין קלטים הרחוקים מכל קלט אפשרי אשר מקיים את התכונה. אלגוריתמים כאלו נקראים אלגוריתמי בדיקת תכונות.
בקורס נלמד על אלגוריתמים אלו ומספר שיטות כלליות למציאתם, וכן דוגמאות ושיטות להוכחות של חסמים תחתונים, ובמקרים מסוימים אף אי-היתכנות כוללת.
בקורס נלמד על אלגוריתמים אלו ומספר שיטות כלליות למציאתם, וכן דוגמאות ושיטות להוכחות של חסמים תחתונים, ובמקרים מסוימים אף אי-היתכנות כוללת.
דרישות קדם: קורס הסתברות (094412 או 104222) וקורס אלגוריתמים (234247 או 104291).
רצוי: שיטות הסתברותיות ואלגוריתמים (236374). לאלו שלא לקחו את הקורס יהיו מספר מטלות קריאה מקדימה.
רצוי: שיטות הסתברותיות ואלגוריתמים (236374). לאלו שלא לקחו את הקורס יהיו מספר מטלות קריאה מקדימה.