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

[kadima]

אשמח לקבל תשובות על השאלות הנ"ל
כל תגובה תעזור ותתקבל בברכה

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

2. מציאת חציון (בעית הבחירה) בזמן של o(n - רעיונות?????
אפשר למצוא קירוב בשיטת החמישיות, מחפשת משהו מדויק. לכאורה ע"י הפרד ומשול

3.מציאת מספר מינימלי של SWAP שיש לעשות במערך לא ממוין כדי למיין אותו.
לכאורה אמור להתבסס על הרעיון של mergesort

4. מציאת זוג איברים במערך שסכומם שווה לסכום נתון כלשהו בזמן של o(n

5. למצוא סדרת איברים במערך המופיעים ברצף במערך וסכומם שווה לכפולה כלשהי של מספר נתון בזמן של O(N

תודה מראש

 

[Rרחמים]

נראה שלכל שאלה כאן צריך לפתוח אשכול בנפרד, אחרת יהיה פה סלט שלם.

 

[undo]

4. מציאת זוג איברים במערך שסכומם שווה לסכום נתון כלשהו בזמן של o(n

סריקה משני הצדדים בו זמנית.

 

[kadima]

סריקה משני הצדדים בו זמנית.

זה N^2
אין שום אפשרות לדעת היכן ימצא הזוג

 

[undo]

זה N^2
אין שום אפשרות לדעת היכן ימצא הזוג

סליחה, התייחסתי למערך ממוין.

 

[פרוגיוזרית]

4. מציאת זוג איברים במערך שסכומם שווה לסכום נתון כלשהו בזמן של o(n

נתון משהו נוסף על המערך? כי אם יש טווח לערכים - K מסוים, אז אפשר למיין בcounting sort בזמן לינארי, ואז לרוץ משני צדדיו כמו שהציעה @undo והסך הכולל עדיין לינארי.

 

[eliezer]

לגבי מציאת חציון
משתמשים ברעיון של מיון מהיר אך עם שינוי.

 

[kadima]

נתון משהו נוסף על המערך? כי אם יש טווח לערכים - K מסוים, אז אפשר למיין בcounting sort בזמן לינארי, ואז לרוץ משני צדדיו כמו שהציעה @undo והסך הכולל עדיין לינארי.

תודה
אבל לא מופיע משהו כזה בשאלה.
אין סיכוי בעזרת איזשהו הפרד ומשול?

 

[פרוגיוזרית]

תודה
אבל לא מופיע משהו כזה בשאלה.
אין סיכוי בעזרת איזשהו הפרד ומשול?

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

 

[kadima]

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

 

[מאה100]

1. בעיית העודף לא זהה לבעיית התרמיל בשברים(חמדני)? אני מתלבטת אם התרמיל בשברים או בשלמים...
משקל= סכום וכו'
משום מה זכור לי כך..

 

[מאה100]

5. לדעתי אי אפשר.
הבעיה מאוד דומה לבעיית: סכום מקסימלי של תת סדרה רציפה(את הכפולה מחשבים ב O(1.)
ואת הבעיה הזאת (סמשתס"ר) פותרים ב O של N^2.
אם יש לי טעות אשמח שתעמידו אותי עליה.
בהצלחה

 

[kadima]

1. בעיית העודף לא זהה לבעיית התרמיל בשברים(חמדני)? אני מתלבטת אם התרמיל בשברים או בשלמים...
משקל= סכום וכו'
משום מה זכור לי כך..

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

 

[מאה100]

לא כ"כ הבנתי את השאלה שלך..
תוכלי להשוות את הפתרון החמדני עם הפתרון הנאיבי.
באופן כללי זמן הריצה של האלג' תלוי בגודל הקלט:
זמן ריצה כולל של האלגוריתם הדינמי - Ѳ(nW)
זמן הריצה הכולל של האלגוריתם הנאיבי: Ѳ(n*2n)
לסיכום, נשתמש בפתרון הדינמי אך ורק אם nW << n* 2n

קלט הבעיה הוא: 2n מספרים של השווי הכספי והמשקל של כל פריט, ובנוסף מספר W של קיבולת התרמיל.

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

בהצלחה

 

[kadima]

או שלא הבנת אותי או שלא הבנתי אותך.
השאלה המקורית שלי הייתה- האם קיימת איזושהי נוסחא/כלל אצבע... כדי לדעת מתי הפתרון החמדני הינו אופטימלי או לא בבעיית העודף. כמובן בתלות בסט המטבעות הנתון.
לדוג עבור 1,2,5,10 - הוא אופטימלי
אך עבור 1,4,5, או לחילופין עבור 1,5,10,20,25 - הוא לא אופטימלי.
ואם הצורה היחידה לפסול אופטימליות היא להביא דוגמא נגדית - הרי האם יש כלל שאומר עד איזה מספר צריך לחפש דוגמא נגדית
לדוג בסט הראשון: 1,4,5 הדוג הנגדית הראשונה היא 8
אבל בסט השני הדוגמא הנגדית הראשונה(בתקווה שבדקתי נכון) היא 40.

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

 

[shakshuka]

4. מציאת זוג איברים במערך שסכומם שווה לסכום נתון כלשהו בזמן של o(n

יש לי רעיון כלשהו, מקווה שעונה על הצורך של היעילות -
לאחד את איברי המערך לתוך STRING, עם תו מפריד ביניהם,
ואז לרוץ ולחפש בREGEX את המשלים לאיבר הנוכחי.

 

[אנונימי123]

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

תודה!!

 

[kadima]

בשביל לסתור- הכי פשוט להביא דוגמא נגדית

 

[אנונימי123]

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

 

[kadima]

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

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