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

קובץ של תירגול 6 באתר לא נפתח…מוחזרת שגיאה

תקלה בקובץ של תירגול 6 by גיא (guest), 08 May 2012 21:05

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

by michal (guest), 19 Sep 2011 23:00

moed b and some answers can be now found under "Exam".
Ori

Exam moed B by Ori LahavOri Lahav, 11 Sep 2011 17:01

היי
יש אפשרות לפרסם את הפתרונות של המועד ב?

פתרונות למועד ב by aaa (guest), 07 Sep 2011 07:23
Exam
Ori LahavOri Lahav 21 Jul 2011 07:22
in discussion News / Course News, Spring 2011 » Exam

The last exam and brief solution can be now found under "Exam".
Ori

Exam by Ori LahavOri Lahav, 21 Jul 2011 07:22

האם יפורסמו?

פתרונות לבחינה by Idoן (guest), 20 Jul 2011 14:06

Here are the grades of the 6 exercises for the students who took Moed A.
Non submission counts as 0.

PDF

Ori

Exercise grades by Ori LahavOri Lahav, 11 Jul 2011 20:24
Spectator (guest) 02 Jul 2011 15:59
in discussion Discussions / Q&A, Spring 2011 » 2009 b moed a open question 2 b

Maybe i didn't understand write the "disjoint nodes" property…

by Spectator (guest), 02 Jul 2011 15:59
Spectator (guest) 02 Jul 2011 15:56
in discussion Discussions / Q&A, Spring 2011 » 2009 b moed a open question 2 b

I didn't understand your example. what's wrong with it? each node has 2 edges entering it, and there is IS of 3 nodes.

by Spectator (guest), 02 Jul 2011 15:56
dror (guest) 02 Jul 2011 15:47
in discussion Discussions / Q&A, Spring 2011 » 2010 מועד א סמסא שאלה 13

nop … 3DNF is P, since you need to satisfy only 1 clause, which has 3 literals.

you can make polynomial reduction from P to NPC since P is in NP
but you cannot make polynomial reduction from NPC to P, since each L in NPC is also in NPhard, and there is no polynomial reduction from NPhard to P

by dror (guest), 02 Jul 2011 15:47
dror (guest) 02 Jul 2011 15:31
in discussion Discussions / Q&A, Spring 2011 » 04.07.2010 Q9

notice that a language is polynomial if it's solution is polynomial relative to the input.

since your input is exponential, and you can find an exponential solution, the ratio is polynomial.

by dror (guest), 02 Jul 2011 15:31

למה התשובה היא רק א? למה הרדוקציה בב' לא נכונה, הרי IP היא NP קשה וכך גם 3DNF, לא?

2010 מועד א סמסא שאלה 13 by dddw (guest), 02 Jul 2011 15:27
dror (guest) 02 Jul 2011 14:52
in discussion Discussions / Q&A, Spring 2011 » 2009 b moed a open question 2 b

I don't think it's a correct solution.
take for an example a triangle graph where each "node" is replaced by a circle.

you've got 3 simple circles who are disjoint with nodes with degree different from 2.
your reduction will fail, even though it's a correct one …

think of it in a simpler way: what reduction have you been doing if it was only 1 simple circle ? how can you make 3 out of 1 ?

by dror (guest), 02 Jul 2011 14:52

Is the following solution right:

1 step - Check if all the nodes in the graph have exactly 2 edges enter\exit them. If not, either there is an edge that not part of a circuit, either there is an edge visited more than twice (within it's own circuit or an other circuit). So, if not, just reject.
2 step - Apply IS (G, 3). If there is an independent set of size 3, we have 3 different circuits.

2009 b moed a open question 2 b by Spectator (guest), 02 Jul 2011 12:45
Dror Z. (guest) 02 Jul 2011 11:32
in discussion Discussions / Q&A, Spring 2011 » formula page- corrections !!!!

לגבי סעיף 3, קו-אנ-פי צריך להיות מוכל באנ-פי.

by Dror Z. (guest), 02 Jul 2011 11:32

1. in decidable languages: under definition of checker: "… M on w." and not "… M on M."
2. examples of languages: under "not in RE nor coRE": ALLtm = {M| M is a TM and M accept every x}
3. complexity: theorem: " if L belongs to coNPhard and NP then NP < coNP" not equale, but MUCHAL (as {1,2} < {1,2,3})
4. IS and/or Clique : belongs to NPhard: switch between union and intersection:
עושים רדוקציה מקליק. עבור ** החיתוך** נעשה גרף חדש …. כעת בהכרח תהיה קבוצה בגודל לפחות קיי של אינדפנדס סט …. עבור האיחוד, יוצרים עוד וי צמתים …..

that's it …. sorry, I had too much to check in it, so I missed these ones ….

a lot of thanks to dror Z.
sincerely yours,
dror P.

formula page- corrections !!!! by dror (guest), 02 Jul 2011 11:23
Dror Z. (guest) 02 Jul 2011 11:17
in discussion Discussions / Q&A, Spring 2011 » 10/2/10 שאלה 6

אני חושב שהיה כאן שרשור על שאלה דומה. שימי לב שבעית ההכרעה הראשונה, באופן לא פורמלי היא "האם מכונה M מתנהגת כמו LBA? (עד כדי קבוע c)" - וזו בעיה לא כריעה. אינטואיטיבית בגלל שצריך לוודא נכונות עבור כל הקלטים האפשריים. פורמלית, בגלל שקיימת רדוקציה חשיבה מA_TM משלים (זה בדיוק מה שעשינו בתרגיל בית 5).

את הבעיות האחרות יהיה יותר קל להסביר באמצעות דוגמא: נניח c=10, אז לצורך העניין עבור כל הקלטים באורך 100, צריך לוודא שהמכונה לא עוברת את התא ה90 (בבעיה השניה) או את התא ה11 (בבעיה השלישית). אבל בעצם אפשר להחיל את אותו עקרון גם על קלטים באורך 90 או 11 - צריך לוודא שהמכונה לא עוברת את התא ה80 או ה2 (בהתאמה), וכן הלאה…כך שבסופו של דבר שתי הבעיות הללו שואלות אותו דבר: "האם מכונה M לא עוברת את התא הראשון?" וזה כמובן כריע.

by Dror Z. (guest), 02 Jul 2011 11:17
Henry Gordon Rice (guest) 02 Jul 2011 11:14
in discussion Discussions / Q&A, Spring 2011 » TM that moves always right

I meant *Dershowitz

lol

by Henry Gordon Rice (guest), 02 Jul 2011 11:14
Henry Gordon Rice (guest) 02 Jul 2011 11:13
in discussion Discussions / Q&A, Spring 2011 » TM that moves always right

*Mansour

by Henry Gordon Rice (guest), 02 Jul 2011 11:13
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License