תכנות אתרים ומדריכים

שימוש באלגוריתם גנטי להתמודדות עם בעיה חישובית קשה במיוחד ממחלקת NP

21.12.2023 | מדריך למידת מכונה | יוסי בן הרוש

אין דבר מהנה יותר ממציאת פתרון אלגנטי לבעיות תכנותיות. במיוחד אם הם קשות ומסובכות ופתרונם מצריך מאמץ רב. אולם קיימות בעיות תכנותיות שהם כל כך מורכבות עד שגם המחשבים החזקים ביותר מתקשים למצוא להם פתרונות בזמן סביר. בעיות אלו שייכות למחלקה NP - בעיות שאין להם פתרון דטרמיניסטי בזמן פולינומי. דוגמה לבעיה מסוג NP היא בעיית התרמיל 0/1 - אשר נחשבת לאתגר אופטימיזציה קלאסי. הבעיה דורשת למקסם את הערך הכולל תחת מגבלות משקל, והיא הולכת ומסתבכת ככל שגדל מספר הפריטים. הסיבוכיות נובעת מכך שככל שגדל מספר הפריטים אותם ניתן לבחור להכניס לתרמיל, גדל מספר השילובים האפשריים באופן אקספוננציאלי כיוון שכל פריט מוסיף שתי אפשרויות (להכניס או להוציא), מה שמוביל ל-2^n שילובים פוטנציאליים עבור n פריטים. מורכבות אקספוננציאלית זו מאפיינת בעיות רבות השייכות למחלקה NP. כיוון שפתרון מיטבי של מקרים מרובי פריטים של בעיית התרמיל לא קיים למעשה, מומחי התכנות פונים לשימוש באלגוריתמים מקורבים שאף שאינם מבטיחים פתרונות מיטביים, הם כן מצליחים לספק תוצאות טובות למדי במסגרת טווחי זמן סבירים. דוגמה אחת היא שימוש באלגוריתם גנטי לצורך מציאת פתרונות מקורבים לבעיה. אלגוריתמים גנטיים, אשר שואבים השראה מתחומי האבולוציה והגנטיקה, עושים שימוש במנגנונים של ברירה, שחלוף, ומוטציה כדי לאפשר לאוכלוסייה של פתרונות פוטנציאליים להתפתח לאורך דורות. בעוד שפתרון האופטימלי אינו מובטח, אלגוריתמים אילה חוקרים ביעילות מרחבי פתרונות עצומים. היישום במדריך של האלגוריתם הגנטי לבעיית התרמיל מדמה את האבולוציה של אוכלוסיות. הוא משלב אסטרטגיות כגון יצירה ושמירה על שונות, ברירת פרטים לפי מידת כשירות, יישום של שחלוף לצירוף חומר גנטי, והכנסת מוטציות לשיפור השונות. אסטרטגיות אילו, בדומה לתהליכים טבעיים, מנווטות במרחב החיפוש, ומתכנסות לפתרונות העומדים בדרישות הבעיה או לפחות מתקרבות לפתרון אופטימלי. שיפורים נוספים, הכוללים אליטיזם והתאמה דינמית של שיעורי השחלוף, נועדו לשפר את ביצועי האלגוריתם. בנוסף, המדריך ידגים קריטריוני התכנסות כדי לקבוע מתי האלגוריתם הגנטי צריך לסיים לחקור עקב תשואה פוחתת של השיפור במידת הכשירות במעבר בין הדורות.

חידה תכנותית: מציאת הפריטים הקרובים ביותר לערך מטרה בתוך מערך

16.12.2023 | מדריך פייתון | יוסי בן הרוש

נתון לך מערך `arr` של מספרים שלמים ממוינים בסדר עולה מהפריט הנמוך לגבוה, וערך מטרה `target`. עליך למצוא את k הפריטים הקרובים ביותר לערך המטרה במערך. במקרה של שוויון יש להעדיף את הפריטים הקטנים יותר.

מדריך sed לעריכת טקסט שורה אחת בכל פעם

08.12.2023 | מדריכי לינוקס | יוסי בן הרוש

sed הוא כלי לעיבוד של טקסטים כשעובדים על מערכת הפעלה לינוקס. sed קיצור של Stream EDitor הוא עורך טקסט שמעבד מידע שורה אחת בכל פעם. משתמשים ב-sed כשעובדים עם טקסטים שמקורם בפייפ או בקובץ ורוצים לעשות להם מניפולציות פשוטות דוגמת: חיפוש, החלפה, סינון, עריכה, מחיקה. היתרון של שימוש ב-sed הוא שידע של כמה אפשרויות בסיסיות יכול לחסוך הרבה זמן עבודה בפרט אם רוצים לבצע פעולות אוטומטיות על קבצי טקסט. sed הוא שימושי במיוחד כשעובדים על קבצי לוג.

חידה תכנותית : מציאת האב המשותף הנמוך ביותר LCA בעץ בינארי

01.12.2023 | מדריך פייתון | יוסי בן הרוש

האב המשותף הנמוך ביותר (LCA = Lowest Common Ancestor) של שני צמתים השייכים לעץ בינארי, p ו-q, הוא הצומת הרחוק ביותר משורש העץ שיש לו את שני הצמתים כצאצאים. עליך לכתוב פונקציה שמוצאת את ה-LCA של עץ נתון עבור שני הצמתים: p ו-q.

סקריפט סימולציית מונטה קרלו להערכת השקעה

24.11.2023 | מדריך למידת מכונה | יוסי בן הרוש

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

חידה תכנותית: סידור של תלוית

17.11.2023 | מדריך פייתון | יוסי בן הרוש

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

חידה תכנותית: מכפלת כל הפריטים במערך מלבד הנוכחי

10.11.2023 | מדריך פייתון | יוסי בן הרוש

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

חידה תכנותית: כמה דרכים שונות לטפס מדרגות

03.11.2023 | מדריך פייתון | יוסי בן הרוש

בגרם מדרגות נתון יש מספר של N מדרגות. ניתן לטפס מדרגה אחת או שתיים בכל פעם. מהו מספר הדרכים לטיפוס לראש גרם המדרגות?

קישורים וטלפונים לעת מלחמה

28.10.2023 | כישורי חיים | יוסי בן הרוש

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

חידה תכנותית: תת מערך בעל סכום מירבי

27.10.2023 | מדריך פייתון | יוסי בן הרוש

בהינתן מערך של מספרים שלמים `nums`, עליך למצוא תת מערך רציף שסכום פריטיו הוא הגבוה ביותר.