Recent Forum Posts
From categories:
page 1123...next »
אבי (guest) 28 Feb 2017 15:10
in discussion Discussions / Q&A Fall 2017 » 2016 סמס א' מועד א'

לא משנה, הבנתי.
תודה

by אבי (guest), 28 Feb 2017 15:10
אבי (guest) 28 Feb 2017 15:01
in discussion Discussions / Q&A Fall 2017 » 2015 סמס א' מועד ב'

אני אנסח את השאלה שלי אחרת:
כשרשום "לכל קלט", מדובר על קלט שלם ולא תת מחרוזת של הקלט, לא?

by אבי (guest), 28 Feb 2017 15:01
אבי (guest) 28 Feb 2017 14:43
in discussion Discussions / Q&A Fall 2017 » 2016 סמס א' מועד א'

3.אם<M,w> לא שייך לHTM משלים, אז M עוצרת על w לאחר t צעדים. אבל אם x קטן מt- אז יוצא ש<'M> כן שייכת לL (כי השפה שלה זה SAT)

by אבי (guest), 28 Feb 2017 14:43
אבי (guest) 28 Feb 2017 14:19
in discussion Discussions / Q&A Fall 2017 » 2015 סמס א' מועד ב'

איך מוכיחים ש:
"בריצה על w למשך |M| צעדים המכונה לא קוראת בכלל את התווים הנמצאים בy" ?

הרי המשפט הוא "על כל קלט w שאורכו לכל היותר |M|….". אז אם התנאי הזה לא מתקיים (|y|>|M|) אז אנחנו לא יודעים מה יקרה, לא?
זה לא שהמכונה עוברת על הקלט תו-תו , משמאל לימין ופשוט קוראת אותו. כי למשל , מכונה יכולה לקבל מילה אחרי שקראה שהתו הראשון הוא 0.

by אבי (guest), 28 Feb 2017 14:19

מכיוון שהראש הקורא יכול להימצא בסרט גם על תאים בהם מלכתחילה הופיע blank מספר הקונפיגורציות הוא אינו סופי.

כן אבל לא מקבלים נקודות על הפתרון.

נחלק כל קלט w שאורכו יותר מ|M| לשני חלקים, w=xy כאשר |x|=|M|.
בריצה על w למשך |M| צעדים המכונה לא קוראת בכלל את התווים הנמצאים בy ולכן סדרת הקונפיגורציות שלה לא תלויה בy.
לעומת זאת סדרת הקונפיגורציות שלה ב|M| הצעדים הנ"ל זהה לסדרת של ריצת M על x (כי היא קוראת את אותם קלטים)
ולכן לפי ההנחה, הריצה גם פה תסתיים תוך |M| צעדים.

student (guest) 28 Feb 2017 10:32
in discussion Discussions / Q&A Fall 2017 » שאלה כללית על מוודא

נראה לי ערבבת קצת.
המוודא הוא דטרמיניסטי - אבל הניחוש נעשה ע"י המ"ט ה-א"ד שמכריעה את השפה מ-NP.
המוודא מקבל מילה ועד (סרטיפיקט c שלמשל נוחש ע"י המ"ט הא"ד), והריצה עליו על הקלט הזה צריכה להיות דטרמיניסטית ופולינומיאלית - למשל מוודא הבודק שגרף וקבוצת k קודקודים שקיבל, שהם באמת מהווים בו clique בגודל k. זה מוודא שכפי שהראינו יכול להיות דטרמיניסטי ולרוץ בזמן פולינומיאלי באורך הקלט.

(צוות הקורס תקנו אותי אם אני טועה)

by student (guest), 28 Feb 2017 10:32
by dafnasadehdafnasadeh, 28 Feb 2017 10:24

מעבר לרצף ה-blank האינסופי לאחר סוף המילה, הרי המילה היא סופית.
לכן יש לה מספר קונפיגורציות סופי שהוא |Q|*|gama|*|w|*|sigma|, אם אני לא טועה. אפשר לעבור על זה ולהבין שאם אנו נכנסים לקונ' כלשהי פעמיים אנו ניכנס ללופ אינסופי.
בנוסף אפשר לבדוק כאשר מגיעים לקצה הימני של הסרט האם אנו נכנסים ללופ אינסופי - הרי אם על כל blank שהוא רואה הוא ממשיך ללכת קדימה, אז מן הסתם הוא לא יעצור.

למה אי אפשר להכריע כך עבור כל מילה האם מ"ט עוצרת עליה?

אנחנו לא יודעים לחשב את BB(n) לכל n, אבל הערכים האלו מוגדרים היטב (וקיימים)
ולכן מ.ט שd הערכים הראשונים הנ"ל מקודדים בה (כמו שמוסבר במצגת) יכולה לחשב את הפונקציה

by dafnasadehdafnasadeh, 28 Feb 2017 10:15

מעל כל שאלה ישנה משבצת שאם מסמנים אותה מקבלים נקודות (שרשום לידה "אינני עונה על השאלה").
אם מסמנים אותה ועונים על השאלה בכל זאת - האם עדיין מקבלים את הנקודות על הסימון?

שאלה לגבי נהלי המבחן by student (guest), 28 Feb 2017 10:11
dafnasadehdafnasadeh 28 Feb 2017 10:07
in discussion Discussions / Q&A Fall 2017 » מספר שאלות

אני לא מבינה למה אתה מתכוון, תנסה שהמשפט יוצג באופן ברור יותר.
בכל אופן החיתוך היחידי שמופיע בשקופית הזאת הוא בין סיגמא ל-V.

by dafnasadehdafnasadeh, 28 Feb 2017 10:07

היי לפי ההגדרה שלמדנו מוודא הוא מ"ט דטרמינסטית.
אך ראיתי מספר דוגמאות בהם ניחשנו את C
אז איך ניחוש יכול להיות דטרמנסטי?
בנוסף נתון כי רצה בזמן פולונומיאלי האם הכוונה לריצה על C
או על כל הסדרה של C

שאלה כללית על מוודא by STUDENT (guest), 28 Feb 2017 09:19

שאלה 2:

רשום בפתרון:
"אם על כל קלט w שאורכו לכל היותר |M|, המכונה עוצרת תוך |M| צעדים לכל היותר, אז היא עוצרת על כל קלט (לא חשוב מה אורכו ) תוך מספר צעדים כזה."

למה זה נכון?

2015 סמס א' מועד ב' by אבי (guest), 28 Feb 2017 08:11
דוד (guest) 27 Feb 2017 18:08
in discussion Discussions / Q&A Fall 2017 » 2016 סמס א' מועד א'

2.אבל איך זה מראה שלא ניתן להשתמש ברייס? לא מספיק להגיד שלא ניתן להשתמש ברייס מכיוון שהתכונה הנתונה לנו היא של המכונה ולא של השפה?

3.איפה הפתרון של זה? כל מה שמצאתי זה פתרון סטודנט והוא עשה מHTM ולא מHTM משלים, והוא לא קיבל על הפתרון שלו ניקוד מלא

by דוד (guest), 27 Feb 2017 18:08
אבי (guest) 27 Feb 2017 17:56
in discussion Discussions / Q&A Fall 2017 » שאלות נוספות

1.אז איך מוכיחים שהיא בוודאות קיימת? כרגע זה נראה שהיא לא באמת קיימת, כי היא מתבססת על זה שיש לה את BBn אבל ראינו שאי אפשר לחשב את זה..

by אבי (guest), 27 Feb 2017 17:56
דוד (guest) 27 Feb 2017 17:43
in discussion Discussions / Q&A Fall 2017 » מספר שאלות

1. אבל מדובר על החיתוך בין S שהוא שייך לV ולבין V.. לא בין סיגמא לV

by דוד (guest), 27 Feb 2017 17:43

1. כי אז Lc מכילה גם מ.ט שמכריעות את SAT בזמן לא פולינומי. וזה לא עוזר לפתרון השאלה
2. אםP=NP אז SAT שייכת גם לP ולכן קיימת M1 כמו בפתרון.
3.יש בפתרון רדוקציה מהמשלים לבעיית העצירה

1. לא צריך להגדיר איך בונים מ.ט שמחשבת את הפונקציה. מספיק להוכיח שקיימת אחת כנ"ל.
(הוכחת קיום ללא בנייה)
2. אבל בפתרון מריצים את המכונה Q+1 צעדים, לא Q.

תסתכל ב Forum tips מצד שמאל

by dafnasadehdafnasadeh, 27 Feb 2017 16:16
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License