פורטל הסטודנטים

מכונות טורינג. מודלי חישוב שונים ושקילותם למכונות טורינג. התזה של צ'רץ. מושג המכונה האוניברסלית. בעיות בלתי כריעות. סיבוכיות זמן וסיבוכיות מקום. מושג הרדוקציה והרדוקציה הפולינומית. חסמים לחישוב דטרמיניסטי והקשר ביניהם. משפט קוק. תוצרי למידה:הסטודנט יהיה מסוגל: 1. להכיר מודלים חישוביים עיקריים וידע לנתח את מאפייניהם ואת ההבדלים ביניהם. בין היתר ידון במכונת טיורינג, מכונת מחסנית, מכונה אוניברסלית, מכונה דטרמיניסטית/לא דטרמיניסטית. 2. להכיר רמות קושי שונות בהיתכנות לפתור בעיות וידע להבחין בין מחלקות קושי עיקריות: NP-HARD, NP-COMPLETE, P 3. לדעת את מגבלות כח החישוב של המחשב וידע להבחין בין בעיות כריעות לכאלה שאינן כריעות. 4. לדעת לנתח ולתאר תכונות עיקריות של תוכנה וחומרה באמצעות מאפיינים מתמטיים.

פקולטה: מתמטיקה
|תואר ראשון |תארים מתקדמים

מקצועות ללא זיכוי נוסף

236343 - תורת החישוביות 237343 - תורת החישוביות