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

יש סיכוי שקונפיגורציות עוקבות יהיו זהות?<

by טשטש (guest), 28 Mar 2016 12:04

in NP since a guess x can be verified in polynomial [time that in L(G) (lecture 4) and of the length of w]

Re: שאלה ממבחן by marianosmarianos, 26 Aug 2014 20:35
avi (guest) 26 Aug 2014 20:11
in discussion Discussions / Q&A Spring 2014 » שאלה ממבחן

Tomorrow is the exam, and I still didnt get any answer to my question.
Good job roster! you are the best

by avi (guest), 26 Aug 2014 20:11
user (guest) 25 Aug 2014 09:05
in discussion Discussions / Q&A Spring 2014 » 2013, סמסטר ב', מועד ב'

ועכשיו עם יישור לימין:

בשאלה הפתוחה הראשונה (רדוקציה מ-HAM PATH ל-HAMILTONIAN EDGE), האם היה הכרח להוסיף עוד קודקוד? מדוע לא מספיק להוסיף רק קשת שמחברת בין t ל-s כדי שהרדוקציה תהיה נכונה?
ראינו בכיתה רדוקציה מ-HAMPATH ל-HAMCYCLE, שם הוספת הקודקוד (פרט להוספת הקשת) היתה הכרחית, אולם זה לא המקרה כאן לדעתי, כי כחלק מהרדוקציה אנחנו מכריחים את המעגל ההמילטוני לעבור דרך הקשת שאנחנו מוסיפים. כך, אם לא היה מסלול המילטוני מ-s ל-t, לא יוכל להיות מעגל המילטוני שעובר דרך הקשת החדשה, כאשר נחבר קשת כזו בין t ל-s. אם יש מעגל המילטוני שעובר דרך הקשת החדשה שהוספנו, זה אומר שבהכרח יש גם מסלול המילטוני שיוצא מהיעד של הקשת הזו (s) לבין תחילתה (t), כי מעגל המילטוני הוא מסלול המילטוני עם נקודת התחלה וסוף זהה, כך שאם הסרנו את הקשת שהוספנו דרכה עבר המעגל, ושאר הגרף ללא שינוי (כלומר, לא נוספו או הורדו קודקודים), חייב להתקיים כי יש מסלול המילטוני בין s ל-t.

תודה רבה

by user (guest), 25 Aug 2014 09:05

בשאלה הפתוחה הראשונה (רדוקציה מ-HAM PATH ל-HAMILTONIAN EDGE), האם היה הכרח להוסיף עוד קודקוד? מדוע לא מספיק להוסיף רק קשת שמחברת בין t ל-s כדי שהרדוקציה תהיה נכונה?
ראינו בכיתה רדוקציה מ-HAMPATH ל-HAMCYCLE, שם הוספת הקודקוד (פרט להוספת הקשת) היתה הכרחית, אולם זה לא המקרה כאן לדעתי, כי כחלק מהרדוקציה אנחנו מכריחים את המעגל ההמילטוני לעבור דרך הקשת שאנחנו מוסיפים. כך, אם לא היה מסלול המילטוני מ-s ל-t, לא יוכל להיות מעגל המילטוני שעובר דרך הקשת החדשה, כאשר נחבר קשת כזו בין t ל-s. אם יש מעגל המילטוני שעובר דרך הקשת החדשה שהוספנו, זה אומר שבהכרח יש גם מסלול המילטוני שיוצא מהיעד של הקשת הזו (s) לבין תחילתה (t), כי מעגל המילטוני הוא מסלול המילטוני עם נקודת התחלה וסוף זהה, כך שאם הסרנו את הקשת שהוספנו דרכה עבר המעגל, ושאר הגרף ללא שינוי (כלומר, לא נוספו או הורדו קודקודים), חייב להתקיים כי יש מסלול המילטוני בין s ל-t.

תודה רבה

2013, סמסטר ב', מועד ב' by user (guest), 25 Aug 2014 06:29
שאלה ממבחן
avi (guest) 24 Aug 2014 08:19
in discussion Discussions / Q&A Spring 2014 » שאלה ממבחן

given deciding problem:

input: a CFG G and a word w
question: Does exist a word x in L(G) s.t |x|=|w|

a. The problem is undecidable
b. The problem is decidable but we cannot know if it is in NP
c. The problem is in NP
d. None of the above

Why is the correct answer c ?
What is non-deterministic in this problem? I mean, we can decide if |L(G)| is infinite deterministically, no? and then the answer is yes.
And if |L(G)| is finite, then we can generate each possible word in this CFG and check lengths.
I cant see what is non-deterministic here.

שאלה ממבחן by avi (guest), 24 Aug 2014 08:19
Re: moed A
marianosmarianos 23 Aug 2014 23:08
in discussion Discussions / Q&A Spring 2014 » moed A

עלה

Re: moed A by marianosmarianos, 23 Aug 2014 23:08
Re: מבנה המבחן by marianosmarianos, 23 Aug 2014 23:07
מבנה המבחן
שם שלי זה (guest) 23 Aug 2014 18:11
in discussion Discussions / Q&A Spring 2014 » מבנה המבחן

זהה למועד א' מבחינת חלוקת נקודות לשאלות פתוחות וסגורות?

מבנה המבחן by שם שלי זה (guest), 23 Aug 2014 18:11

Input: sets A1…An, and a number k.
Question: does there exist a set C of size k, such that Ai (intersection) C = (not empty set) for every i=1..n?

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

שאלה 4 סעיף א' בתרגיל בית מס' 6 by Itay (guest), 20 Aug 2014 14:56
Student (guest) 19 Aug 2014 21:08
in discussion Discussions / Q&A Spring 2014 » Question 2, 2013 Moed B.

i57_tinypic_com_e1299e_jpg

by Student (guest), 19 Aug 2014 21:08
Question 2, 2013 Moed B.
Student (guest) 19 Aug 2014 21:07
in discussion Discussions / Q&A Spring 2014 » Question 2, 2013 Moed B.

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

האם אפשר לבחור את אותן השפות ולהסיק מכך לתשובה כלשהי?

Question 2, 2013 Moed B. by Student (guest), 19 Aug 2014 21:07
moed A
SIR IISIR II 30 Jul 2014 17:11
in discussion Discussions / Q&A Spring 2014 » moed A

תוכלו להעלות את טופס מועד א גם ללא התשובות? תודה מראש.

moed A by SIR IISIR II, 30 Jul 2014 17:11

Solutions to Moed A published

Passing grade: All the students that received in the final exam a grade of 55-59 got an exam grade of 60.

High grades: For sudents that got 101 or 102 in the exam, we used this for their final grade. Final grade was no more than 100.

Exam - 75% of the grade
Midterm - 15% of the grade
HW - 10% of the grade (best 5 out of 6).

Final grade formulla by Oren SalzmanOren Salzman, 29 Jul 2014 12:26
student (guest) 21 Jul 2014 16:17
in discussion Discussions / Q&A Spring 2014 » פתרון המבחן וציוני תרגילים

I follow the request.
I've also noticed several solutions to ex6 were returned to the copying chamber, though many more were missing.
Are we due to receive all of the ex6 solutions within the following week or two?

Thanks in advance.

by student (guest), 21 Jul 2014 16:17

שלום, רציתי לשאול מתי יעלו את פתרון המבחן ויעדכנו את הציונים של תרגיל בית מספר שש?

פתרון המבחן וציוני תרגילים by I am a question (guest), 20 Jul 2014 12:15

About the procedure of running a Turing machine one step on 0 and then one more stem on 0 and one step on 1 and then one more step on 0 ,one more step on 1 and one step on 10 and then…

There is a simple name that I can call it instead of writing it like that every time I use it ?

Running a Turing machine simultaneously by guest (guest), 17 Jul 2014 17:53
שאלה כללית
שלומי (guest) 17 Jul 2014 11:45
in discussion Discussions / Q&A Spring 2014 » שאלה כללית

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

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

שאלה כללית by שלומי (guest), 17 Jul 2014 11:45

in the solution of exercise 4 question 1b you say:
Halt* <=m ALLTM ( f(<M>)=<M0> where M0 on input y simulates M on input y moving qr when M moves to qa.

shouldn't qr and qa be replaced?

because in this form:
M halts on all inputs »> M0 does not accept anything
M does not halt on all inputs »> M0 don't halts on all inputs and if it halts it rejects.

and in the replaced form:
M halts on all inputs »> M0 accepts anything ( its language is sigma star)
M does not halt on all inputs »> M0 don't halts on all inputs and if it halts it accepts.(its language is not sigma star)

Problem in solution of ex. 4 by Guest (guest), 17 Jul 2014 06:45
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License