ZPP
ZPP היא קבוצה של בעיות שמתקבלות על ידי אלגוריתם שאף פעם לא טועה. אלגוריתם הסתברותי עושה בחירות אקראיות, כמו הטלת מטבע. תוחלת זמן ריצה היא הזמן הממוצע שהאלגוריתם לוקח. בבעיות מסוימות יש פתרון מהיר שקובע תמיד את אותה תשובה. יש גם אלגוריתמים שמשתמשים באקראיות. חלקם יכולים לטעות לפעמים. ZPP שונה: הוא ת...
מיכאל רבין
מיכאל עוזר רבין נולד ב-1931. הוא מתמטיקאי ישראלי חשוב. משפחתו עלתה לארץ כשהיה ילד. הוא למד בחיפה. בגיל צעיר אהב מתמטיקה. בשנות ה-50 למד באוניברסיטה והמשיך לפרינסטון ללמוד דוקטורט. רבין עבד על רעיונות למחשבים ולתוכנות. הוא והחוקר דנה סקוט המציאו דרך לחשוב על מכונות חישוב. מכונה כזו נקראת אוטומט. או...