מקצוע מידע על מקצוע : תורת החישוביות ס" - 106843

106843 - תורת החישוביות ס'
נקודות
זיכוי
3.0
 
ניתן
בסמסטר
א+ב+ג
 
עבודת
בית
פרויקט
או סמינר
מעבדה תרגול הרצאה  
  1   1 2 שעות
שבועיות

קביעת הציון עפ"י מעקב במשך הסמסטר ובחינה סופית.


  236343 תורת החישוביות       מקצועות ללא זיכוי נוסף
 
  237343 תורת החישוביות       מקצועות זהים


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


נערך בתאריך 29/01/2022 בשעה 00:22:11