פרויקט בתכנות מתקדם
אלגוריתמים לשחזור עצי אבולוציה
אנו מעוניינים ללמוד את ההיסטוריה האבולוציונית שהובילה להיווצרותה של קבוצת זנים נתונה (בדרך כלל ההתייחסות היא לזנים קיימים). על סמך תורתו של דרווין ניתן לתאר היסטוריה אפשרית כזו בצורת עץ (פילוגנטי), שהוא עץ בינארי שבעליו מופיעים הזנים הנתונים. כל צמת פנימי בעץ כזה מתאר אירוע של התפצלות זן-קדמון אחד לשני זנים. הבעיה של שחזור פילוגנטי על סמך נתונים על הזנים בני זמננו היא אחת הבעיות המרכזיות בביולוגיה חישובית, ויש לה מוטיבציה גם מתחומים רבים אחרים, כמו חקר שפות, ניתוח היסטוריה של תהליכי חישוב, וכו'.
בשלשת העשורים האחרונים נעשה מחקר נרחב בנושא שחזור פילוגנטי, וישנן כיום מספר שיטות ואלגוריתמים לפתרון הבעיה. עם זאת עדיין יש מקום רב לשיפור, ולכן ממשיך המאמץ לפיתוח שיטות יעילות ואו אמינות יותר. בקורס נדון במספר גישות מתקדמות לשחזור עצים פילוגנטים ולאחזקתם, המתבססות על עקרונות פשוטים למדי.
במסגרת הקורס תידרשו לממש (בתכנית מחשב) אחד האלגוריתמים המוצעים, ולבדוק את היישום על קבוצות-מבחן של נתונים. המימוש ייתכן בכל אחת מהשפות- Java, C, C++, Matlab, ואחרות (עם אישור מיוחד). ישנם מספר פרויקטים שונים המוצעים במסגרת הקורס, בעלי אופי שונה ומגוון. בכל אחד מהם מושם דגש אחר על כל אחד מהתחומים:
- תכנון וניתוח אלגוריתמי
- מימוש מושכל של מבנה-נתונים מורכב
- בדיקת ביצועים על נתוני-אמת
בקורס ייערך מפגש היכרות, בו יוצג כל הרקע הדרוש להבנת האלגוריתמים. כמו-כן יינתן תיאור תמציתי של דרישות הפרויקטים, וכל סטודנט יתבקש לבחור באחד. ניתן להגיש פרויקט בזוג. במקרים מיוחדים, ייתכן ויתאפשר להגיש בשלשה. במהלך הסמסטר תיקבענה פגישות-התקדמות (אחת או שתיים) עם כל צוות, על מנת לאפשר לסטודנטים לפרוש את עבודתם בצורה יעילה.
בסוף הסמסטר ייערכו מספר מפגשים בהם יציג כל צוות את הפרויקט שלו (כ-30 דקות למצגת). תאריכים למפגשים אלה ייקבעו במהלך הסמסטר.
הקורס מעניק 3.0 נקודות, והציון ניתן בו ע"פ הסכמה הבאה:
10% - תכנית עבודה
60% - דו"ח סופי וקוד. הציון יחולק פחות או יותר כך:
</P>40% - מענה על דרישות הפרויקט
10% - סדר ותיעוד בקוד המוגש
10% - רעיונות יצירתיים
30% - מצגת סיכום הפרוייקט
דרישות קדם: אלגוריתמים1, ו - מבנה נתונים1
רצוי גם (אם כי לא הכרחי) - אלגוריתמים בביולוגיה חישובית