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

ספר הקורס

ההרצאות מבוססות באופן כללי על הספר Abstarct Algebra - Theory and Applications by Thomas W. Judson

נושאי ההרצאות

הרצאה 1 הקדמה; הסבר על קידוד והצפנה, מבוא למבנים אלגבריים

קידוד הוא שיטה להעברת מידע ובין היתר מטרתו היא להבטיח את נכונות המידע ולזהות (ולתקן) שגיאות.

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

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

הרצאה 2 חבורות ותת חבורות; פרקים 3,4 מהספר

[math]\displaystyle{ \mathbb{Z},\mathbb{Z}_n,{GL}_n,{SL}_n,S_n }[/math], קווטרניונים, מעגל היחידה ושורשי יחידה, המרוכבים ללא אפס כתת חבורה של מטריצות ממשיות בגודל 2 על 2.

כתיב אקספוננט [math]\displaystyle{ g^n=g\cdots g }[/math] או כפל [math]\displaystyle{ ng=g+\cdots+g }[/math] בהתאם לסימון פעולת החבורה.

הגדרה של תת חבורות ציקליות, סדר של איבר. סדר האיבר הוא גודל החבורה הציקלית.

הרצאה 3 חבורת תמורות; פרק 5 מהספר

סימן של תמורה, סימן של הרכבת תמורות

הרצאות 4-5 קוסטים (מחלקות שקילות), אינדקס של תת חבורה, חבורת אוילר, משפטי לגראנג', אוילר ופרמה; פרק 6 מהספר

לפני הרצאות אלו, בבקשה חזרו על הנושא של יחסי שקילות. ניתן לצפות בסרטון הבא:

הרצאות 6-7 הצפנה סימטרית (מפתח פרטי), הצפנה אסימטרית (מפתח ציבורי), חתימה; פרק 7 מהספר

הצפנות סימטריות וחוזקן, RSA, דיפי-הלמן.

הרצאות 8-9 משפט האיזומורפיזם; פרקים 9,10,11 מהספר

הומומורפיזמים, תת חבורות נורמליות, חבורות מנה, משפט האיזומורפיזם הראשון.

הדגמה על ידי חבורת המודולו, מותר להפעיל את המודולו בכל שלב שנרצה.

הרצאה 10 קידוד; פרק 8 מהספר

קידוד, ספרת ביקורת של תעודת זהות, קוד לינארי, קוד המינג. ֿ checksum בפרוטוקולי IP, TCP, UDP.

הרצאה 11 חוג הפולינומים; פרקים 16,17 מהספר

ֿ חלוקה עם שארית, אידיאלים.

הרצאה 12 קודים ציקליים; פרק 22 מהספר

השדה הבינארי, קודים פולינומיים.

CRC בשימוש פרוטוקול Ethernet.