Get Started. It's Free
or sign up with your email address
Rocket clouds
מדמ"ח by Mind Map: מדמ"ח

1. אלגורתמים

1.1. שונות

1.1.1. חיפוש בינארי

1.1.1.1. מיו ערמה

1.1.1.1.1. נבנה ערמה, ואז נוצא על פעם את המקסימום

1.1.1.2. חיפוש במערך ממויין , עי צמצום בחצי של תווך החיפוש כל פעם

1.1.2. בחירה- מציאת האיבר הi בגודלו במערך

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

1.1.3. RSA הצפנה

1.1.4. GCD מחלק משותף

1.2. מיון

1.2.1. מבוסס השוואות- חסום ל nlogn

1.2.1.1. מיון מהיר

1.2.1.1.1. בוחרים איבר מהמערך- ומעבירם את מי שגדול ממנו לצד אחד וקטן ממנו לצד אחד. על כל תת מערך מבצעים שוב

1.2.1.2. מיון בועות (באבל סורט)

1.2.1.2.1. הפרדה של המערך לשני תתי מערכים ומיון של כל אחד מהם , מיגוז של תתי המערכים

1.2.2. לא מבוסס השוואות (ועם יצא מקדים על הקלט) לינארי

1.2.2.1. מיון בסיס redix

1.2.2.1.1. ממינים ספרה ספרה מהקטן לגדול, כל מיון במיון מניה

1.2.2.2. מיון מניה counting

1.2.2.2.1. יודעים שאיברים בטווח מסויים אז פשוט סופרים לפי אינדקס של מערך אחר כמה בכל אחד ואז מוסיפים

1.3. גרפים

1.3.1. שיכון בזכון- אם מטריצת שכניות או מערך שכניות

1.3.2. חיפוש

1.3.2.1. חיפוש לרוחב BFS

1.3.2.1.1. מתחילים, ומכניסים לתור את כל השכנים, בודקים אם אחד מהם המטרה אם לא ממשיכים מתור (נזכור איפה ביקרנו)

1.3.2.2. חיפוש לעומק DFS

1.3.2.2.1. מתחילים, ומכניסים למחסנית את כל השכנים, בודקים אם אחד מהם המטרה אם לא ממשיכים מתור (נזכור איפה ביקרנו)

1.3.3. מציאת עץ פורס מינימלי MST

1.3.3.1. האלגוריתם של פרים

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

1.3.3.2. האלגוריתם של קרוסל

1.3.3.2.1. ממינים את הקשתות בהתחלה ואז מוספיפים קשר קשר אם היא לא סוגרת מעגל

1.3.4. מציאת מסלול קצר

1.3.4.1. אלגוריתם דייקסטרה

1.3.4.1.1. מאתחלים מרחקים לאין סוף, מתחילים מהקודקוד ועבור כל אחד מהשכנים משנים את המרחק חמינימום בין הקודם ומקור ועוד הצלע. ממשיכים לקודקוד הבא מבין האפשרויות (שכנים עד כה ) בעל משקל מינימלי - כשאין עוד אפשריות סיימנו

1.4. אלגוריתמי שטף

1.4.1. אלגוריתם מיסה גרייס-

1.4.1.1. מציאת איברים שהופיעו n/k פעמים

1.4.1.2. נשמור מערך עם K-1 מקומות, כאשר מופיע איבר בשטף נכניס אותו ואם איבר אחר נוריד לכולם אחד. מי שב0 יוצא. בסוף יהיו חשודים- צריך לעבר שוב ולבדוק

1.4.1.3. במקרה הפרטי שהופיע חצי מהפעים זה עם תא אחד שמוסיף או מוריד ויודעים בטוח

1.5. עקרונות לפתרון

1.5.1. אלגוריתמים חמדניים

1.5.2. תכנון דינאמי

1.5.3. אלגוריתמי קירוב

1.5.4. רשתות זזרימה

2. מבני נתונים

2.1. אבסטרקטי (תיאוריה - לא מימש)

2.1.1. מחסנית

2.1.1.1. אחרון שנכנס ראשון שיוצא

2.1.2. תור

2.1.2.1. ראשון שנכנס - ראשון שיוצא

2.1.3. תור קדימות

2.1.3.1. לכל איבר יש ערך, והאיברים יוצרים לפי ערכם

2.1.4. מילון

2.1.4.1. מפתח וערך, בלי כפילות מפתחות

2.1.5. Union-Find

2.1.5.1. איחוד של קבוצות זרות ובדיקה אם איברים באותה הקבוצה

2.1.5.2. אפשר לממש או ברשמות מקושרות או בגרף (יער)

2.2. מימושים

2.2.1. מערך

2.2.2. רשימה מקושרת

2.2.2.1. שדרודים אפשריים: מצביע לאחור, לראש, איבר ראשון דמי

2.2.3. עץ בינארי

2.2.3.1. עץ חיפוש בינארי- לכל קודקוד כל האיברים בתת העץ השמאלי קטנים ממני ובשמאלי גדולים ממנו

2.2.3.2. עץ AVL עץ חיפוש בינארי מאוזן. שומרים על איזון עם גלגולים

2.2.3.2.1. שיפורים: הוספת המידה לקודוק (כמה איברים מתחתיו) או סכום של איברים שמתחתיו

2.2.4. ערמה

2.2.4.1. בזיכרון יושב במערך שמייצג עץ בינארי כמעט שלם

2.2.4.2. כל אבא גדול (קטן) מבניו

2.2.4.3. פעולות

2.2.4.3.1. תיקון למעלה/למטה

2.2.4.3.2. תיקון של כל מי שלא עלה כלפי מטה

2.2.4.3.3. הוצאת המקסימום- זה הואצאה של השורש. העברת העלה לשורש, ותיקון מטה

2.2.4.3.4. הכנסה- הוספה לסוף ותיקון מעלה

2.2.5. Hash

2.2.5.1. מימוש מילון ע"י טבלת גיבוב ופונקציית גיבוב

2.2.5.1.1. התנגשות סגורה- מבנה נתונים נוסף בתוך התא

2.2.5.1.2. התנגשות פתוחה מציאת פונקציית גיביב נוספת

3. כללי

3.1. זמני ריצה

3.1.1. רגילים: חסם עליון חסם תחתון וחסם הדוק

3.1.2. חישוב זמן ריצה רקורסיבי:

3.1.2.1. או פתיחה וחישוב של הטור

3.1.2.2. משפט האב

3.2. עקרונות במונחה עצמים

3.3. תבניות עצוב