ΔΙΔΑΣΚΩΝ: Θεόδουλος Γαρεφαλάκης, Γ216, tgaref@uoc.gr
ΩΡΕΣ ΔΙΔΑΣΚΑΛΙΑΣ: Δευτέρα 11 - 1 (Α208), Τετάρτη 1-3 (Α208)
ΣΥΓΓΡΑΜΜΑΤΑ:
ΑΠΟΤΕΛΕΣΜΑΤΑ ΕΞΕΤΑΣΕΩΝ
Επαναλάβαμε βασικούς ορισμούς και έννοιες σχετικές με ομάδες και δακτυλίους. Ορίσαμε τη χαρακτηριστική μίας ακέραιας περιοχής. Είδαμε την έννοια του ιδεώδους και ορίσαμε το δακτύλιο πηλίκο. Ορίσαμε την σχέση διαιρετότητας σε ακέραια περιοχή και τις έννοιες του πρώτου και του ανάγωγου στοιχείου. Δείξαμε ότι κάθε πρώτο στοιχείο είναι ανάγωγο.
\( \) Ορίσαμε τα μεγιστικά και τα πρώτα ιδεώδη. Δείξαμε ότι το ιδεώδες $I$ της α.π. $R$ είναι μεγιστικό αν και μόνο αν ο δακτύλιος $R/I$ είναι σώμα. Επίσης δείξαμε ότι το ιδεώδες $I$ είναι πρώτο αν και μόνο αν ο δακτύλιος $R/I$ είναι α.π.
Εάν $R$ είναι μια περιοχή κυρίων ιδεωδών, τότε το $p\in R$ είναι πρώτο στοιχείο αν και μόνο αν $(p)$ είναι πρώτο ιδεώδες. Αντίστοιχα, το $m\in R$ είναι ανάγωγο στοιχείο αν και μόνο αν το $(m)$ είναι μεγιστικό ιδεώδες.
Έχουμε ήδη δει ότι κάθε πρώτο στοιχείο είναι ανάγωγο. Από τα παραπάνω προκύπτει ότι σε μια περιοχή κυρίων ιδεωδών κάθε ανάγωγο στοιχείο είναι πρώτο. Άρα σε περιοχές κυρίων ιδεωδών οι έννοιες του πρώτου και του ανάγωγου στοιχείου συμπίπτουν.
Δείξαμε ότι σε μία περιοχή κυρίων ιδεωδών κάθε μη μηδενικό, μη αντιστρέψιμο στοιχείο γράφεται, κατ' ουσίαν μοναδικά, ως γινόμενο αναγώγων. Ορίσαμε την έννοια της Ευκλείδιας περιοχής και δείξαμε ότι κάθε Ευκλείδια περιοχή είναι περιοχή κυρίων ιδεωδών. Παραδείγματα Ευκλείδιων περιοχών είναι ο δακτύλιος των ακεραίων αριθμών καθώς και κάθε πολυωνυμικός δακτύλιος σε μία μεταβλητή πάνω από σώμα. Είδαμε τον Ευκλείδιο αλγόριθμο.
\(\) Ορίσαμε βασικές έννοιες της θεωρίας σωμάτων: επέκταση σωμάτων, βαθμό επέκτασης, αλγεβρικό στοιχείο, ελάχιστο πολυώνυμο αλγεβρικού στοιχείου. Δείξαμε επίσης κάποιες βασικές προτάσεις: Εάν $F\subseteq L \subseteq K$ είναι πύργος σωμάτων, τότε για οι βαθμοί των εμπλεκόμενων επεκτάσεων συνδέονται με τη σχέση $[K:F] = [K:L]\cdot [L:F]$. Επίσης, δειξαμε ότι το ελάχιστο πολυώνυμο $\min(\alpha,F)$, του στοιχείου $\alpha$ πάνω από το σώμα $F$ είναι ανάγωγο στο δακτύλιο $F[X]$.
Μελετήσαμε την απλή επέκταση $F(\alpha)$ του σώματος $F$, όπου $\alpha$ είναι αλγεβρικό στοιχείο πάνω από το $F$ με ελάχιστο πολυώνυμο $p(X)$. Δείξαμε ότι το $F(\alpha)$ είναι ισόμορφο με το σώμα $F[X]/(p(X))$.
Είδαμε πώς δεδομένου ενός σώματος $F$ και ενός πολυωνύμου $f\in F[X]$ μπορούμε να κατασκευάσουμε μία επέκταση του $F$ η οποία περιέχει όλες τις ρίζες του $f$.
\(\)Ορίσαμε την αλγεβρική θήκη ενός σώματος $F$ και τη συμβολίσαμε με $\bar{F}$. Κάθε σώμα έχει αλγεβρική θήκη. Δείξαμε ότι ένα πεπερασμένο σώμα έχει θετική χαρακτηριστική, η οποία είναι πρώτος αριθμός. Αν $F$ είναι ένα πεπερασμένο σώμα χαρακτηριστικής $p$, τότε περιέχει μία ισόμορφη εικόνα του σώματος $\mathbb{Z}/(p)$. Ταυτίσαμε την εικόνα με το σώμα $\mathbb{Z}/(p)$ (το οποίο θα συμβολίζουμε με $\mathbb{F}_p$). Έτσι το σώμα $F$ είναι μία πεπερασμένη επέκταση του $\mathbb{F}_p$. Αν $n$ είναι ο βαθμός της επέκτασης, τότε $|F|=p^n$. Είδαμε παραδείγματα.
\(\)Δείξαμε ότι αν $K$ είναι ένα σώμα και $G$ είναι μια πεπερασμένη υποομάδα της πολλαπλασιαστικής ομάδας $K^{*}$, τότε η $G$ είναι κυκλική. Συμπεράναμε ότι η πολλαπλασιαστική ομάδα κάθε πεπερασμένου σώματος είναι κυκλική.
Δείξαμε ότι αν $F$ είναι σώμα χαρακτηριστικής $p$ και $a,b\in F$, τότε $(a+b)^{p^m} = a^{p^m} + b^{p^m}$ για κάθε $m\in \mathbb{N}$.
Αποδείξαμε ότι για κάθε πρώτο αριθμό $p$ και κάθε φυσικό αριθμό $n$ υπάρχει μοναδική επέκταση του σώματος $\mathbb{F}_p$ βαθμού $n$ εντός μίας δεδομένης αλγεβρικής θήκης. Εάν λοιπόν σταθεροποιήσουμε μία αλγεβρική θήκη του $\mathbb{F}_p$, τότε υπάρχει μοναδικό σώμα με $p^n$ στοιχεία, το οποίο συμβλίζουμε με $\mathbb{F}_{p^n}$. Τα στοιχεία του $\mathbb{F}_{p^n}$ χαρακτηρίζονται ως εξής: $\alpha \in \mathbb{F}_{p^n}\ \Longleftrightarrow\ \alpha^{p^n} = \alpha$.
\(\)Έστω $f\in \mathbb{F}[X]$ ένα ανάγωγο πολύώνυμο βαθμού $n$ και $\alpha$ μία ρίζα του. Δείξαμε ότι το σύνολο των ριζών του $f$ είναι το $\{\alpha, \alpha^p,\ldots, \alpha^{p^{n-1}}\}$. Ειδικότερα, οι ρίζες είναι απλές.
Δείξαμε ότι $m|n \ \Longleftrightarrow\ \mathbb{F}_{p^m} \subseteq \mathbb{F}_{p^n}$. Είδαμε παραδείγματα.
Για φυσικό αριθμό $n$ συμβολίζουμε με $I_n$ το σύνολο των μονικών αναγώγων πολυωνύμων του $\mathbb{F}_p[X]$ και με $\pi(n)$ το πλήθος των στοιχείων του $I_n$. Δείξαμε ότι
\[ X^{p^n}-X = \prod_{d|n}\ \prod_{f\in I_d}\ f \]
Δηλαδή το πολυώνυμο $X^{p^n}-X$ είναι το γινόμενο όλων των μονικών αναγώγων βαθμού που διαιρεί το $n$. Ως πόρισμα έχουμε
\[ \pi(n) = \frac{1}{n}\ \sum_{d|n}\ \mu(d) p^{n/d}\]
όπου $\mu$ είναι η συνάρτηση του Moebius.
\(\)Ορίσαμε τα κυκλοτομικά πολυώνυμα. Έαν $p$ είναι πρώτος και $n$ φυσικός αριθμός πρώτος προς το $p$, ορίζουμε
\[ \Psi_n = \prod_{0\leq j<n, \\ (j,n)=1} (X-\omega^j), \]
όπου $\omega\in \bar{\mathbb{F}}_p$ είναι μία πρωταρχική $n$-οστη ρίζα της μονάδας. Δηλαδή, το $\Psi_n$ είναι το μονικό πολυώνυμο με ρίζες ακριβώς τις πρωταρχικές $n$-οστες ρίζες της μονάδας. Αποδείξαμε τα παρακάτω.
\(\)Λύσαμε τις ασκήσεις του 2ου φυλλαδίου.
Ορίσαμε την απεικόνιση του ίχνους:
\[ \mathrm{Tr}: \mathbb{F}_{p^n}\ \longrightarrow\ \mathbb{F}_p\ ,\ \ \ \ \mathrm{Tr}(\alpha) = \sum_{i=0}^{n-1} \alpha^{p^i}. \]
Δείξαμε ότι είναι $\mathbb{F}_p$-γραμμική απεικόνιση και δεν είναι η μηδενική απεικόνιση. Άρα η εικόνα είναι το $\mathbb{F}_p$, δηλαδή είναι επί.
\(\)Δείξαμε ότι $\mathrm{dim} \mathrm{im}(\mathrm{Tr}) = 1$ και $\mathrm{dim} \mathrm{ker}(\mathrm{Tr}) = n-1$.
Δείξαμε ότι για κάθε $\alpha\in \mathbb{F}_{p^n}$, $\mathrm{Tr}(\alpha^p)=\mathrm{Tr}(\alpha)$. Δηλαδή οι ρίζες ενός αναγώγου πολυωνύμου βαθμού $m$ όπου $m|n$ (οι οποίες θα βρίσκονται στο $\mathbb{F}_{p^n}$), έχουν κοινό ίχνος. Δείξαμε ότι αν το στοιχείο $\alpha \in \mathbb{F}_{p^n}$ έχει ελάχιστο πολυώνυμο $P_{\alpha}(X)=X^m\ +\ c_{m-1}\ \ X^{m-1}\ +\ \cdots\ +\ c_0$, όπου φυσικά $m|n$, έχουμε
\[ \mathrm{Tr}(\alpha) = - \frac{n}{m} c_{m-1} \]
Επίσης, δείξαμε ότι
\[ \alpha \in \mathrm{ker}(\mathrm{Tr})\ \ \Longleftrightarrow\ \ \exists \beta\in \mathbb{F}_{p^n}\ \ :\ \ \alpha = \beta^p - \beta \]
Λύσαμε τις ασκήσεις του 3ου φυλλάδίου.
\(\)Ορίσαμε τις βασικές έννοιες της θεωρίας κωδίκων. Ειδικότερα, ορίσαμε την έννοια του γραμμικού κώδικα πάνω από το $\mathbb{F}_q$, το μήκος και τη διάσταση του. Ορίσαμε την έννοια της απόστασης και του βάρους Hamming. Ορίσαμε την ελάχιστη απόσταση ενός κώδικα. Είδαμε παραδείγματα.
Ορίσαμε τον πίνακα βάσης (ή γεννήτορα πίνακα) και τον πίνακα ελέγχου ενός γραμμικού κώδικα. Δείξαμε ότι η ελάχιστη απόσταση ενός γραμμικού κώδικα $C$ είναι ίση με το ελάχιστο πλήθος γραμμικώς εξαρτημένων στηλών ενός πίνακα ελέγχουν του $C$. Είδαμε παραδείγματα.
Ειδαμε την αποκωδικοποίηση με σύνδρομα. Ορίσαμε του κώδικες Hamming.
ΔΙΑΚΟΠΕΣ ΠΑΣΧΑ
ΔΙΑΚΟΠΕΣ ΠΑΣΧΑ
\(\)Ορίσαμε τους κώδικες Hamming, $\mathrm{Ham}(r,q)$ πάνω από το σώμα $\mathbb{F}_q$ και δείξαμε ότι έχουν παραμέτρους $[(q^r-1)/(q-1), (q^r-1)/(q-1) - r, 3]$.
Μιλήσαμε για την έννοια της ισοδυναμίας κωδίκων. Δύο κώδικες ονομάζονται ισοδύναμοι εάν ο ένας μπορεί να προκυψει από τον άλλο με μία μετάθεση των συντεταγμένων και πολαπλασιαμό των συντεταγμένων με μη μηδενική σταθερά (κάθε συντεταγμένη μπορεί να πολλαπλασιαστεί με διαφορετική σταθερά). Για πράδειγμα, η παρακάτων απεικόνιση δίνει ισοδύναμους κώδικες (για $n=4$)
\[ \phi : (c_1,c_2,c_3,c_4)\ \mapsto\ (\lambda_2 c_2, \lambda_3 c_3, \lambda_1 c_1, \lambda_4 c_4) \]
Δείξαμε το φράγμα του Hamming: Κάθε κώδικας $C$ με μήκος $n$ και ελάχιστη απόσταση $d$, πάνω από ένα αλφάβητο με $q$ σύμβολα ικανοποιεί την ανισότητα
\[ |C| \leq \frac{q^n}{\sum_{i=0}^{e}\ \binom{n}{i} (q-1)^i } \]
όπου $e=\lfloor (d-1)/2 \rfloor$.
Δείξαμε ότι οι κώδικες Hamming ικανοποιούν το φράγμα με ισότητα. Κάθε κώδικας που "πιάνει" την ισότητα στο φράγμα του Hamming ονομάζεται τέλειος (perfect).
Λύσαμε τις ασκήσεις του φυλλαδίου 4.
\(\)Για κάθε γραμμικό κώδικα $C$ με παραμέτορυς $[n,k,d]$ ισχύει το φράγμα του Singleton: $d\leq n-k+1$. Εάν ισχύει $d=n-k+1$ τότε ο κώδικας $C$ ονομάζεται MDS.
Δείξαμε ότι ο κώδικας $C$ είναι MDS αν και μόνο αν ο $C^{\perp}$ είναι MDS.
Ορίσαμε τους γενικεύμένους κώδικες Reed-Solomon και δείξαμε ότι είναι MDS.
Δείξαμε ότι έαν $C$ είναι ένας MDS κώδικας πάνω από το $\mathbb{F}_q$ με παραμέτρους $[n,k,n-k+1]$, τότε είτε $k\leq 1$ ή $n\leq q + k-1$.
Λύσαμε τις ασκήσεις του φυλλαδίου 5.
Λύσαμε ασκήσεις από το φυλλάδιο επαναληπτικών ασκήσεων.
Site pages
Current course
Participants
ΕΦΑΡΜΟΣΜΕΝΗ ΑΛΓΕΒΡΑ
6 February - 12 February
13 February - 19 February
20 February - 26 February
27 February - 5 March
6 March - 12 March
13 March - 19 March
20 March - 26 March
27 March - 2 April
3 April - 9 April
10 April - 16 April
17 April - 23 April
24 April - 30 April
1 May - 7 May
8 May - 14 May
15 May - 21 May
22 May - 28 May