-
RP
כל מה שרצית לדעת על RP:במדעי המחשב, RP (ראשי תיבות של Randomized Polynomial time) היא מחלקת הסיבוכיות של כל הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי ביחס לגודל הקלט באופן הבא:אם הקלט בשפה, האלגוריתם מקבל בהסתברות של לפחות 1/2.אם הקלט אינו בשפה, האלגוריתם דוחה בהסתברות של 1(כלומר – תמיד).במילים אחרות, האלגוריתם יכול להטיל מטבע בעת ריצתו.…
-
FNP
כל מה שרצית לדעת על FNP:בתורת הסיבוכיות, מחלקת הסיבוכיות FNP היא ההרחבה לבעיית הפונקציה של מחלקת בעיות ההכרעה NP. בעיות רבות ב-NP, ובהן גם מספר רב של בעיות NP-שלמות, שואלות מתי חפץ מסוים קיים, כמו השמה מספקת, צביעת גרף, או מציאת קליקה בגודל מסוים. גרסות ה-FNP עבור בעיות אלה, שואלות לא רק האם קיים פתרון…
-
טיפוס נתונים מופשט
כל מה שרצית לדעת על טיפוס נתונים מופשט:במדעי המחשב, טיפוס נתונים מופשט (Abstract Data Type או ADT) הוא מודל מתמטי עבור קבוצה מסוימת של מבני נתונים בעלי התנהגות דומה, או עבור טיפוסי נתונים שונים בשפות תכנות להם סמנטיקה דומה, ומאפשר הפשטה שלהם. טיפוס נתונים מופשט מוגדר על ידי הפעולות שניתן לבצע עליו ועל ידי מגבלות…
-
TFNP
כל מה שרצית לדעת על TFNP:בתורת הסיבוכיות, TFNP (Total Function Nondeterministic Polynomial) היא מחלקת סיבוכיות המהווה תת-מחלקה של מחלקת הסיבוכיות FNP בה מובטח כי קיים פתרון.יחס בינארי P ( x , y ) {\displaystyle \ P(x,y)} הוא ב-TFNP אם ורק אם קיים אלגוריתם דטרמיניסטי בעל זמן ריצה פולינומי היכול לזהות, בהינתן x ו-y האם…
-
שיטת אכרה-באזזי
כל מה שרצית לדעת על שיטת אכרה-באזזי:במדעי המחשב, שיטת אכרה-באזזי היא שיטה המשמשת לניתוח ההתנהגות האסימפטוטית של יחס נסיגה (רקורסיה), אשר מופיע באנליזה של אלגוריתמי הפרד ומשול שבהם תתי-הבעיות הן בגדלים שונים בצורה משמעותית. השיטה מהווה הרחבה משמעותית של שיטת האב, אשר מניחה שתתי-הבעיות של הבעיה הנתונה הן בגדלים זהים.שיטת אכרה-באזזי תקפה לנוסחאות חוזרות של…
-
התמרת פורייה קוונטית
כל מה שרצית לדעת על התמרת פורייה קוונטית:בחישוב קוונטי, התמרת פורייה קוונטית היא שער קוונטי המבצע התמרת פורייה בדידה. פעולה זו בעלת חשיבות רבה עבור אלגוריתמים שונים בחישוב קוונטי, ובפרט אלגוריתם שור לפירוק לגורמים של מספר שלם, ואלגוריתם למציאת תת חבורה חבויה.בעוד שחישוב התמרת פורייה "קלאסית" על קלט באורך n {\displaystyle n} דורשת ביצוע O…
-
פונקציה חשיבה
כל מה שרצית לדעת על פונקציה חשיבה:בתורת הסיבוכיות, שהיא ענף של מדעי המחשב, פונקציה חשיבה בזמן היא פונקציה f מהמספרים הטבעיים לעצמם, וקיימת מכונת טיורינג שבהינתן קלט n, תשאיר על הסרט שלה בסוף הריצה את הפלט (f(n בזמן ריצה שלא ארוך מ-(f(n. המטרה של הגדרה זו היא לא להתייחס לפונקציות שאין להן חסם עליון על…
-
EXPTIME
כל מה שרצית לדעת על EXPTIME:בתורת הסיבוכיות, מחלקת הסיבוכיות EXPTIME (נקראת גם EXP או DEXPTIME) היא קבוצת כל בעיות ההכרעה הניתנות לפתרון באמצעות מכונת טיורינג דטרמיניסטית בזמן O ( 2 p ( n ) ) {\displaystyle O(2^{p(n)})} כאשר O {\displaystyle O} הוא סימון אסימפטוטי ו p ( n ) {\displaystyle p(n)} הוא פולינום.ניתן גם להגדיר…
-
כריסטוס פאפאדימיטריו
כל מה שרצית לדעת על כריסטוס פאפאדימיטריו:פרופסור כריסטוס חרילאוס פאפאדימיטריו (ביוונית Χρήστος Χαρίλαος Παπαδημητρίου, נולד ב-16 באוגוסט 1949) הוא מדען מחשב ממוצא יווני, העוסק בעיקר בתחום של סיבוכיות חישובית ואלגוריתמים וישומיהם למאגרי נתונים, אופטימיזציות בינה מלאכותית ועוד, וזוכה פרס קנות' לשנת 2002 עבור תרומתו המתמשכת והיסודית לביסוס התאוריה של מדעי המחשב, ובפרס גדל לשנת 2012…
-
מכונת טיורינג לא-דטרמיניסטית
כל מה שרצית לדעת על מכונת טיורינג לא-דטרמיניסטית:כל אלגוריתם ניתן לתיאור על ידי מודל מתמטי מופשט המכונה מכונת טיורינג. בעוד מכונת טיורינג הסטנדרטית היא מכונת מצבים מוגדרת היטב (כלומר, לכל מצב של המכונה ברור באופן מוחלט (דטרמיניסטי) מה יהיה הצעד הבא של המכונה), מכונת טיורינג לא-דטרמיניסטית (Non-deterministic Turing machine, לעיתים מסומנת בקיצור מכונה א"ד) היא…