עבודה אקדמית? חפשו עכשיו במאגר הענק, האיכותי והעדכני ביותר:

מוענק על כל האתר 7 אחוז הנחה בעת "חרבות ברזל". קוד קופון: "מלחמה"

ב"ה. אנו חב"דניקים ולא נחטא בגזל: יש גם עבודות אקדמיות בחינם (גמ"ח). 15,000 עבודות אקדמיות במחיר שפוי של 99 - 390 שח.  סרטון על מאגר העבודות האקדמיות

اللغة العربية Русский

français              አማርኛ

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

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

חוות דעת על מרצים

הוצאת ויזה לדובאי תשלום מאובטח בעברית

אמריקן אקספרס – ויקיפדיה    (לא דיינרס)    

תוצאת תמונה עבור פייבוקס 5% הנחה ב-פייבוקס  

bit ביט on the App Store   ×ª×©×œ×•× בחיוב אשראי טלפוני דרך נציג שירות 24/7העברה בנקאית

 

עבודה אקדמית אלגוריתמים מקורבים לפתרון בעיית הספיקות המשוקללת המרבית (עבודה אקדמית מס. 304)

‏290.00 ₪

73 עמ'.

עבודה אקדמית אלגוריתמים מקורבים לפתרון בעיית הספיקות המשוקללת המרבית

תוכן עניינים

פרק 1 (מבוא)

            1.1 - במה עוסק הסמינר?                                                                 עמ' 2

            1.2 - בעיות אופטימיזציה                                                                 עמ' 4

            1.3 - בעיית הספיקות                                                                        עמ' 7

 

פרק 2 (אלגוריתמים דטרמיניסטיים)

            2.1 - האלגוריתמים החמדנים של ג'ונסון                                       עמ' 9

                        2.1.1 - האלגוריתם הראשון של ג'ונסון                               עמ' 9

                        2.1.2 - האלגוריתם השני של ג'ונסון                                    עמ' 14

            2.2 - חיפוש מקומי                                                                            עמ' 22

 

פרק 3 (אלגוריתמים אקראיים)

            3.1 - האלגוריתם Random                                                            עמ' 25

            3.2 - שיטת ההסתברויות המותנות                                     עמ' 26

            3.3 - האלגוריתם GenRandom                                                   עמ' 27

            3.4 - שיטת GenApprox                                                                עמ' 28

                        3.4.1 - אלגוריתם ¾-קירוב                                     עמ' 30

                        3.4.2 - אלגוריתם Goemans-Williamson                  עמ' 35

            נספח (הוכחת הלמה מסעיף 2.1.2)                                        עמ' 64 

 ביבליוגרפיה                                                                                                עמ' 70

 

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

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

הפרק השני בסמינר מחולק לשלושה חלקים ועוסק בשלושה אלגוריתמים דטרמיניסטיים לפתרון הבעיה: שני האלגוריתמים שהוצגו על ידי ג'ונסון במאמר [3] משנת 1974, ואלגוריתם החיפוש המקומי.

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

האלגוריתם השני של ג'ונסון מחוכם יותר מהאלגוריתם הראשון, ומקטין פי 2 את ערכה של פסוקית עבור כל ליטרל חופשי אשר נותר בה. (כיוון שעבור חצי מהשמות ערכי האמת, יביא ליטרל זה לסיפוק הפסוקית) בסמינר מוכח שאלגוריתם זה דורש גם הוא זמן ריצה לינארי, שמדובר באלגוריתם 2/3-קירוב, ו-2/3-קירוב בלבד. (ניתן לציין שעובדה זו חמקה מג'ונסון כאשר הציג את האלגוריתם. ג'ונסון טען כי מדובר באלגוריתם ½-קירוב בלבד, כמו האלגוריתם הראשון) הוכחת ההערכה ההדוקה לביצועי האלגוריתם מתבססת על ההוכחה המופיעה במאמר [2] משנת 1997, בו הוכחה טענה זו לראשונה, 23 שנים לאחר שהאלגוריתם הוצג על ידי ג'ונסון.

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

הפרק השלישי בסמינר עוסק במספר אלגוריתמים אקראיים לפתרון הבעיה המשיגים ביצועים טובים אף יותר מאלה הדטרמיניסטיים. בפרק מופיעה "שיטת ההסתברויות המותנות", שיטה כללית לדה-רנדומיזציה של אלגוריתמים אקראיים מסוימים ההופכת אותם לאלגוריתמים דטרמיניסטיים המבטיחים ביצועים השווים לביצועיהם הממוצעים לפני ההמרה. בפרק זה מוצגים חמישה אלגוריתמים: שני האלגוריתמים הפשוטים Random ו-GenRandom אשר בוחרים את השמת ערכי האמת באקראי לפי התפלגות נתונה, אלגוריתם ה-¾-קירוב של Goemans-Williamson אותו הציגו השניים במאמר

אלגוריתם ¾-קירוב פשוט נוסף המנצל את שיטתם של Goemans-Williamson באופן אחר, והאלגוריתם של Yannakakis, גם הוא אלגוריתם ¾-קירוב, אשר הופיע במאמר. ניתן להשתמש בשיטת ההסתברויות המותנות על מנת להפוך את כל האלגוריתמים הללו לדטרמיניסטיים.

ביבליוגרפיה לדוגמא (בעבודה האקדמית כ-20 מקורות אקדמיים באנגלית ובעברית)

1)      R. Battiti and M. Protasi, Approximate algorithms and heuristics for MAX-SAT, Handbook of combinatorial optimization , pp. 77-148

2)      J. Chen, D. K. Friesen and H. Zheng, Tight bound on the Johnson’s algorithm for Max-SAT, Proc. 12th Annual IEEE Conf. On Computational Complexity , Ulm, Germany, pp. 274-281

3)      D.S. Johnson, Approximation algorithms for combinatorial problems, journal of Computer and System Sciences 9 , pp. 256-278


העבודה האקדמית בקובץ וורד פתוח, ניתן לעריכה והכנסת פרטיך. גופן דיויד 12, רווח 1.5. שתי שניות לאחר הרכישה, קובץ העבודה האקדמית ייפתח לך באתר מיידית אוטומטית + יישלח קובץ גיבוי וקבלה למייל שהזנת

‏290.00 ₪ לקוחות חוזרים, הקישו קוד קופון:


שדה אימייל הינו חובה