Recent Forum Posts
From categories:
page 1123...next »

למה יש צורך להוסיף את
u1,u2?

dתרגיל בית 6 שאלה 1 by Student (guest), 27 Aug 2013 16:27

אנונומטר משמש למדידת מהירות וכיוון רוח
אנומרטור הוא מונה

by עדיף מאוחר (guest), 27 Aug 2013 06:07

למישהו יש את המבחן ואולי גם פתרון?
אם כן, שלחו בבקשה ל
aviran AT gmail . com

(המערכת לא נותנת לפרסם מייל בפורמט הרגין…)

למישהו יש את המבחן של סמסטר א? by aviran (guest), 26 Aug 2013 10:59

צודק פספסתי את החלק הזה בהגדרה שגודל הזיכרון נקבע לפי הקלט
ואחרי זה זה ברור
תודה

by ליאור (guest), 10 Aug 2013 17:56

יש לשים לב כי LBA
היא מ"ט שאסור לה לחרוג מהתא הריק הראשון אחרי הקלט.

למשל אם הקלט הוא בגודל n
אז למכונה אסור להגיע למקום ה- n+1

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

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

כעת נראה לי שזה ברור למה לא ניתן לקבוע את כל המילים שנמצאות ב LBA:
כדי לעשות זאת צריך לסמלץ את המכונה על אינסוף קלטים !

by student (guest), 10 Aug 2013 10:25

כל שפה LBA :
אפשר להכריע כל מילה אם היא נמצאת בשפה או לא כפי שלמדנו על ידי חישוב כמות הצעדים המקסימלי שלא יגרום לקונפיגורציה לחזור על עצמה
יש מספר סופי של מילים שנכנסות בסרט החסום (נגיד מספר האותיות בחזקת אורך הסרט)
לכן אפשר לייצר לכל מכונה חסומת סרט את כל המילים שנמצאות שם (כנראה שלא… וזה השאלה שלי בעצם)
למה אי אפשר לדעת את כל המילים מראש לכל LBA

כי אז אני יכול להגיד למשל EQ LBA יהיה כריע
ולפי השעורי בית זה לא כריע

guest (guest) 07 Aug 2013 14:32
in discussion Discussions / Q&A Spring 2013 » תשובות לשאלות הסגורות

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

זה בהנחה שאתה רוצה רק את התשובות א', ב' או ג'…

אם אתה מחפש את ההסבר (כמוני למשל) - אז אכן נבקש שתעלו הסברים גם לחלק הזה

תודה

by guest (guest), 07 Aug 2013 14:32

שלום רב,
תוכלו לפרסם את התשובות לשאלות הסגורות א.3, כך שנוכל להשוות עם תשובותינו?

תודה :-)

תשובות לשאלות הסגורות by Anonymous (guest), 06 Aug 2013 19:49

Solutions to Moed A published

In "General Information" Tab.

Final Grade Computation by marianosmarianos, 05 Aug 2013 20:54
guest (guest) 25 Jul 2013 19:30
in discussion Discussions / Q&A Spring 2013 » רדוקציה פולינומיאלית

נו ומה הבעיה ?
B יכולה להיות ב-P

by guest (guest), 25 Jul 2013 19:30
Tomer (guest) 25 Jul 2013 18:37
in discussion Discussions / Q&A Spring 2013 » רדוקציה פולינומיאלית

לא. אם היה, היינו מבצעים את הרדוקציה בזמן פולינומיאלי, מכריעים בזמן פולינומיאלי ומחזירים את התשובה הנכונה.

by Tomer (guest), 25 Jul 2013 18:37
anonymous (guest) 25 Jul 2013 18:20
in discussion Discussions / Q&A Spring 2013 » NP intersection co-NP = P ?

על-פי השקף הראשון של הרצאה 10, והאינטרנט (לדוגמא בחיפוש NP intersect coNP, אני לא יכול לפרסם לינקים…), לא ברור אם $NP\cap co-NP = P$ או ש-$NP\cap co-NP \supset P$

by anonymous (guest), 25 Jul 2013 18:20

האם ייתכן :
A IN P
B IN NP
THERE IS POLYNOMIAL TIME REDUCTION FROM B TO A ?

רדוקציה פולינומיאלית by guestt (guest), 25 Jul 2013 14:12

האם מתקיים
P = NP intersection co-NP ?

תודה

NP intersection co-NP = P ? by guest (guest), 25 Jul 2013 14:08

תודה :)

by anonymous (guest), 25 Jul 2013 13:09

P מוכל ב-NP
P מוכל ב-coNP
NP מוכל ב-R
coNP מוכל ב-R
(ונובע מזה שגם P מוכל ב-R)

מה שאין זה קשר הכלה בין RE, coRE, R לבין NP-Hard, coNP-Hard

עסקנו בקורס במחלקות R,RE,CORE ובמחלקות P,NP,CONP - בעיקר בנפרד.

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

עד כמה שאני הבנתי:
R וRE - מדברים על שפות שהן כריעות/כריעות-למחצה, אבל לא מדברים בכלל על הזמן שלוקח להכריע אותן. כלומר: יכולה להיות שפה בR, שהיא כריעה, אבל הזמן שלוקח להכריע אותה הוא אקספוננציאלי באורך הקלט, ולכן השפה הזו לא בP…
P - שפות שאפשר להכריע בזמן פולינומי.
NP - שפות שאפשר "להכריע" באופן לא-דטרמיניסטי בזמן פולינומי.

לכן לא מתקיים שR מוכל בP, או שRE מוכל בNP, או משהו בסגנון. נכון ?
האם יש יחס הכלה כלשהו בין שפות בשני הצדדים ?

אשמח להבהרה של המתרגלים/מישהו שהצליח להבין את העניין …

תודה

הקשר בין RE, R, co-RE לבין P,NP,co-NP by omer (guest), 25 Jul 2013 12:32
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License