שאלות בענין אלגוריתמים

[undo]

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

 

[אפר]

1. בבעית העודף - החזרת מספר מטבעות מינימלי לסכום מסוים- האם יש איזושהי נוסחה פשוטה לדעת עבור סט ספציפי של מטבעות האם האלגוריתם החמדני הינו אופטימלי? (האם זה נכון שמספיק לבדוק רק עד המכנה המשותף המצומצם לגודל המטבעות? ואם כן- מדוע?)
לדוג עבור 1,2,5,10 - האלג' אופטימלי, ועבור 1,4,5 - לא אופטימלי

אם אחד המטבעות גדול או שווה ל 50 אחוז מחיבור של המטבע מעליו והמטבעות מתחתיו האלגוריתם החמדני לא יהיה אופטימלי

כך נראה לי ממבט ראשון

 

[אפר]

אם אחד המטבעות גדול או שווה ל 50 אחוז מחיבור של המטבע מעליו והמטבעות מתחתיו האלגוריתם החמדני לא יהיה אופטימלי

כך נראה לי ממבט ראשון

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

 

[אפר]

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

תיקנתי בהודעה הבאה

 

[אפר]

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

לדוג'
1,4,9

אז זה הולך כך
4 נכנס ב 9 2.25 = מעגלים ל3
הפער הוא 3
מטבעות (9,1,1,1=4) > עיגול (3)
=לא יעיל (9,1,1,1) מול (4,4,4) = 12

לעומת זאת
1,2,4,9

ואז זה הולך כך
4 נכנס ב 9 2.25 = מעגלים ל3
הפער הוא =3
מטבעות (9,2,1=3) שווה(אותו דבר בקטן) עיגול (3)
= יעיל (9,2,1) מול (4,4,4) = 12

 

[undo]

לפי זה - החמדני כן יעיל ל 9, 4, 2, 1:
9 + 2 + 1 (3) = 12 - חמדני
4 + 4 + 4 (3) = 12 - דינאמי

5, 4, 1:
4 נכנס ב 5 1.25 פעמים = 2.
5 + 1 + 1 + 1 (4) = 8. סך האיברים שונה מ 2, ואכן הוא לא יעיל כאן.
הפתרון האופטימלי הוא 4 + 4

 

[אפר]

לפי זה - החמדני כן יעיל ל 9, 4, 2, 1:
9 + 2 + 1 (3) = 12 - חמדני
4 + 4 + 4 (3) = 12 - דינאמי

5, 4, 1:
4 נכנס ב 5 1.25 פעמים = 2.
5 + 1 + 1 + 1 (4) = 8. סך האיברים שונה מ 2, ואכן הוא לא יעיל כאן.
הפתרון האופטימלי הוא 4 + 4

גדול ולא שונה

 

[אפר]

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

לדוג'
1,4,9

אז זה הולך כך
4 נכנס ב 9 2.25 = מעגלים ל3
הפער הוא 3
מטבעות (9,1,1,1=4) > עיגול (3)
=לא יעיל (9,1,1,1) מול (4,4,4) = 12

לעומת זאת
1,2,4,9

ואז זה הולך כך
4 נכנס ב 9 2.25 = מעגלים ל3
הפער הוא =3
מטבעות (9,2,1=3) שווה(אותו דבר בקטן) עיגול (3)
= יעיל (9,2,1) מול (4,4,4) = 12

ולפי זה ניתן להשתמש בחמדני ולעשות המרה רק לאפשרות של העיגול במקרה של 1,4,9 המרה של כל (9,1,1,1) ל (4,4,4)

 

[kadima]

לא הצלחתי ממש להבין.
לפי הנוסחא שלך - האם 1,3,5 אופטימלי או לא?
ו1,2,5,10,20,25?
ואותו סט של 6 המטבעות לעיל + מטבע של 15?

 

[אפר]

לא הצלחתי ממש להבין.
לפי הנוסחא שלך - האם 1,3,5 אופטימלי או לא?
ו1,2,5,10,20,25?
ואותו סט של 6 המטבעות לעיל + מטבע של 15?

1,3,5 אופטימלי
כך
5לחלק ל3 = 1.67 מעוגל ל2 (*3=6)
חמדני 6 = 1,5(2)
העיגול = 2 אז שניהם שווים וממילא החמדני - אופטימלי

1,2,5,10,20,25
2)
5 לחלק ל2 = 2.5 מעוגל ל3 (*2=6)
חמדני 6 = 1,5 (2)
העיגול=3 אז החמדני קטן מהעיגול והוא אופטימלי - לאיבר זה
5)
10 לחלק ל5 = 2 (*5=10)
חמדני 10 = 10 (1)
העיגול = 2 אז החמדני קטן מהעיגול והוא אופטימלי לאיבר זה
10)
20 לחלק ל 10 = 2 (*10=20)
חמדני 20 = 20 (1)
העיגול = 2 אז החמדני קטן מהעיגול והוא אופטימלי לאיבר זה
20)
25 לחלק ל20 = 1.25 מעוגל ל2 (*20=40)
חמדני 40 = 25,10,5 (3)
העיגול =2 אז החמדני גדול מהעיגול והוא לא אופטימלי לאיבר זה
וממילא בסט מטבעות זה החמדני לא אופטימלי

1,2,5,10,15,20,25
2)
5 לחלק ל2 = 2.5 מעוגל ל3 (*2=6)
חמדני 6 = 1,5 (2)
העיגול=3 אז החמדני קטן מהעיגול והוא אופטימלי - לאיבר זה
5)
10 לחלק ל5 = 2 (*5=10)
חמדני 10 = 10 (1)
העיגול = 2 אז החמדני קטן מהעיגול והוא אופטימלי לאיבר זה
10)
15 לחלק ל 10 = 1.5 מעוגל ל 2 (*10=20)
חמדני 20 = 20 (1)
העיגול = 2 אז החמדני קטן מהעיגול והוא אופטימלי לאיבר זה
15)
20 לחלק ל 15 = 1.333 מעוגל ל2 (*15=30)
חמדני 30 = 25,5 (2)
העיגול = 2 חמדני שווה לעיגול ולכן הוא אופטימלי לאיבר זה
20)
25 לחלק ל20 = 1.25 מעוגל ל2 (*20=40)
חמדני 40 = 25,15 (2)
העיגול =2 אז החמדני שווה לעיגול והוא אופטימלי לאיבר זה
וממילא בסט מטבעות זה החמדני אופטימלי

 

[אפר]

1,3,5 אופטימלי
כך
5לחלק ל3 = 1.67 מעוגל ל2 (*3=6)
חמדני 6 = 1,5(2)
העיגול = 2 אז שניהם שווים וממילא החמדני - אופטימלי

1,2,5,10,20,25
2)
5 לחלק ל2 = 2.5 מעוגל ל3 (*2=6)
חמדני 6 = 1,5 (2)
העיגול=3 אז החמדני קטן מהעיגול והוא אופטימלי - לאיבר זה
5)
10 לחלק ל5 = 2 (*5=10)
חמדני 10 = 10 (1)
העיגול = 2 אז החמדני קטן מהעיגול והוא אופטימלי לאיבר זה
10)
20 לחלק ל 10 = 2 (*10=20)
חמדני 20 = 20 (1)
העיגול = 2 אז החמדני קטן מהעיגול והוא אופטימלי לאיבר זה
20)
25 לחלק ל20 = 1.25 מעוגל ל2 (*20=40)
חמדני 40 = 25,10,5 (3)
העיגול =2 אז החמדני גדול מהעיגול והוא לא אופטימלי לאיבר זה
וממילא בסט מטבעות זה החמדני לא אופטימלי

1,2,5,10,15,20,25
2)
5 לחלק ל2 = 2.5 מעוגל ל3 (*2=6)
חמדני 6 = 1,5 (2)
העיגול=3 אז החמדני קטן מהעיגול והוא אופטימלי - לאיבר זה
5)
10 לחלק ל5 = 2 (*5=10)
חמדני 10 = 10 (1)
העיגול = 2 אז החמדני קטן מהעיגול והוא אופטימלי לאיבר זה
10)
15 לחלק ל 10 = 1.5 מעוגל ל 2 (*10=20)
חמדני 20 = 20 (1)
העיגול = 2 אז החמדני קטן מהעיגול והוא אופטימלי לאיבר זה
15)
20 לחלק ל 15 = 1.333 מעוגל ל2 (*15=30)
חמדני 30 = 25,5 (2)
העיגול = 2 חמדני שווה לעיגול ולכן הוא אופטימלי לאיבר זה
20)
25 לחלק ל20 = 1.25 מעוגל ל2 (*20=40)
חמדני 40 = 25,15 (2)
העיגול =2 אז החמדני שווה לעיגול והוא אופטימלי לאיבר זה
וממילא בסט מטבעות זה החמדני אופטימלי

ב VBA

Option Compare Database

Function OptimalChamdani(ParamArray SetMatbeot()) As Boolean
Dim Temp1, Temp2
Dim TempIgul As Long
For Each i In SetMatbeot()
Temp2 = IIf(IsEmpty(Temp1), 0, Temp1)
Temp1 = i
If Temp2 > 0 Then TempIgul = Int((((Temp1 / Temp2)) / 1) + 0.999999)
If Not Chamdani(TempIgul * Temp2, SetMatbeot()) <= TempIgul Or Chamdani < 0 Then Exit Function
Next i
OptimalChamdani = True
End Function

Function Chamdani(Ms As Double, ParamArray SetMatbeot()) As Long
Dim Mone As Long, Total As Double, TempMone As Double
TempMone = -1
Do Until Total = Ms
If TempMone = Total Then GoTo Chelki
TempMone = Total
Total = Total + MaxInArray(Ms - Total, SetMatbeot)
Mone = Mone + 1
Loop
Chamdani = Mone
Exit Function
Chelki:
Chamdani = -1
End Function

Function MaxInArray(Agbala As Double, ParamArray SetMatbeot()) As Double
Dim i, Temp
Temp = 0
For Each i In SetMatbeot(0)(0)
If IsNull(i) Then i = 0
If i > Temp And i <= Agbala Then Temp = i
Next i
MaxInArray = Temp
End Function

Function MinInArray(ParamArray SetMatbeot()) As Double
Dim i, Temp
Temp = 0
For Each i In SetMatbeot(0)(0)
If IsNull(i) Then i = 0
If i > Temp Then Temp = i
Next i
For Each i In SetMatbeot(0)(0)
If IsNull(i) Then i = 0
If i < Temp And i > 0 Then Temp = i
Next i
MinInArray = Temp
End Function

 

[kadima]

וואו!
איזו השקעה.
אין מילים- נראה שאכן עובד. אני עדיין מנסה למצוא איזושהי דוגמא נגדית, בינתיים לא מצאתי...
תודה רבה.

 

[loving music]

היי
מקווה שיש מישהו שיענה לי עכשיו....
הנוסחה נראית מדהימה, והיא גם מתיישבת על ההיגיון (אני הגעתי למשהו די דומה)
אבל זאת לא הוכחה שאפשר לכתוב במבחן., בעצם זאת לא הוכחה בכלל....
יש העיקרון דרך להוכיח אלגוריתמים חמדניים שמבוססת על הנחה שיש שאלגוריתם כלשהו הבוחר את הפתרון האופטימלי (במקרה הזה 0 מינימום המטבעות), אחר כך מניחים שהפלט של שתיהם (החמדן והאחר) זהה עד לנקודה מסויימת (שיכולה להיות גם הנקודה האפס ), ומשם והלאה הם שונים.
עד כאן ההנחות וכאן צריך להוכיח שניתן להחליף את הבחירה של האחר במקום השונה הראשון בבחירה של החמדני בלי לפגוע בנכונות הפלט, ואחר כך ניתן להחליף במקום הבא וכך הלאה - כלומר הפלט עדיין ישאר אופטימלי גם לאחר שיוחלף כולו לפלט של החמדן ומכאן שהחמדן הוא אופטימלי.
הבעיה היא שיש בעיות שפשוט מאד להוכיח את זה ויש בעיות (כמו בעיית העודף עם המטבעות 1,3,5) שזה יותר מורכב.
יש מישהו שמכיר את הדרך הזאת ויודע לתת לי הוכחה לבעייה הזאת עם הקלט הזה?

 

[אפר]

היי
מקווה שיש מישהו שיענה לי עכשיו....
הנוסחה נראית מדהימה, והיא גם מתיישבת על ההיגיון (אני הגעתי למשהו די דומה)
אבל זאת לא הוכחה שאפשר לכתוב במבחן., בעצם זאת לא הוכחה בכלל....
יש העיקרון דרך להוכיח אלגוריתמים חמדניים שמבוססת על הנחה שיש שאלגוריתם כלשהו הבוחר את הפתרון האופטימלי (במקרה הזה 0 מינימום המטבעות), אחר כך מניחים שהפלט של שתיהם (החמדן והאחר) זהה עד לנקודה מסויימת (שיכולה להיות גם הנקודה האפס ), ומשם והלאה הם שונים.
עד כאן ההנחות וכאן צריך להוכיח שניתן להחליף את הבחירה של האחר במקום השונה הראשון בבחירה של החמדני בלי לפגוע בנכונות הפלט, ואחר כך ניתן להחליף במקום הבא וכך הלאה - כלומר הפלט עדיין ישאר אופטימלי גם לאחר שיוחלף כולו לפלט של החמדן ומכאן שהחמדן הוא אופטימלי.
הבעיה היא שיש בעיות שפשוט מאד להוכיח את זה ויש בעיות (כמו בעיית העודף עם המטבעות 1,3,5) שזה יותר מורכב.
יש מישהו שמכיר את הדרך הזאת ויודע לתת לי הוכחה לבעייה הזאת עם הקלט הזה?

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

 

[loving music]

לא יודעת אם קראת את כל מה שכתבתי קודם, אבל אני צריכה ניסוח פורמלי למבחן, ועכשיו מצאתי פתרון לבעיה דומה בדרך המבוקשת, אני מעתיקה אותו בשינויים קלים. מומלץ לקרוא כי זה מסדר את העניין הזה בראש...
הוכחה לבעיית המטבעות עבור כל קלט:
נשים לב:
א - כל אלג' יעיל שפותר את הבעיה ישתמש ב 2 מטבעות של 1 לכל היותר, כי 3 מטבעות של 1 ניתן להחליף במטבע 3
ב-כל אלג' יעיל שפותר את הבעיה ישתמש ב מטבע 1 של 3 לכל היותר, כי 2 מטבעות של 1 ניתן להחליף במטבעות 5,1 (בחירה חמדנית)

נמיין את המטבעות שבחרו האלגוריתמים מהגדול לקטן וניגש למקום הראשון שבו הבחירה הייתה שונה (שוב, ייתכן שזהו המקום הראשון) ונסמן את הבחירה של החמדן כ-X, ואת הבחירה של החמדן כ-Y
מכיוון שהחמדן בוחר בכל פעם את המטבע הגדול ביותר האפשרי, ברור ש X>Y
אם כן:
נניח ש X=5
האחר יחליף את הבחירה הזאת במטבע אחד של 3 ו-2 מטבעות של 1 - סב"כ 3 מטבעות - וזה וודאי פחות יעיל ממטבע אחד של 5.
נניח ש X=3
האחר יחליף את הבחירה ל 2 מטבעות של 1 (הרי הוכחנו שאף אלגוריתם יעיל לא יבחר יותר מ 2 מטבעות של 1)
ואם כן נותרנו עם סכום של 1 שהאלגוריתם האחר לא יכול לשלם, וזה מבטל את נכונות האלג האחר
אם אף אלג אחר לא יוכל למצוא בחירה טובה יותר מהחמדן, מוכח שהחמדן מביא את הבחירה הטובה ביותר.
(השורה הטיפשית והמובנת מאליה שצריך בסוף כל הוכחה...)
תנסה את זה על כל צרוף של מטבעות, פשוט מושלם!

 

[אפר]

לא יודעת אם קראת את כל מה שכתבתי קודם, אבל אני צריכה ניסוח פורמלי למבחן, ועכשיו מצאתי פתרון לבעיה דומה בדרך המבוקשת, אני מעתיקה אותו בשינויים קלים. מומלץ לקרוא כי זה מסדר את העניין הזה בראש...
הוכחה לבעיית המטבעות עבור כל קלט:
נשים לב:
א - כל אלג' יעיל שפותר את הבעיה ישתמש ב 2 מטבעות של 1 לכל היותר, כי 3 מטבעות של 1 ניתן להחליף במטבע 3
ב-כל אלג' יעיל שפותר את הבעיה ישתמש ב מטבע 1 של 3 לכל היותר, כי 2 מטבעות של 1 ניתן להחליף במטבעות 5,1 (בחירה חמדנית)

נמיין את המטבעות שבחרו האלגוריתמים מהגדול לקטן וניגש למקום הראשון שבו הבחירה הייתה שונה (שוב, ייתכן שזהו המקום הראשון) ונסמן את הבחירה של החמדן כ-X, ואת הבחירה של החמדן כ-Y
מכיוון שהחמדן בוחר בכל פעם את המטבע הגדול ביותר האפשרי, ברור ש X>Y
אם כן:
נניח ש X=5
האחר יחליף את הבחירה הזאת במטבע אחד של 3 ו-2 מטבעות של 1 - סב"כ 3 מטבעות - וזה וודאי פחות יעיל ממטבע אחד של 5.
נניח ש X=3
האחר יחליף את הבחירה ל 2 מטבעות של 1 (הרי הוכחנו שאף אלגוריתם יעיל לא יבחר יותר מ 2 מטבעות של 1)
ואם כן נותרנו עם סכום של 1 שהאלגוריתם האחר לא יכול לשלם, וזה מבטל את נכונות האלג האחר
אם אף אלג אחר לא יוכל למצוא בחירה טובה יותר מהחמדן, מוכח שהחמדן מביא את הבחירה הטובה ביותר.
(השורה הטיפשית והמובנת מאליה שצריך בסוף כל הוכחה...)
תנסה את זה על כל צרוף של מטבעות, פשוט מושלם!

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

 

[loving music]

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

 

[loving music]

ואגב ההוכחה שלך באמת נכונה, אבל אני לא רואה דרך לכתוב אותה בצורה שתתקבל במבחן (הם קשוחים ממש...)

 

[נסיון9876]

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

 

[loving music]

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