בתחילת שנות התשעים הגיעה לראשונה דיפ פרפל לישראל לשתי הופעות, ההופעה הראשונה נערכה ב-28 בספטמבר 1991 בפארק הירקון שבתל אביב וההופעה השנייה, אשר סגרה את סיבוב ההופעות של הלהקה, נערכה למחרת בחוף צמח, שבכנרת. הביקורות שפורסמו על המופע היו שליליות, והגדירו אותו כבלתי מוצלח, בלשון המעטה. ביצועיו של הסולן, ג'ו לין טרנר (שהחליף את איאן גילן באותה עת), היו בלתי מספקים. כמו כן, במהלך ההופעה האחרונה שבחוף צמח, לפני ההדרן, ירד מהבמה ריצ'י בלקמור, גיטריסט הלהקה, ולא הסכים לחזור, למרות קריאות הקהל. לפי גרסה אחת, הוא נבהל מכך שרבים בקהל אחזו "סטיקלייטים" זוהרים, ולפי גרסה אחרת, נזרקו לבמה בובות של דובים, שהבהילו אותו. בספטמבר 2008 הגיעה הלהקה להופעות בישראל בפעם השנייה, והופיעה ארבע פעמים. הופעה אחת נערכה ב"האנגאר 11" שבנמל תל אביב, ושלוש האחרות בתיאטרון קיסריה. ההופעות זכו להצלחה רבה ולביקורות אוהדות, וכל הכרטיסים עבורן נמכרו מראש.
במאי 2011, הגיעו חברי הלהקה בפעם השלישית לישראל, לשתי הופעות בתיאטרון קיסריה. בריאיון עמם, סיפרו חברי הלהקה, כי הם מעט עצובים על הידרדרות מעמד להקות הרוק בהשוואה לאמנים שמתפרסמים בתחרויות כגון "כוכב נולד", ושהם זוכרים לטובה את הקהל הישראלי. בנוגע למצב המדיני והפוליטי, אמר סולן הלהקה, איאן גילן, כי "אנו מודעים למצב באזור, אך הופענו בהרבה מקומות בהם הייתה מחלוקת פוליטית, מכיוון שאנו אנשי מוזיקה. הרי זה היה אבסורד אם הופעה שלנו לפני עשור בלונדון, הייתה מתפרשת כתמיכה בטוני בלייר". המתופף איאן פייס אמר, כי "אנו באים לעשות את החיים שמחים יותר", ואף כינה אמנים שביטלו הופעות בישראל עקב המצב הפוליטי - "רכיכות". ב-22 וב-23 בפברואר 2014 הופיעה הלהקה בפעם הרביעית בישראל, בהיכל נוקיה, במסגרת סיבוב ההופעות של אלבומם "Now What?!".
ב-22 במאי 2016 הופיעה הלהקה בפארק ראשון לציון, בפעם החמישית בישראל.
ב-22 במאי 2022 הלהקה הופיעה בהיכל מנורה מבטחים בת"א, בפעם השישית בישראל.
כל הכרטיסים להופעה נמכרו והלהקה זכתה לביקורות טובות.
עקב הביקוש הרב, ב-23 במאי 2022 הופיעה הלהקה בפעם הראשונה בירושלים, בהיכל הפיס ארנה.
בעיית תרמיל הגב
בעיית תרמיל הגב (באנגלית: Knapsack problem) היא בעיית מיטוב קומבינטורית הנחקרת בתחום מדעי המחשב. בבעיה זו נתונה קבוצת עצמים שלכל אחד מהם משקל ומחיר, ובנוסף נתון חסם על המשקל. המטרה היא למצוא אוסף של העצמים הנתונים שסכום משקליהם אינו עולה על החסם הנתון, ומחירו מרבי.
הבעיה נחשבת לבעיה חשובה במדעי המחשב בגלל הערך התאורטי שלה (הבעיה היא NP-שלמה), ועקב השימושים שלה בתחומים כגון הקצאת משאבים וקריפטוגרפיה.
הגדרת הבעיה.
נתונים formula_1 עצמים ולכל עצם formula_2 נתונים מחירו formula_3 ומשקלו formula_4. לכל עצם formula_2 נסמן ב-formula_6 את מספר העצמים מהחפץ שנכניס לתרמיל.
המטרה היא למקסם את הביטוי formula_7 (המחיר הכולל של העצמים בתרמיל) בכפוף לאילוץ formula_8 (משקלם הכולל של החפצים אינו עולה על החסם).
הגרסה הנפוצה והפשוטה ביותר היא בעיית תרמיל הגב הבינארי: בבעיה זו לכל חפץ יש עותק אחד בלבד ולכן formula_9 (כלומר, אם חפץ מסוים נכנס לתרמיל אזי יש רק אחד מסוגו בתרמיל).
בבעיית תרמיל הגב החסומה, לכל עצם formula_2 יש כמות formula_11 ומותר להכניס לתרמיל מספר עותקים של העצם: formula_12.
בבעיית תרמיל הגב הלא חסומה, מותר לקחת מספר עותקים בלתי מוגבל מכל עצם: formula_13.
NP-שלמות.
גרסת ההכרעה של בעיית תרמיל הגב היא: בהינתן formula_1 עצמים עם מחירים formula_3 ומשקלים formula_4, ובהינתן מחיר כולל formula_17 וחסם על המשקל W יש להכריע האם קיימת בחירה של העצמים כך ש- formula_18 תחת האילוץ formula_8.
בעיה זו היא NP-שלמה:
גישות לפתרון.
תכנון דינאמי.
כיוון שהבעיה היא NP-שלמה, לא ידועים אלגוריתמים פולינומיים אשר מוצאים פתרון מיטבי. עם זאת, בגרסת הבעיה בה מובטח שכל משקלי הפריטים הם מספרים שלמים, קיים אלגוריתם המבוסס על תכנון דינאמי אשר פותר באופן מיטבי את הבעיה בסיבוכיות זמן פסאודו-פולינומית (אם משקלי הפריטים לא שלמים מספר תתי הבעיות עלול להיות אקספוננציאלי ביחס לקלט).
האלגוריתם הבא פותר את בעיית תרמיל הגב הבינארית בסיבוכיות זמן formula_35.
בהינתן מופע של הבעיה כמתואר בחלק "הגדרת הבעיה", נגדיר formula_36 להיות מחיר הפתרון המיטבי שניתן להשיג באמצעות עצמים שמספר הסידורי שלהם אינו עולה על formula_2 ושסכום משקלם אינו עולה על formula_38. הגדרה זו מאפשרת פיתוח נוסחת נסיגה ל-formula_36:
כעת ניתן, באמצעות חישוב ערכי הטבלה formula_48, לחשב ברקורסיה את formula_49, הלוא הוא המחיר המיטבי לבעיה.
הקוד הבא בשפת Python מממש את האלגוריתם המתואר:
def knapsack01_dp(items, limit):
table = [[0 for w in range(limit + 1)] for j in xrange(len(items) + 1)]
for j in xrange(1, len(items) + 1):
item, wt, val = items[j-1]
for w in xrange(1, limit + 1):
if wt &gt; w:
table[j][w] = table[j-1][w]
else:
table[j][w] = max(table[j-1][w],
table[j-1][w-wt] + val)
result = []
w = limit
for j in range(len(items), 0, -1):
was_added = table[j][w] != table[j-1][w]
if was_added:
item, wt, val = items[j-1]
result.append(items[j-1])
w -= wt
return result
אלגוריתמי קירוב.
גישה אחרת לפתרון הבעיה היא שימוש ב[[אלגוריתם_קירוב|אלגוריתמי קירוב]]. לבעיה זו קיימים מספר אלגוריתמי קירוב כולל [[סכמת קירוב פולינומית#סכמת קירוב פולינומית מלאה |סכמת קירוב פולינומית מלאה]] (FPTAS).
[[אלגוריתם חמדן|האלגוריתם החמדן]] הבא מוצא תרמיל שמחירו לכל הפחות מחצית המחיר של הפתרון המיטבי (2-קירוב):
נמיין את העצמים (שמשקלם אינו גדול מהחסם; עצם שמשקלו גדול מהחסם formula_50 אינו רלוונטי לבעיה) לפי יחס המחיר-משקל שלהם formula_51. נוסיף לתרמיל, כל עוד זה אפשרי, את העצם הבא ברשימה הממוינת לפי יחס מחיר-משקל (מתחילים עם העצם בעל היחס הגבוה ביותר). נסמן ב-formula_52 את מספר העצמים שהצלחנו להכניס בצורה זו, ולכן ניתן לתאר את המחיר של העצמים שהכנסנו על ידי: formula_53. כעת נתבונן על המחיר של העצם ה-formula_54: formula_55. אם formula_56, נשאיר את formula_52 העצמים בתיק, ואם formula_58, נוציא את formula_52 העצמים מהתיק, ונכניס במקומם את העצם ה-formula_54.
הוכחה שאלגוריתם זה נותן פתרון 2-קירוב: נסמן ב-formula_48 את הערך של הפתרון האופטימלי. נתבונן בבעיה דומה בה מותר לנו להכניס חלקי עצמים (נניח חצי עצם), ולא רק עצמים שלמים, ונסמן ב-formula_62 את הערך של הפתרון האופטימלי עבור בעיה זו. הפתרון האופטימלי עבור בעיה בה מותר להכניס חלקי עצמים, הוא גדול-שווה לפתרון האופטימלי של הבעיה המקורית בה ניתן להכניס רק עצמים שלמים (שכן כל פתרון עבור הבעיה המקורית, הוא גם פתרון אפשרי של הבעיה עם חלקי עצמים).
אם יכולנו להכניס לתרמיל חלקי עצמים, אזי ברור שהפתרון האופטימלי היה להכניס את j העצמים הראשונים, ולהכניס חלק מהעצם ה-j+1 שבדיוק ממלא את המשקל שניתן עוד להכניס לתרמיל (המשקל שניתן עוד להכניס לתרמיל לאחר הכנסת j העצמים הראשונים הוא formula_63, ולכן החלק של העצם ה-j+1 שיוכנס לתרמיל הוא formula_64). לכן:
ובמילים: המחיר של העצמים 1 עד j+1 גדול מהמחיר של עצמים 1 עד j + המחיר של חלק מעצם j+1, ששווה ל-M (הפתרון של הבעיה עם חלקי עצמים), שגדול-שווה ל-m (הפתרון של הבעיה שלנו).
לכן, אם נחלק את הסכום formula_67 ל-formula_68 ול-formula_55, בהכרח לפחות אחד משני הביטויים הללו חייב להיות בעל מחיר של לפחות formula_70, כיוון שסכום המשקלים של שניהם חייב להיות גדול-שווה ל-formula_48.
הערות שוליים.
[[קטגוריה:אופטימיזציה רציפה]]
[[קטגוריה:קומבינטוריקה]]
[[קטגוריה:בעיות NP-שלמות]]
[[קטגוריה:הוכחות]]
אדר דריאן
אָדָר דַריָאן (1931 – 8 בספטמבר 2015) היה קריקטוריסט, מעצב גרפי ומאייר ישראלי יליד רומניה. על יצירתו זכה בשנת 2012 ב"פרס עיפרון הזהב".
ביוגרפיה.
אדר דריאן נולד בבוקרשט שברומניה, בשנת 1931. את ניסיונו הראשון באמנות רכש מסבו, וולף גולדשמידט, שהיה מעצב בגדי גברים. בנעוריו החל ליצור קריקטורות, שאותן פרסם בעיתון הסאטירי "Pitigoiul" ובמקומות אחרים.
בשנת 1964 עלה לישראל עם משפחתו. הוא עבד כמעצב גרפי ב"פרסום דחף", בסטודיו של פול קידר וב"פרסום שחם לוינסון אילון". בנוסף, חזר ליצור קריקטורות, אותן פרסם במדור יומי בעיתון "דבר" ובעיתון ברומנית "Viata Noastra" וכן קריקטורה שבועית בעיתון "העולם הזה". בין השנים 1968–1970 כתב ואייר סידרה מדעית "מה באמת?" בעיתון הילדים "הארץ שלנו". בנוסף, אייר קומיקס מאת "יריב אמציה" ו"א. חורש", שמות עט של פנחס שדה, שהתפרסמו בעיתון זה בשנים 1969–1970.
בשנת 1969 החל לעבוד כקריקטוריסט ב"מעריב", שם פרסם קריקטורה שבועית במדור "סתם חיוך" וכמעצב הגרפי של "מעריב לנוער", עבורו יצר קריקטורות במדור "חיוכי ליל שישי". בין השנים 1979–1990 יצר קריקטורות עבור סינדיקט העיתונות "Agence Litteraire International". בין השנים 1983–1989 שימש כעורך הגרפי של הירחון "עת־מול". בנוסף, יצר קריקטורות לתוכניות הטלוויזיה "כמעט חצות" (הטלוויזיה הישראלית, 1980) ו"בכנסת" (1992). הוא המשיך בעבודה במעריב עד לשנת 1991, אז חזר להתגורר ברומניה, שם יצר קריקטורה יומית לעיתון "Libertatea". בשנת 2004 שב להתגורר בישראל. נפטר ב-2015, בגיל 84.
אדר אדריאן
פישל רבינוביץ'