שינויים

קפיצה אל: ניווט, חיפוש

מבנים אלגבריים למדעי המחשב - ארז שיינר

נוספו 82 בתים, 13:24, 19 בדצמבר 2017
===הרצאה 9 משפט האיזומורפיזם, מבוא לקידוד; פרק 11 מ[http://abstract.ups.edu/aata/ הספר]===
*'''משפט האיזומורפיזם הראשון'''. יהי <math>\varphi:G\to H</math> איזומורפיזם בין חבורות. אזי <math>G/\ker(\varphi)\cong im(\varphi) </math>
*הוכחה:
*כיוון ש <math>\varphi(21)=\varphi(3)</math>, נובע לפי הוכחת משפט האיזומורפיזם הראשון כי <math>21+9\mathbb{Z}=3+9\mathbb{Z}</math>, כלומר אכן מותר לעשות את המודולו בסוף.
===הרצאה 10 קידוד; פרק 8 מ[http://abstract.ups.edu/aata/ הספר]=מבוא לקידוד==== 
*קוד ISBN בעל 10 ספרות, כאשר הספרה האחרונה היא ספרת ביקורת.
*הספרות שייכות לחבורה <math>\mathbb{Z}_{11}</math>, כאשר 9 הספרות הראשונות הן 0-9 והאחרונה יכולה להיות גם X.
*אם נחליף במיקום של זוג ספרות כלשהן נקבל קוד בלתי תקין.
**<math>a_ix_i+a_jx_j-a_ix_j-a_jx_i=(a_i-a_j)(x_i-x_j)\neq 0</math>.
*שימו לב שקוד זה מוגבל במספר הספרות, ואכן כשהוסיפו ספרות שינו אותו באופן דומה במידה מסוימת לתעודת הזהות שנלמד למטהבהמשך.
===הרצאה 10 קידוד; פרק 8 מ[http://abstract.ups.edu/aata/ הספר]===*תעודת זהות בישראל.*כעת עבור ספרת הביקורת של תעודת הזהות אנו לא מרשים שימוש בספרה X ולכן עובדים ב<math>\mathbb{Z}_{10}</math>.
*הבעייה - זה אינו שדה ויש מחלקי אפס. למשל <math>5\cdot 0 = 5\cdot 2</math>, לכן הקוד לעיל לא יזהה בהכרח החלפת ספרה.
*תאור מילולי של חישוב ספרת ביקורת (אלגוריתם Luhn):