קורס מלא, מקור-אחר-מקור
להבין סיבוכיות. לא רק לשנן הוכחות.
מסלול דו־לשוני מתורת החישוב ועד NP-שלמות, קירוב, אקראיות וסיבוכיות מקום — עם הסברים, פתרונות והמחשות אינטראקטיביות.
362 PDF + 4 books
מפת מקורות עם הפניות לעמודים
11 יחידות
מהבסיס ועד PH ואורקלים
HE ⇄ EN
מסלול מקביל ומלא בשתי שפות
מפת הקורס
כל נושא בנוי על קודמו, עם הגדרות מדויקות, אינטואיציה, הוכחות ותרגול.
ההתקדמות שלך0 מתוך 11
- דרישות קדםחישוביות, לוגיקה, גרפים, אסימפטוטיקה והסתברות.
- מודלים ומשאביםמכונות טיורינג, קונפיגורציות, זמן ומקום.
- מחלקות דטרמיניסטיותDTIME, DSPACE, משפטי היררכיה והכלות יסוד.
- אי־דטרמיניזםעצי חישוב, NTIME/NSPACE, סימולציה וריפוד.
- NP ו־coNPעדים, מוודאים, משלים ושאלות פתוחות.
- רדוקציות ושלמותרדוקציות קארפ, NP-קושי ומשפט קוק–לוין.
- בעיות קנוניותSAT, בעיות גרפים, מספרים, מסלולים וצביעה.
- אופטימיזציה וקירוביחסי קירוב, Vertex Cover, Max-Cut, TSP ו־Bin Packing.
- אקראיותRP, BPP, הגברת הסתברות, Freivalds ו־Karger.
- סיבוכיות מקוםL, NL, משפט סביץ׳, רדוקציות לוגריתמיות ו־coNL.
- מבנה מתקדםההיררכיה הפולינומית, אורקלים ומחלקות יחסיות.