אלגוריתם מטריצה

[עריסטו]

אלגוריתם מטריצה

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

 

[ש ב ו ז]

אולי כך...

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

 

[עריסטו]

אבל כאשר אתה מכפיל את הטור

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

 

[ron369]

הממ...בוא נבדוק משהו.

1 -1 -1 1​

ברור שהקפל קומוטטיבי, ולכן אחרי כמות כלשהי של הכפלות נקבל:

c d a-> ac -ad b-> -bc bd​

נניח ש a,b או c,d חיוביים. אחרת, נסובב את המטריצה, ונחזור למצב הישן (כמעט, אבל מספיק קרוב).

1) ac > ad => c>d 2) ac > bc => a>b 3) bd > bc => d>c 4) bd > ad => b>a (for 1: ac+ (-ad)>0 => ac>ad)​

סתירה, לא?

 

[ron369]

סתירה מס' 2 (רק אחרי מס' 1!)

נסתור את הסתירה לכאורה. תהי מטריצה. נבחר עמודה ושורה כלשהן. r,c (וקטורים). נדאג שנקודת המפגש ביניהם תהיה חיובית. וכעת, לכל אחד מהאיברים ב-r,c, בפרט לנקודת המפגש שלהם, בבירור יש שורה או עמודה, אשר משותפות רק לו (זה טריוויאלי בטירוף). נדאג שכל אחת מהנקודות האלו תהיה חיובית. כלומר, קיבלנו שורה חיובית ועמודה חיובית. כעת, נכפיל את השורה והעמודה בפלוס אינסוף, וסיימנו. סיבוכיות: O(N^2) במימוש מתאים (או, אם תרצה, O(MN) עבור מטריצה מסדר NXM), אם אני לא טועה.

 

[ron369]

אה, ולשניכם - אכזבתם אותי

מה אתם לא פותרים כזו בעיה קלה?

 

[עריסטו]

פתרון אחר + שאלה

קודם כל השאלה: לא הבנתי את הפתרון שלך...

אפשר לקבל דוגמה? חוץ מזה פתרתי את השאלה המקורית בדרך אחרת: האלגוריתם שלי - בכל צעד בוחרים שורה כלשהי או עמודה כלשהי שסכום המספרים בהן שלילי, ומכפילים את איברי השורה/העמודה ב - 1-. האלגוריתם חייב לעצור כי סכום המספרים במטריצה גדל בכל צעד כזה, ומספר האפשרויות לאיברי המטריצה סופי.

 

[עריסטו]

הסבר מה לא הבנתי

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

 

[עריסטו]

אולי הבנתי

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

 

[ron369]

הממ, חשבתי שאין אפסים ../images/Emo13.gif

 

[ron369]

פתרון נחמד מאד ../images/Emo13.gif

 

[גיל14]

הוא אמר מספר ממשי.

 

[ron369]

אז מה?

לא הבנתי את הקשר (אבל כן, האלגוריתם שלי הופרך באלגנטיות).

 

[ש ב ו ז]

אני ממש לא בטוח שהאלגוריתם שלך הופר

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

 

[ron369]

מה? אני לא בטוח שהבנתי,

אבל זה יכול ליצור בעיות. למשל, אם יש אפסים גם בשורות, וגם בעמודות... למשל, מה אם הטור והשורה כולם אפסים?

 

[עריסטו]

לא הבנתי

נניח שהשורה היא שורה 1 והטור הוא טור 1, ובשורה 1 טור 2 יש 0, וגם בטור 1 שורה 2 יש 0. אתה אומר שאם סכום המספרים בטור 2 שלילי נכפיל את טור 2 ב - 1-. נניח שעשינו כך. אבל עכשיו יכול להיות שסכום המספרים בשורה 2 הוא שלילי. מה נעשה? נכפיל את שורה 2 ב - 1-? זה יכול לגרום לסכום שלילי בטור חדש שבראשו יש אפס, וכן הלאה...

 

[ש ב ו ז]

לא עכשיו נכפיל את הטור והשורה

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

 

[עריסטו]

לא עונה לי... (אם הבנתי נכון)

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

 

[ש ב ו ז]

וכן הלאה. לא עד אין סוף.

 

[עריסטו]

איך אתה יודע שהתהליך

לא יימשך עד אינסוף?