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

  • הוסף לסימניות
  • #1
אשמח לקבל תשובות על השאלות הנ"ל
כל תגובה תעזור ותתקבל בברכה

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

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

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

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

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

תודה מראש
 
  • הוסף לסימניות
  • #2
נראה שלכל שאלה כאן צריך לפתוח אשכול בנפרד, אחרת יהיה פה סלט שלם.
 
  • הוסף לסימניות
  • #6
4. מציאת זוג איברים במערך שסכומם שווה לסכום נתון כלשהו בזמן של o(n
נתון משהו נוסף על המערך? כי אם יש טווח לערכים - K מסוים, אז אפשר למיין בcounting sort בזמן לינארי, ואז לרוץ משני צדדיו כמו שהציעה @undo והסך הכולל עדיין לינארי.
 
  • הוסף לסימניות
  • #7
לגבי מציאת חציון
משתמשים ברעיון של מיון מהיר אך עם שינוי.
 

קבצים מצורפים

  • Screenshot_20191202-091102_Dropbox.jpg
    Screenshot_20191202-091102_Dropbox.jpg
    1.3 MB · צפיות: 186
נערך לאחרונה ב:
  • הוסף לסימניות
  • #8
נתון משהו נוסף על המערך? כי אם יש טווח לערכים - K מסוים, אז אפשר למיין בcounting sort בזמן לינארי, ואז לרוץ משני צדדיו כמו שהציעה @undo והסך הכולל עדיין לינארי.
תודה
אבל לא מופיע משהו כזה בשאלה.
אין סיכוי בעזרת איזשהו הפרד ומשול?
 
  • הוסף לסימניות
  • #9
תודה
אבל לא מופיע משהו כזה בשאלה.
אין סיכוי בעזרת איזשהו הפרד ומשול?
צריכה להתרענן מקורס האלגוריתמים שלי. זוכר לי כמעט בוודאות שהיו שאלות בסגנון הזה. אם יהיה לי זמן לשבת על זה ממש, אז בע"ה בערב. (זה קורס בפתוחה, אגב?)
 
  • הוסף לסימניות
  • #10
לא רוצה לגרום לטרחה משמעותית.
זה לא מקורס של הפתוחה- אלא מאיזו מצגת שמצאתי ברשת של שאלות ללא תשובות. (ועשה רושם רציני- שאמור להיות לזה תשובה)
לא קריטי בכלל.
יותר חשוב לי אם כן השאלה בענין הפתרון החמדני בענין העודף.
ואם בכלל - יש למישהי דוגמאות מובנות להוכחת אופטימליות של אלגוריתם חמדני.
כל השאר- בונוס מבחינתי
תודה
 
  • הוסף לסימניות
  • #11
1. בעיית העודף לא זהה לבעיית התרמיל בשברים(חמדני)? אני מתלבטת אם התרמיל בשברים או בשלמים...
משקל= סכום וכו'
משום מה זכור לי כך..
 
  • הוסף לסימניות
  • #12
5. לדעתי אי אפשר.
הבעיה מאוד דומה לבעיית: סכום מקסימלי של תת סדרה רציפה(את הכפולה מחשבים ב O(1.)
ואת הבעיה הזאת (סמשתס"ר) פותרים ב O של N^2.
אם יש לי טעות אשמח שתעמידו אותי עליה.
בהצלחה
 
  • הוסף לסימניות
  • #13
1. בעיית העודף לא זהה לבעיית התרמיל בשברים(חמדני)? אני מתלבטת אם התרמיל בשברים או בשלמים...
משקל= סכום וכו'
משום מה זכור לי כך..
זה לכאורה אכן דומה לבעית התרמיל בשלמים וע"כ זה לא תמיד אופטימלי.
השאלה שלי היא האם יש דרך לדעת מתי הצורה החמדנית היא אופטימלית ומתי לא.
 
  • הוסף לסימניות
  • #14
לא כ"כ הבנתי את השאלה שלך..
תוכלי להשוות את הפתרון החמדני עם הפתרון הנאיבי.
באופן כללי זמן הריצה של האלג' תלוי בגודל הקלט:
זמן ריצה כולל של האלגוריתם הדינמי - Ѳ(nW)
זמן הריצה הכולל של האלגוריתם הנאיבי: Ѳ(n*2n)
לסיכום, נשתמש בפתרון הדינמי אך ורק אם nW << n* 2n

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

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

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

ובכלל יעזור לי מאוד אם למישהו יש הוכחות לאופטימליות של אלגוריתמים חמדניים שלא בצורה הבסיסית הרגילה(כלומר הוכחות שלא כוללות את הוכחת תת מבנה אופטימלי והוכחה באינדוקציה על הבחירות - אלא הוכחות יותר אינטואיטיביות.)
תודה מראש
 
  • הוסף לסימניות
  • #16
4. מציאת זוג איברים במערך שסכומם שווה לסכום נתון כלשהו בזמן של o(n
יש לי רעיון כלשהו, מקווה שעונה על הצורך של היעילות -
לאחד את איברי המערך לתוך STRING, עם תו מפריד ביניהם,
ואז לרוץ ולחפש בREGEX את המשלים לאיבר הנוכחי.
 
  • הוסף לסימניות
  • #17
משהי יודעת את הוכחה שהפתרון החמדני לבעיית העודף לא טוב תמיד??
לפי משהו עם %....

תודה!!
 
  • הוסף לסימניות
  • #18
בשביל לסתור- הכי פשוט להביא דוגמא נגדית
 
  • הוסף לסימניות
  • #19
אבל לא תמיד זה עוזר,
כשמבקשים הוכחה... צריך הסבר כללי, לא דוקא על משהו יחיד שזה לא נותן לו את הפתרון האופטימלי...
 
  • הוסף לסימניות
  • #20
ממש מוזר.
עקרונית כדי תפסול טענה של תמיד(לכל X...) מספיק בודאות דוגמא נגדית
ואם הטענה היא של "קיים...." הרי מספיק להצביע על סט כלשהו של מטבעות עבורו הטענה מתקיימת. וכמובן להוכיח שהטענה אכן מתקיימת.

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

פרוגבוט

תוכן שיווקי
פרסומת

פוסטים חדשים שאולי לא קראת....

גלגל_מזלות_וינשוף_קסום.gif

ברוכים הבאים לאשכול הרשמי של "חויה בקליק" - הבית של המשחקים האינטראקטיביים, הקליקרים וההפעלות הכי חכמות שיש.

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

אז איך זה עובד?​

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

רוצים לסובב את הגלגל ולבדוק את המזל?​

  1. הגיבו כאן באשכול: "אני רוצה לסובב את הגלגל"
  2. נשלח לכם בהודעה פרטית קישור קסם חד-פעמי.
  3. לחצו על הקישור- ותגלו מיד במה זכיתם.
  4. כל כרטיס זוכה!

קצת עלינו (למי שלא מכיר):​

אנחנו ב"חויה בקליק" הופכים כל אירוע – מיום הולדת משפחתי ועד כנס של 2000 איש – לאירוע סוחף, תחרותי ומגבש.

מה תמצאו אצלינו:

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

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

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

  • ספיישל חנוכה: תוכניות מוכנות, מעוצבות ומתוכנתות למסיבות חנוכה - רק לחבר למסך ולהתחיל לשחק.

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

שירות ותמיכה​

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

📞 בטלפון לתמיכה ושירות: 03-773-7970
🌐 לאתר שלנו ולהתרשמות: -https://clicker.co.il/
📧 מייל: K037737970 @ GMAIL.COM

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

הצטרפות לניוזלטר

איזה כיף שהצטרפתם לניוזלטר שלנו!

מעכשיו, תהיו הראשונים לקבל את כל העדכונים, החדשות, ההפתעות בלעדיות, והתכנים הכי חמים שלנו בפרוג!

לוח מודעות

הפרק היומי

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


תהילים פרק כה

אלְדָוִד אֵלֶיךָ יי נַפְשִׁי אֶשָּׂא:באֱלֹהַי בְּךָ בָטַחְתִּי אַל אֵבוֹשָׁה אַל יַעַלְצוּ אֹיְבַי לִי:גגַּם כָּל קוֶֹיךָ לֹא יֵבֹשׁוּ יֵבֹשׁוּ הַבּוֹגְדִים רֵיקָם:דדְּרָכֶיךָ יי הוֹדִיעֵנִי אֹרְחוֹתֶיךָ לַמְּדֵנִי:ההַדְרִיכֵנִי בַאֲמִתֶּךָ וְלַמְּדֵנִי כִּי אַתָּה אֱלֹהֵי יִשְׁעִי אוֹתְךָ קִוִּיתִי כָּל הַיּוֹם:וזְכֹר רַחֲמֶיךָ יי וַחֲסָדֶיךָ כִּי מֵעוֹלָם הֵמָּה:זחַטֹּאות נְעוּרַי וּפְשָׁעַי אַל תִּזְכֹּר כְּחַסְדְּךָ זְכָר לִי אַתָּה לְמַעַן טוּבְךָ יי:חטוֹב וְיָשָׁר יי עַל כֵּן יוֹרֶה חַטָּאִים בַּדָּרֶךְ:טיַדְרֵךְ עֲנָוִים בַּמִּשְׁפָּט וִילַמֵּד עֲנָוִים דַּרְכּוֹ:יכָּל אָרְחוֹת יי חֶסֶד וֶאֱמֶת לְנֹצְרֵי בְרִיתוֹ וְעֵדֹתָיו:יאלְמַעַן שִׁמְךָ יי וְסָלַחְתָּ לַעֲוֹנִי כִּי רַב הוּא:יבמִי זֶה הָאִישׁ יְרֵא יי יוֹרֶנּוּ בְּדֶרֶךְ יִבְחָר:יגנַפְשׁוֹ בְּטוֹב תָּלִין וְזַרְעוֹ יִירַשׁ אָרֶץ:ידסוֹד יי לִירֵאָיו וּבְרִיתוֹ לְהוֹדִיעָם:טועֵינַי תָּמִיד אֶל יי כִּי הוּא יוֹצִיא מֵרֶשֶׁת רַגְלָי:טזפְּנֵה אֵלַי וְחָנֵּנִי כִּי יָחִיד וְעָנִי אָנִי:יזצָרוֹת לְבָבִי הִרְחִיבוּ מִמְּצוּקוֹתַי הוֹצִיאֵנִי:יחרְאֵה עָנְיִי וַעֲמָלִי וְשָׂא לְכָל חַטֹּאותָי:יטרְאֵה אוֹיְבַי כִּי רָבּוּ וְשִׂנְאַת חָמָס שְׂנֵאוּנִי:כשָׁמְרָה נַפְשִׁי וְהַצִּילֵנִי אַל אֵבוֹשׁ כִּי חָסִיתִי בָךְ:כאתֹּם וָיֹשֶׁר יִצְּרוּנִי כִּי קִוִּיתִיךָ:כבפְּדֵה אֱלֹהִים אֶת יִשְׂרָאֵל מִכֹּל צָרוֹתָיו:
נקרא  2  פעמים
למעלה