FANDOM


20407 - מבני נתונים ומבוא לאלגוריתמים
מדעי המחשב
כללי
רמה: רגילה
נקודות זכות: 6 נ"ז ברמה רגילה
קורסים נדרשים: מבוא למדעי המחשב, מתמטיקה דיסקרטית.
סוגי הנחיה רגילה, מוגברת

לידיעון הקורסים
לאתר הקורס בתלם



נושאי הקורסעריכה

פרק א'עריכה

פרק זה עוסק בחסמים אסימפטוטיים על קצב גידול פונקציות. (o קטן, O גדול, \ \omega קטן, \ \Omega גדול ו\ \Theta) בפרק זה נלמדות הגדרות החסמים ומספר כלים להשוואת קצב הגידול של פונקציות נתונות. (פרקים 1,2 בספר של קורמן)

פרק ב'עריכה

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

(פרק 4 וסעיפים 8.1-8.3 בספר של קורמן)


פרק ג'עריכה

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

(פרק 10 בספר של קורמן)


פרק ד'עריכה

פרק זה עוסק במבנה נתונים המכונה ערימה, ובאלגוריתם מיון הפועל בסדר גודל \ nlog(n) ומנצל את תכונות הערימה. כמו כן, נלמד שימוש של מבנה הערימה כתור עדיפויות.

(פרק 7 בספר של קורמן)


פרק ה'עריכה

פרק זה עוסק בשאלת מיון מערך בזמן לינארי.

תחילה נפתח דיון כללי באלגוריתמי מיון מבוססי השוואות. מוכח שלא קיים אלגוריתם מבוסס השוואות, המסוגל, במקרה הגרוע, למיין סדרה של n איברים בסדר גודל זמן ריצה שמתחת ל\ nlog(n).

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

(פרק 9 בספר של קורמן)


פרק ו'עריכה

פרק זה עוסק במבני נתונים בסיסיים כדוגמת:

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

(פרק 11 בספר של קורמן)


פרק ז'עריכה

פרק זה עוסק בטבלאות גיבוב ויישומיהן.

(סעיפים 12.1-12.3.3 בספר של קורמן)


פרק ח'עריכה

פרק זה עוסק בעצי חיפוש בינאריים.

(סעיפים 13.1-13.3 בספר של קורמן)


פרק ט'עריכה

פרק זה עוסק בעצים אדומים־שחורים - גרסא של עצי חיפוש בינאריים אשר דואגת לשמור על גובה העץ חסום על ידי \ O(log(n)).

(פרק 14 בספר של קורמן)


פרק י'עריכה

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

(סעיפים 16.1-16.3 בספר של קורמן)


פרק יא'עריכה

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


(סעיפים 17.1-17.3 בספר של קורמן)


פרק יב'עריכה

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

(פרק 18 בספר של קורמן, להוציא סעיף 18.4.2)

הבחינהעריכה

מבנה הבחינהעריכה

חומר עזרעריכה

בבחינה כל חומר עזר מותר לשימוש.

קישורים חיצוניים עריכה

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

ברחבי אתר Wikia

ויקי אקראית