תרגילי השלמה לשבוע 4
- המפספסים תרגיל 1 בלבד – מתבקשים לפתור רק את תרגיל מספר 1.
- המפספסים שני תרגילים – מתבקשים לפתור את תרגיל 1 ואת תרגיל 2.
תרגיל 1
עץ פילוגנטי או עץ אבולוציוני הוא גרף בצורת עץ המייצג את היחסים ההיסטוריים-אבולוציונים המשוערים בין מינים ביולוגים שונים על סמך דמיון גנטי או מורפולוגי ביניהם. (ויקיפדיה)
נסמן את האב המשותף הקדמון ביותר בתור המילה LUCA, ונביט על העץ הפילוגנטי הבא (הפרחים והתודות לוויקיפדיה):
בתרשים זה, נוכל להגיד ש־Chlorobacteria יורשת ישירות מ־LUCA, וכך גם Gracilicutes ו־Eurybacteria.
לעומת זאת, Endobacteria יורשת ישירות מ־Eurybacteria אך יורשת בעקיפין מ־LUCA.
אפשר להגיד על Neomura שהיא יורשת ישירות מ־Actinobacteria, ויורשת בעקיפין מ־Eurybacteria ומ־LUCA.
נתאר את העץ בעזרת הקובץ הבא:
Chlorobacteria -> LUCA
Hadobacteria -> LUCA
Cynaobacteria -> LUCA
Gracilicutes -> LUCA
Eurybacteria -> LUCA
Endobacteria -> Eurybacteria
Actinobacteria -> Eurybacteria
Neomura -> Actinobacteria
Eukarya -> Neomura
Archaea -> Neomura
- קבלו נתיב לקובץ בתצורה שהודגמה מעלה, שמתאר עץ פילוגנטי. הקובץ יכול להכיל עד 1000 שורות. מצאו כמה ירושות עקיפות יש בסך הכל בקובץ. לדוגמה, בעץ שהוצג מעלה יש 10 ירושות עקיפות.
- המרחק בין Eukarya לבין Endobacteria הוא 3 פסיעות. המרחק בין Eukarya ו־Chlorobacteria הוא 4 פסיעות. המרחק בין Gracilicutes לבין Hadobacteria הוא פסיעה אחת (בייצוג עצי תקין, בניגוד לתמונה, שניהם יוצאים מ־LUCA). כתבו פונקציה שמקבלת שמות של 2 מינים ביולוגיים ומוצאת את המרחק ביניהם.
שימו לב: השאלה תוקנה ב־2020-05-08. מי שפתר בדרך הישנה – גם תשובתו תתקבל.
תרגיל 2
(תודה לנגה אוסין)
אתם אחראיים על השידור החי של “ג’וק, סמור, בֹּנֶה”, אשר יוקרן לקהל עצום על מספר ענקי של מסכי טלוויזיה שהוצמדו אחד לשני מבעוד מועד. על מנת לעשות קצת סדר, חילקתם את המסכים בין מפעילים שונים, כשלכל אחד תחום אחריות משלו. בתחילת ההקרנה, כל המפעילים ידליקו את המסכים שתחת אחריותם בו־זמנית.
אך אבוי! רגע לפני השידור, שמתם לב שחלק מהאזורים חופפים, כלומר מסכים מסוימים יקבלו פקודה משני מפעילים בו זמנית. אם דבר כזה יקרה, המסך ישבוק חיים וכל השידור עלול להיהרס. על מנת להבין את היקף הבעיה, ממשו פונקציה אשר מחזירה את מספר מסכי הטלוויזיה אשר צפויים לא לעבוד. הכל תלוי בכם!
הרישום של איזה מפעיל אחראי על איזה אזור נראה כך:
1,3: 4x4
3,1: 4x4
5,5: 2x2
בצורת כתיבה זו, נסתכל על צד שמאל (1,3 בשורה הראשונה) בתור נקודת ההתחלה. ניתן לדמיין אותה בתור ראשית הצירים, ואת מסכי הטלוויזיה בתור הרביע הרביעי. בדוגמה מעלינו, המלבן יתחיל פסיעה אחת ימינה מנקודת ההתחלה, ושלוש פסיעות למטה .
צד ימין (4x4 בשורה הראשונה) יציג את רוחבו וגובהו של המלבן, כאשר הרוחב משמאל ל־x והגובה מימינו.
ראוי לציין כי כל האזורים המוקצים הנם מלבניים, וכולם מורכבים ממסכי טלוויזיה בגודל 1x1.
האם שמתם לב להתנגשות בין האזורים בדוגמה למעלה?
ננסה לצייר כל תחום, כאשר המסכים מסומנים בהתאמה למספר השורה שבדוגמה:
........
...2222.
...2222.
.11XX22.
.11XX22.
.111133.
.111133.
........
כמו שוודאי ראיתם, ישנו ריבוע במרכז אשר מורכב מאיקסים. במקרה זה, הוא מייצג את התנגשות המלבנים המוגדרים בשורה הראשונה ובשנייה.
הרישום שתעשו בפועל, כמובן, יהיה הרבה יותר גדול מזה.
שימו לב! מספר מסכי הטלוויזיה אינו ידוע, ואין להגדיר גודל קבוע למען פתרון התרגיל.
בחנו את עצמכם: מספר המסכים אשר יקבלו יותר מפקודה אחת הוא 701 (תיקנו, תודה).
9,222: 19x20
62,876: 28x29
8,156: 17x18
73,337: 24x24
13,834: 20x23
75,523: 20x13
7,7: 11x27
2,512: 11x17
07,525: 27x20
47,742: 21x25
154,740: 28x25
808,793: 28x24
249,936: 13x11
93,400: 8x9
295,894: 17x22
535,885: 8x5
878,268: 13x11
152,685: 28x24
152,639: 22x26
905,560: 23x27
962,104: 19x12
125,145: 19x22
260,488: 13x21
179,815: 12x24
661,595: 4x6
584,97: 10x15
869,842: 11x19
491,825: 19x25
639,935: 10x28
583,26: 11x13
956,264: 22x17
168,706: 22x21
10,81: 29x18
751,214: 16x21
830,200: 17x20
587,580: 18x20
749,587: 10x13
546,376: 28x25
222,945: 11x28
43,937: 14x27
53,108: 25x21
669,894: 28x28
598,390: 23x25
440,136: 24x28
657,50: 16x13
134,155: 15x28
873,580: 28x16
519,287: 23x24
283,691: 12x20
78,660: 11x23
220,650: 24x21
722,671: 11x11
130,554: 12x26
248,423: 28x20
545,884: 10x3
926,657: 21x13
207,925: 22x27
813,292: 17x24
951,143: 23x25
582,397: 18x19
947,119: 14x24
874,701: 12x10
57,682: 10x18
450,510: 11x28
820,700: 27x17
231,114: 13x15
434,283: 22x18
489,743: 23x28
608,782: 10x24
297,896: 23x29
240,664: 13x29
96,953: 26x28
520,21: 21x25
878,207: 16x21
31,408: 19x26
846,419: 6x19
754,602: 17x29
95,621: 27x27
50,391: 10x24
915,362: 27x22
743,524: 25x23
41,58: 11x26
242,800: 27x21
525,652: 15x26
507,865: 18x26
855,272: 29x28
343,718: 12x13
405,628: 18x28
479,608: 20x13
752,934: 26x24
25,99: 14x12
909,952: 25x26
425,523: 27x12
345,586: 29x27
642,240: 16x10
369,567: 26x24
483,770: 23x10
745,683: 27x19
601,817: 16x21
793,153: 13x23
סגירת תרגילי ההשלמה תתבצע בראשון בשעה 18:00, ולא דקה אחרי.