מבנים אלגבריים למדעי המחשב - ארז שיינר: הבדלים בין גרסאות בדף

מתוך Math-Wiki
שורה 10: שורה 10:


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


===הרצאה 2 חבורות ותת חבורות; פרקים 3,4 מ[http://abstract.ups.edu/aata/ הספר] ===
===הרצאה 2 חבורות ותת חבורות; פרקים 3,4 מ[http://abstract.ups.edu/aata/ הספר] ===
שורה 25: שורה 26:
סדר של איבר, תת חבורה ציקלית, סדר האיבר הוא גודל החבורה הציקלית.
סדר של איבר, תת חבורה ציקלית, סדר האיבר הוא גודל החבורה הציקלית.


===הרצאה 3 חבורת תמורות, הומומורפיזמים, איזומורפיזמים, משפט קיילי; פרקים 5,9 מ[http://abstract.ups.edu/aata/ הספר] ===
 
===הרצאה 3 חבורת תמורות, סימן התמורה; פרק 5 מ[http://abstract.ups.edu/aata/ הספר] ===


הגדרת סימן של תמורה לפי חלוקת פולינומים, הוכחת כפליות הסימן.
הגדרת סימן של תמורה לפי חלוקת פולינומים, הוכחת כפליות הסימן.


הצגת תמורה כמחזורים זרים, הצגת מחזורים כהרכבה של חילופים, סימן חילוף הוא שלילי.
הצגת תמורה כמחזורים זרים, הצגת מחזורים כהרכבה של חילופים, סימן חילוף הוא שלילי.
===הרצאה 4 הומומורפיזמים, איזומורפיזמים, משפט קיילי, משפט לגראנג'; פרקים 9 ו6 מ[http://abstract.ups.edu/aata/ הספר] ===


הומומורפיזמים, איזומורפיזמים.
הומומורפיזמים, איזומורפיזמים.
שורה 37: שורה 42:
משפט קיילי- כל חבורה איזומורפית לתת חבורה של חבורת תמורות.
משפט קיילי- כל חבורה איזומורפית לתת חבורה של חבורת תמורות.


===הרצאות 4-5 קוסטים (מחלקות שקילות), אינדקס של תת חבורה, חבורת אוילר, משפטי לגראנג', אוילר ופרמה; פרק 6 מ[http://abstract.ups.edu/aata/ הספר]===
תת חבורה מחלקת חבורה למחלקות שקילות (קוסטים) שוות בגודלן לגודל תת החבורה.
לפני הרצאות אלו, בבקשה חזרו על הנושא של יחסי שקילות. ניתן לצפות בסרטון הבא:
 
אינדקס תת החבורה הוא מספר מחלקות השקילות שהיא מייצרת בחבורה, וזה בדיוק גודל החבורה חלקי גודל תת החבורה (משפט לגראנג').
 
בחבורה סופית, לכל איבר יש סדר סופי ותת חבורה צקלית בגודל סדר האיבר. לכן סדר כל איבר מחלק את גודל החבורה.
 
חבורה מגודל ראשוני חייבת להיות ציקלית, וכל איבר פרט לאיבר היחידה יוצר אותה.
 
*לפני הרצאה זו, חזרו בבקשה על הנושא של יחסי שקילות. ניתן לצפות בסרטון הבא:


<videoflash>jKprPSfRysE</videoflash>
<videoflash>jKprPSfRysE</videoflash>
===הרצאה 5 חבורת אוילר, משפטי אוילר ופרמה; פרק 6 מ[http://abstract.ups.edu/aata/ הספר]===




שורה 46: שורה 63:


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


===הרצאות 8-9 משפט האיזומורפיזם; פרקים 10,11 מ[http://abstract.ups.edu/aata/ הספר]===
===הרצאות 8-9 משפט האיזומורפיזם; פרקים 10,11 מ[http://abstract.ups.edu/aata/ הספר]===
שורה 52: שורה 70:


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


===הרצאה 10 קידוד; פרק 8 מ[http://abstract.ups.edu/aata/ הספר]===
===הרצאה 10 קידוד; פרק 8 מ[http://abstract.ups.edu/aata/ הספר]===
שורה 58: שורה 77:


checksum בפרוטוקולי IP, TCP, UDP.
checksum בפרוטוקולי IP, TCP, UDP.


===הרצאה 11 חוג הפולינומים; פרקים 16,17 מ[http://abstract.ups.edu/aata/ הספר]===
===הרצאה 11 חוג הפולינומים; פרקים 16,17 מ[http://abstract.ups.edu/aata/ הספר]===
חלוקה עם שארית, אידיאלים.
חלוקה עם שארית, אידיאלים.


===הרצאה 12 קודים ציקליים; פרק 22 מ[http://abstract.ups.edu/aata/ הספר]===
===הרצאה 12 קודים ציקליים; פרק 22 מ[http://abstract.ups.edu/aata/ הספר]===

גרסה מ־12:48, 9 בנובמבר 2017

ספר הקורס

ההרצאות מבוססות באופן כללי על הספר 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 הומומורפיזמים, איזומורפיזמים, משפט קיילי, משפט לגראנג'; פרקים 9 ו6 מהספר

הומומורפיזמים, איזומורפיזמים.

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

משפט קיילי- כל חבורה איזומורפית לתת חבורה של חבורת תמורות.

תת חבורה מחלקת חבורה למחלקות שקילות (קוסטים) שוות בגודלן לגודל תת החבורה.

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

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

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

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


הרצאה 5 חבורת אוילר, משפטי אוילר ופרמה; פרק 6 מהספר

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

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


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

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

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


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

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

checksum בפרוטוקולי IP, TCP, UDP.


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

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


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

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

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