수업일지 - 확률과 랜덤변수(01-1)

수업일지 -- 유한체이론 및 응용, 2001학년도 1학기, 전기전자공학과

여러분이 이 페이지를 읽는 날짜를 기준으로 하여

이전의 기록은 이미 수업시간에 다루었던 내용을 간추린 것이고 이후의 기록은 대략적인 계획입니다.

자주 들러서 예습/복습에 도움이 되기를 바라며, 열심히 공부하기 바랍니다.

담당교수: 송홍엽

최종 합계 성적 2001년 6월 29일.

FIRST QUARTER (GO TO 1 st 2nd 3rd 4th quarter; top today bottom )

1주

3월 2일(금3) 개강.

수업 계획서 배포, 교재소개, class rule 설명, 출석부확인, 5회 무단결석 = F학점, 사전 통보(이메일, 전화, 쪽지)한 경우는 무단결석 아님.
quiz and solution

3월 7일(수23)

Chapter 1 Prologue
Field, infinite, finite
integers mod p
Chapter 2 Euclidean Domains and Euclid's Algorithm (Theorem 2.1)
Integral Domain, Euclidean Domain, GCD
Three examples of ED: Integers, Polynomials over a field, Gaussian integers
Theorem 2.1 Over ED, GCD always exists and expressible as a linear combination

2주

3월 9일(금3)

Problem 2-10: 문제 수정
Euclid's Algorithm: Proof and Extended Version, examples
Chapter 3 Unique Factorization in Euclidean Domains (Theorem 3.6)
- units, associates, prime, relatively prime
- Five Lemmas for Theorem 3.6
HW#1: Chapter 2: 2,3,4,10,11, and Chapter 3: 2,6,8,9,11
박사과정 수강생의 지정 topic 선정: 학기 후반부에 약 3시간씩 발표예정
- Exponential Sum, Finite Geometry, Coding Theory, all from the book "Intro. to Finite Fields..." by Lidl and Niederreiter

3월 14일(수23)

Theorem 3.6
Chapter 4 Building Fields from Euclidean Domains (Theorem 4.1 and many examples)
Chapter 4 Problems: 9,10,11 -- to be included in HW#2
Everything of Chapter 4 was covered except for one last long example.

3주

3월 16일(금3)

HW#1 collected
Last example of Chapter 4 and a little more.
Theorem: Given a size q, there exists one and only one field of size q up to isomorphism.
Some concept from Linear Algebra
- def of group, field, vector space, subspace
- number of k-dim subspaces of Vn over F2
- sum and product of subspaces

3월 21일(수23)

Some concept from Linear Algebra
- Linear Transformation, null space, range space, some examples
- homomorphism, isomorphism, and automorphism
some results of group theory
- subgroup, index, cosets, etc
Chapter 5 begins
- Theorem 5.1: a FF with size q -> q=p^m for some prime p and integer m>0.
- Theorem 5.2: a=nonzero element of FF of size q -> ord(a) divides q-1.

4주

3월 23일(금3)

Chapter 5 continues. Let F be a finite field of size q.
- Lemma 5.3: if p(x) over F is of degree m, then p(x)=0 has at most m roots over F.
- Lemma 5.4: if alpha in F has order n, then the order of alpha to the s is equal to n divided by gcd(s,n).
- Theorem 5.5: if t is a positive integer, then F contains either no elements of order t or exactly phi(t) elements of order t.
- Theorem 5.6: summation of phi(d) over all divisors d of n is equal to n. (proof: self-exercise)
- Theorem 5.7: if t divides q-1 then F contains exactly phi(t) elements of order t.

3월 28일(수23)

HW#2 (10 문항) due: Chapter 5가 끝나는 시간의 다음 수업시간 시작시.
- Chapter 4: 9, 10, 11
- Extra Proof that dimension of V is equal to nullity and rank of a linear transformation T from V.
- Chapter 5: 3, 4, 6, 7, 8, 14

Chapter 5 continues.
- Gauss Algorithm of finding a primitive elements: Big example with F of size 25.
- Lemma 5.8: if ord(alpha)=m and ord(beta)=n, and (m,n)=1, then ord(alpha beta)=mn.
- minimal polynomials: definitions and existence.
- Theorem 5.9: F is a field with size p^m. For each alpha in F, there exists a unique monic polynomial p(x) in F_p [x] such that (1) p(alpha)=0, (2) deg(p) <= m, and (3) if f(x) in F_p [x] satisfies f(alpha)=0 then p(x) divides f(x).
- def: such a polynomial p(x) is called the minimal polynomial of alpha with respect to F_p.
- NOTE: minimal polynomial is irreducible.
- when alpha is a primitive element the p(x) is called primitive polynomial.

SECOND QUARTER (GO TO 1st 2nd 3rd 4th quarter; top today bottom )

5주

3월 30일(금3) Finish Chapter 5.

We assume that F is a finite field of size q^n and K is its subfield of size q. We assume that alpha is an element of F.

Lemma 5.10: alpha in F of size q^n is in fact an element of K of size q (K is a subfield of F) if and only if alpha^q = alpha.

Lemma 5.11: p choose k is a multiple of p for k=1,2,...,p-1. p=prime.
Lemma 5.12: char(F)=p. then (alpha + beta)^p = alpha^p + beta^p
def: conjugates of alpha in F (of size q^n) with respect to K (of size q, and K is a subfield of F) are alpha, alpha^q, alpha^(q^2), alpha^(q^3),....
Number of conjugates of alpha with respect to K is called the degree of alpha with respect to K.
Theorem 5.13: the degree d of alpha is a divisor of n. it is the smallest positive integer such that q^d = 1 (mod ord(alpha)). Furthermore, if a=b (mod d) then alpha^(q^a)=alpha^(q^b).
Theorem 5.14: the minimal polynomial of alpha in F with respect to K is given by (x-alpha)(x-alpha^q)(x-alpha^(q^2))...(x-alpha^(q^(d-1))) where d is the degree of alpha with respect to K.
Example 5.8: self-exercise.
HW#2 - due next Wed.

4월 4일(수23) Chapter 6 (Existence, Uniqueness, and subfields)

HW#2 collected
Review of materials covered so far
- ch4: construction of a finite field of size q
- ch5: abstract properties of a finite field of size q; def and properties of minimal polynomials
Existence & uniqueness & subfields
Theorem 6.1: x^(q^n) - x is the product of V_d(x) over all the divisors d of n, where V_d(x) is the product of all the monic irreducible polynomials of degree d over K of size q.
Corollary 6.2: q^n = summation of d I_d over all the divisors d of n, where I_d is the number of monic irreducible polynomials of degree d over K.
Another proof of Cor 6.2 --- read, study, and summerize it as an extra problem #1 of HW#3
definition of mu(n) for n=1,2,... called Mobius-mu function
properties of mu(n):
- it is multiplicative, i.e. if (a,b)=1 then mu(ab)=mu(a) mu(b): easy proof
- for n>1, the summation of mu(d) over all the divisors d of n becomes 0: proof by induction.

6주

4월 6일(금3) Chapter 6 (finish)

Theorme 6.3 mobius inversion formula
Theprem 6.4 Existence of a finite field of size p^m for a prime p and an integer m>0
Theorem 6.5 Uniqueness of a finite field of size p^m for a prime p and an integer m>0
read, study, and summerize the proof of Theorem 6.5 as an extra problem #2 of HW#3
Theorem 6.6 Existence of a subfiled of GF(p^m)
75 pages out of 150 pages up to Chapter 9 have been covered so far.

4월 11일(수23) Chapter 7

n-th cyclotomic polynomial over C
n-th cyclotomic polynomial over GF(q) of char=p
theorem 7.1: some relations on cyclotomic polynomials
theorem 7.2: existence and factoring of n-th cyclotomic polynomial over GF(q) of char=p
examples

7주

4월 13일(금3) Chapter 7

example 7.4: 180-th cyclotomic polynomial over GF(2)
factorization of n-th cyclotomic polynomial over GF(q)
- never irreducible when n is not of the form 1, 2, 4, p^t, 2p^t.
- when n is of the form 1, 2, 4, p^t, 2p^t, it is
  - irreducible, if q is primitive root mod n
  - not irreducible, otherwise.

Berlekamp algorithm of factoring a polynomial over GF(q)
Theorem 7.3
HW#3 Problems (due: 5월 2일 수요일 수업시간)
- Two extra problems in Chapter 6
- Exercise Problems in Chapter 7: 4,5,6,7,8,9,10,11

4월 18일(수23) Chapter 7

FINISH: Berlekamp algorithm of factoring a polynomial over GF(q)

THIRD QUARTER (GO TO 1st 2nd 3rd 4th quarter; top today bottom )

8주

4월 20일(금3) Chapter 8

definition and properties of trace function from GF(p^t) to GF(p)

4월 25일(수23) - 중간고사 기간 - 수업 없음

9주

4월 27일(금3) - 중간고사 기간 - 수업 없음

5월 2일(수23) Chapter 8

calculation of trace functions
solvability of quadratic equations over GF(q)
HW#4 -- due 5월 23일 (수) 수업시간 시작시
- Chapter 8 Problems: 3, 9, 11, 13, 19 (시험범위에 포함)
- Chapter 9 Problems: 3, 4, 5, 6, 9 (시험범위에 포함 안됨)

10주

5월 4일(금3) Chapter 8

dual basis and bit-serial multiplication over GF(2^m)
4세대 이동통신 워크샵 참석차 휴강: 이 부분은 생략합니다.
Chapter 8의 HW 연습문제 중에서 이 부분은 생략합니다.

5월 9일(수23) Chapter 9

Linear Recurrence
Properties of LRS (case: f(x) is irreducible)

11주

5월 11일(금3) Chapter 9

Properties of LRS (case: f(x) is irreducible)

5월 16일(수23) 휴강:국제학술대회 참석 및 논문발표 "Sequences and Their Applications," Bergen, Norway.

중간시험 (범위: 처음부터 여기까지) up to Chapter 8 (확정)

-- emphasis on Chapters 5,6,7,8

1. 모든 HW 문제를 복습할 것

2. 위의 모든 Theorem의 증명을 복습할 것 (특히 5장-8장 내에 공부한 모든 Lemma와 Theorem의 증명을 필히 숙지할 것)

3. 그리고도 시간이 있으면 HW에 포함되지 않은 문제를 풀어볼 것.

4. 예상하기로, 문제풀이 5-6개 정도, 증명문제 5-6개 정도. (정확히 2시간)

12주

5월 18일(금3) 휴강:국제학술대회 참석 및 논문발표 "Sequences and Their Applications," Bergen, Norway, 5월 12일 - 5월 18일.

5월 23일(수23) 박사과정 발표 1 (신민호: Exponential Sums)

character
- additive character of a finite field
- multiplicative character of a finite field

FOURTH QUARTER (GO TO 1st 2nd 3rd 4th quarter; top today bottom )

13주

5월 25일(금3) 학과방침으로 휴강합니다.

5월 30일(수23) 박사과정 발표 2 (김일호: Finite Geometries)

Affine geometry of order 2 over field K
Projective geometry of order 2 over field K
Finite Progective Plane of order q: existence is guaranteed if GF(q) exists

14주

6월 1일(금3) special topic - cyclic Hadamard difference sets (part I)

6월 2일(토) 보강: 오전10시 - 1시(3시간) B701 Conference on Chapter 10:

박사과정을 제외한 나머지 수강생은 약 10분-15분의 시간동안

할당된 주제의 내용을 정리하여 발표하기 바랍니다.

발표는 10분, 질의응답 5분. Click this -> "구체적인 내용" for the details.

금일 발표자료를 발표시간 중 이야기 한 모든 내용을 참조하여

수정/보완하여 나에게 다시 email로 보내기 바랍니다.

6월 8일(금) 수업시간 전까지.

이후에 모든 자료를 통합하여 여기에 posting할 계획입니다.

6월 6일(수23) - 현충일 --- 휴일!

15주

6월 8일(금3) special topic - cyclic Hadamard difference sets (part II)

여기까지 기말시험범위....

발표자료: cyclic difference sets

6월 13일(수23) 박사과정 발표 3 (은유창: Bent Function Sequences) 종강일

Class Presentation 평가점수: 구체적인 내용

16주

6월 15일(금3) - 기말고사 시험기간 시작일

6월 25일(월) 오전 10시 - 6월 26일(화) 오전 10시

Take-Home Final

-- come and visit this page for the problem sheets in 25th of June at 10 AM

-- You must submit your answer sheets in A4 size by 10 AM of 26th of June at my office

-- No delay whatsoever will be accepted.

-- 교재 전체에서(6월 8일 수업까지).... 주로 문제풀기 위주임

-- HW문제를 다시 복습하고 중간시험 준비시 공부한 내용을 복습할 것

-- 중간시험 이후 수업시간에 다룬 내용에 대해서 복습할 것

Chapter 10: Linear Feedback Shift Register Sequences
characters of finite fields
finite projective plane
cyclic hadamard difference sets

Final exam download (답안지 제출: 6월 26일 오전 10:00 까지)

If you have a trouble to access the file, call me at x4861 now.

최종성적처리 완료 2001년 6월 29일.

Go Back Home

(GO TO 1st 2nd 3rd 4th quarter; top today bottom )