U E D R , A S I H C RSS

TAOCP/Basic Concepts

1. 1.1 Algorithms


1.1. μ•Œκ³ λ¦¬μ¦˜ E(μœ ν΄λ¦¬λ“œμ˜ μ•Œκ³ λ¦¬μ¦˜(Euclid's algorithm))

~cpp 
μ–‘μ˜ μ •μˆ˜ mκ³Ό n이 μ£Όμ–΄μ‘Œμ„λ•Œ, κ·Έκ²ƒλ“€μ˜ μ΅œλŒ€κ³΅μ•½μˆ˜(greatest common divisor)
(mκ³Ό n을 λͺ¨λ‘ λ‚˜λˆ„λŠ” κ°€μž₯ 큰 μ–‘μ˜ μ •μˆ˜)λΌ κ΅¬ν•œλ‹€.
E1. [λ‚˜λ¨Έμ§€ κ΅¬ν•˜κΈ°] m을 n으둜 λ‚˜λˆ„κ³  λ‚˜λ¨Έμ§€λΌ r이라 ν•˜μž.(0 <= r < n)
E2. [그것이 0인가?] r = 0 이면, μ•Œκ³ λ¦¬μ¦˜μ€ λλ‚œλ‹€; n이 닡이닀.
E3. [μ„이기] m <- n, n <- r 으둜 μ„μ •ν•œλ‹€, 그리고 E1λ‹¨κ³„λ‘œ λŒμ•„κ°„λ‹€.β– 

~cpp 
Fig 1. μ•Œκ³ λ¦¬μ¦˜ E의 μˆœμ„œλ„

        |<------------------------------------------------------|
       ↓                                                       |
--------------------          ------------------ μ•„λ‹ˆμ˜€   -------------
| E1.λ‚˜λ¨Έμ§€ κ΅¬ν•˜κΈ° |-------->( E2.그것이 0인가? )-------->| E3.μ„이기 |
--------------------          ------------------          -------------
                                        |예
                                       ↓

m = 119 와 n = 544 κ°€ μ£Όμ–΄μ‘Œλ‹€κ³  ν•˜μž
E1 λ‹¨κ³„μ—μ„œ μ‹œμž‘. m을 n으둜 λ‚˜λˆ„λ©΄ λͺ«μ€ 0이고 λ‚˜λ¨Έμ§€λŠ” 119이닀. 그러λ€λ‘œ r <- 119
E2 λ‹¨κ³„μ—μ„œ r β‰  0 이λ€λ‘œ μ μš©λ˜μ§€ μ•ŠλŠ”λ‹€
E3 λ‹¨κ³„μ—μ„œ m <- 544, n <- 119
μ΄κ²ƒμœΌλ‘œ μ²˜μŒμ— m < n 이면 항상 mκ³Ό n이 κ΅ν™˜λœλ‹€λŠ” 것을 μ•Œ 수 μžˆλ‹€
μš°λ¦¬λŠ” λ‹€μŒκ³Ό 같은 μƒˆλ‘œμš΄ λ‹¨κ³„λΌ μΆ”κ°€ν•  수 μžˆλ‹€(κΌ­ ν•„μš”ν•˜μ§„ μ•Šλ‹€)

~cpp 
E0. [m >= n 인지 ν™•μΈν•˜κΈ°] m < n 이라면, m <-> n 을 κ΅ν™˜ν•œλ‹€

E1으둜 λŒμ•„κ°€μ„œ 544/119 = 4+68/119, 그러λ€λ‘œ r <- 68
λ‹€μ‹œ E2λŠ” μ μš©λ˜μ§€μ•Šκ³ 
E3μ—μ„œ m <- 119, n <- 68
λ‹€μŒμˆœν™˜μ—μ„œ r <- 51, m <- 68, n <- 51
λ‹€μŒμ— r <- 17, m <- 51, n <- 17
λ§ˆμ§€λ§‰μœΌλ‘œ 51을 17둜 λ‚˜λˆ„μ—ˆμ„λ•Œ, r <- 0, κ·ΈλŸ¬λ―€λ‘œ E2μ—μ„œ μ•Œκ³ λ¦¬μ¦˜μ€ μ’…λ£Œλœλ‹€
119와 544의 μ΅œλŒ€κ³΅μ•½μˆ˜λŠ” 17이닀


1.2. μ•Œκ³ λ¦¬μ¦˜μ˜ 5가지 μ€‘μš”ν•œ νŠΉμ§•

1) μœ ν•œμ„±(Finiteness)
μ•Œκ³ λ¦¬μ¦˜μ€ μœ ν•œν•œ 단계 후에 항상 μ’…λ£Œλ˜μ–΄μ•Ό ν•œλ‹€

2) λͺ…ν™•μ„±(Definiteness)
μ•Œκ³ λ¦¬μ¦˜μ˜ 각 λ‹¨κ³„λŠ” μ •ν™•νžˆ μ •μ˜λ˜μ–΄μ•Ό ν•œλ‹€

3) μž…λ ₯(Input)
μ•Œκ³ λ¦¬μ¦˜μ€ 0개 μ΄μƒμ˜ μž…λ ₯을 가진닀

4) 좜λ ₯(Output)
μ•Œκ³ λ¦¬μ¦˜μ€ ν•˜λ‚˜ μ΄μƒμ˜ 좜λ ₯을 가진닀

5) νš¨μœ¨μ„±(Effectiveness)
μ•Œκ³ λ¦¬μ¦˜μ€ 보톡 효율적으둜 μˆ˜ν–‰λ˜λ„λ‘ κΈ°λŒ€λœλ‹€


1.3. μ•Œκ³ λ¦¬μ¦˜μ˜ κ°œλ…μ„ μˆ˜ν•™μ  μ§‘ν•©λ‘ μ˜ κ΄€κ³„λ‘œ λ‚˜νƒ€λ‚΄κΈ°

계산적인 방법(computational method)을 4쌍의 (Q,I,Ξ©,f)둜 ν˜•μ‹μ„ κ°–μΆ° μ •μ˜ν•˜μž
QλŠ” 뢀뢄집합 I와 Ξ©λΌ ν¬ν•¨ν•˜λŠ” 집합이닀
fλŠ” Qμ—μ„œ Q μžκΈ°μžμ‹ μœΌλ‘œ κ°€λŠ” ν•¨μˆ˜μ΄λ‹€
Ω의 λͺ¨λ“  μ›μ†Œ q에 λŒ€ν•˜μ—¬ f(q)λŠ” q와 κ°™μ•„μ•Ό ν•œλ‹€.
Q : 계산
I : μž…λ ₯
Ξ© : 좜λ ₯
f : 계산 κ·œμΉ™
집합 I의 μ›μ†Œ x의 μž…λ ₯은 κ³„μ‚°μˆ˜μ—΄, x0, x1, x2,..., λΌ λ‹€μŒκ³Ό 같이 μ •μ˜ν•œλ‹€
~cpp 
	x0 = x	이고	xk + 1 = f(xk) (k >= 0)
Ω에 μ†ν•˜λŠ” xk 에 λŒ€ν•˜μ—¬ kκ°€ κ°€μž₯ μž‘μ€ μ •μˆ˜λΌλ©΄ κ³„μ‚°μˆ˜μ—΄μ€ kλ‹¨κ³„μ—μ„œ μ’…λ£Œλœλ‹€κ³  ν•œλ‹€. 그리고 이 κ²½μš°μ— xλ‘œλΆ€ν„° κ²°κ³Ό xkκ°€ μƒμ„±λœλ‹€κ³  ν•œλ‹€.

μ•Œκ³ λ¦¬μ¦˜ EλŠ” λ‹€μŒκ³Ό 같이 이런 κ΄€κ³„λ‘œ ν˜•μ‹ν™”λœλ‹€.
QλΌ λͺ¨λ“  단일 (n), λͺ¨λ“  μˆœμ„œμžˆλŠ” 쌍 (m,n), λͺ¨λ“  μˆœμ„œμžˆλŠ” 4쌍 (m,n,r,1), (m,n,r,2), (m,n,p,3) (m,n,pλŠ” μ–‘μ˜ μ •μˆ˜, r은 음이 μ•„λ‹Œ μ •μˆ˜)의 집합이라 ν•˜μž.
IλΌ λͺ¨λ“  쌍 (m,n)의 뢀뢄집합이라 ν•˜μž.
Ξ©λΌ λͺ¨λ“  단일 (n)의 뢀뢄집합이라 ν•˜μž.
fλŠ” λ‹€μŒκ³Ό 같이 μ •μ˜λœλ‹€.
~cpp 
f((m,n)) = (m,n,0,1};	f((n)) = (n);
f((m,n,r,1)) = (m, n, m을 n으둜 λ‚˜λˆˆ λ‚˜λ¨Έμ§€, 2);
r = 0 이면 f((m,n,r,2)) = (n), 그렇지 μ•ŠμœΌλ©΄ (m,n,r,3);
f((m,n,p,3)) = (n,p,p,1).

2. 1.3. MIX

이 μ±…μ˜ μˆ˜λ§Žμ€ λΆ€λΆ„μ—μ„œ MIXμ–Έμ–΄κ°€ λ“±μž₯ν•œλ‹€. λ”°λΌμ„œ λ…μžλŠ” 이 μ ˆμ„ 주의 깊게 곡뢀해야 ν•œλ‹€.

2.1. 1.3.1. Description of MIX

2.1.1. μš©μ–΄κ³Ό ν‘œκΈ°λ²•

  • Words( Partitial fieslds of words포함)
    μ—¬μ„ λ°”μ΄νŠΈλ‘œ 이루어진닀. ν•œ λ°”μ΄νŠΈμ—λŠ” 0~63κΉŒμ§€ μˆ«μžκ°€ λ“€μ–΄κ°ˆ 수 μžˆλ‹€. 그림으둜 λ‚˜νƒ€λ‚΄λ©΄ λ‹€μŒκ³Ό κ°™λ‹€.
    0 1 2 3 4 5
    Β± Byte Byte Byte Byte Byte
    ν•„λ“œ μ œν•œμ΄ μ£Όμ–΄μ§ˆ 수 μžˆλ‹€. ν˜•μ‹μ€ (L:R)이닀. (L~R의 λ²”μœ„λΌ λœ»ν•œλ‹€.)
    <!> 예) (0:0)λŠ” λΆ€ν˜Έ, (1:5)λŠ” λΆ€ν˜Έκ°€ μ—†λŠ” 숫자, (3:4)λŠ” 3,4번째 λ°”μ΄νŠΈ
  • Registers
    λ ˆμ§€μŠ€ν„°λŠ” μ•žμ— μ†Œλ¬Έμž r을 λΆ™μ—¬ ν‘œκΈ°
    A, X register
    Β± Byte Byte Byte Byte Byte
  • I register - rI1~rI6κΉŒμ§€ 있음.
    Β± Byte Byte
    J register
    + Byte Byte
    κ·Έ 외에
    Overfolw toggle - on, off
    Comparison indicator, - EQUAL, LESS, GREATER
    Input, Output Devices
  • Instruction format
    0 1 2 3 4 5
    Β± A A I F C
    C - λͺ…λ Ήμ–΄ μ½”λ“œ(the poeration code)
    F - λͺ…λ Ήμ–΄μ˜ λ³€κ²½(a modification of the operation code). (L:R)이라면 8L+R = F
    Β±AA - λ©”λͺ¨λ¦¬ μ£Όμ†Œ(the address)
    I - 인덱슀(the index specification). 값이 1~6으둜 rI1~rI6에 μžˆλŠ” λ‚΄μš©κ³Ό λ©”λͺ¨λ¦¬ μ£Όμ†ŒλΌ λ”ν•¨
    μ—¬κΈ°μ„œ 더해진 μ£Όμ†ŒλΌ M, M에 λ“€μ–΄μžˆλŠ” 값을 CONTETNS(M)이라고 ν•œλ‹€.
  • Notation
    ~cpp OP ADDRESS, I(F)
    같은 ν˜•μ‹μœΌλ‘œ μ“΄λ‹€.
    <!> ''예) LDAλŠ” λͺ…λ Ήμ–΄ μ½”λ“œκ°€ 8이닀.
    LDA 2000, 2(0:3) 은 || + || 2000 |||| 2 || 3 || 8 || κ³Ό κ°™λ‹€.''

2.1.2. μ—°μ‚°

  • Loading operators.
    CONTENTS(M)을 λ ˆμ§€μŠ€ν„°μ— λ„£λŠ”λ‹€.
    LDA, LDX, LDi, LDAN, LDXN, LDiN이 μžˆλ‹€.
  • Storing operators.
    λ ˆμ§€μŠ€ν„°μ˜ 값을 CONTENTS(M)에 λ„£λŠ”λ‹€.
    STA, STX, STi, STJ, STZκ°€ μžˆλ‹€.
  • Arithmetic operators.
    사칙연산을 ν•œλ‹€. ADD, SUB, MUL, DIVκ°€ μžˆλ‹€.
  • Address transfer operators.
    이 μ—°μ‚°μ—μ„œ M은 λ©”λͺ¨λ¦¬ 셀을 가리킀지 μ•Šκ³ , κ·Έλƒ₯ λΆ€ν˜ΈμžˆλŠ” 숫자둜 쓰인닀. ENTr, ENNr, INCr, DECrκ°€ μžˆλ‹€. ( r은 A, X, 1~6)
    <!> 예) ENTA 2000 - > rA || + || 0 || 0 || 0 || 2000 ||
  • Comparison operator
    λ ˆμ§€μŠ€ν„°μ™€ CONTENTS(M)을 λΉ„κ΅ν•΄μ„œ LESS, GREATER, EQUAL을 μ„μ •ν•˜λŠ” λͺ…령어이닀. CMPA, CMPX, CMPiκ°€ μžˆλ‹€. CMPiλΌ ν•  λ•ŒλŠ” μ•žμ— μ„Έ μžλ¦¬κ°€ 0이라고 κ°€μ •ν•œλ‹€.
  • Jump operators.
    M이 κ°€λ¦¬ν‚€λŠ” λ©”λͺ¨λ¦¬ μ…€λ‘œ μ ν”„ν•œλ‹€. JSJλΌ λΉΌλ©΄ μ ν”„λΌ ν•˜λ©΄μ„œ 점프 λͺ…λ Ήμ–΄ λ‹€μŒ μœ„μΉ˜λΌ rJ에 μ €μž₯ν•œλ‹€. the comparison indicatorλΌ μ΄μš©ν•˜κ±°λ‚˜(JL, JE, JG, JGE, JLE, JNE) , λ ˆμ§€μŠ€ν„°(JrN, JrZ, JrP, JrNN, JrNZ, JrNP)λΌ μ΄μš©ν•œλ‹€.
  • Miscellaneous operators.
    μ‹œν”„νŠΈ λͺ…령은 rA와 rXλΌ μ‚¬μš©ν•œλ‹€. SLA, SRA, SLAX, SRAX, SLC, SRCκ°€ μžˆλ‹€. M은 μ‹œν”„νŠΈν•˜λŠ” νšŸμˆ˜λΌ λ‚˜νƒ€λ‚Έλ‹€.
    MOVEλͺ…령은 F만큼 CONTENTS(M)을 rI1이 κ°€λ¦¬ν‚€λŠ” λ©”λͺ¨λ¦¬ μ…€λ‘œ 값을 λ³΅μ‚¬ν•œλ‹€.
    <!> ''예1) rI1 = 1001일 λ•Œ MOVE 1000,(3)
    CONTENTS(1000) -> CONTENTS(1001), rI1 = 1002
    CONTENTS(1001) -> CONTENTS(1002), rI1 = 1003
    CONTENTS(1002) -> CONTENTS(1003), rI1 = 1004''
    그럼 λ‹€μŒμ—” μ–΄λ–»κ²Œ λ˜λ‚˜?
    <!> 예2) rI1 = 2000일 λ•Œ MOVE 1000,(3)
    ''CONTENTS(1000) -> CONTENTS(2000), rI1 = 2001
    CONTENTS(1001) -> CONTENTS(2001), rI1 = 2002
    CONTENTS(1002) -> CONTENTS(2002), rI1 = 2003''
    (rI1값이 쀑간쀑간 λ°”λ€ŒλŠ”κ²Œ μ•„λ‹ˆλΌ λ‹€ λλ‚˜κ³  F만큼 더해진닀고 μƒκ°ν•˜λ©΄λΌ --μ„Έν™˜)
  • NOP λͺ…령은 아무것도 ν•˜μ§€ μ•ŠλŠ”λ‹€.
    HLT λͺ…령은 κΈ°κ³„λΌ λ©ˆμΆ˜λ‹€(The machine stops.)
  • Input-output opertors.
    ν•„μš”ν•  λ•Œ 보렀고 μƒλž΅ν–ˆλ‹€.
  • Conversion operators.
    NUM은 rAXλΌ κ°€μ§€κ³  숫자둜 λ°”κΎΈμ–΄ rA에 μ €μž₯ν•œλ‹€. 각 λ°”μ΄νŠΈκ°€ ν•œ 자리둜 λ°”λ€ŒλŠ”λ°, 일의 자리만 가지고 λ°”κΎΌλ‹€(10 -> 0, 23->3 )
    CHARλŠ” rAλΌ κ°€μ§€κ³  문자 μ½”λ“œλ‘œ λ°”κΎΈμ–΄ rAX에 μ €μž₯ν•œλ‹€.
  • Timing
    각 λͺ…λ Ήμ–΄λŠ” μ‹€ν–‰ μ‹œκ°„(excution time)이 μžˆλ‹€.

2.2. 1.3.3 Applications to Permutations

MIX ν”„λ‘œκ·Έλž¨μ˜ μ˜ˆμ œλΌ λ³΄μ—¬μ€λ‹€. μ€‘μš”ν•œ μˆœμ—΄μ˜ μ„±μ§ˆ(properties of permutations)을 μ†Œκ°œν•œλ‹€.

μˆœμ—΄μ€ abcdefλΌ μž¬λ°°μ—΄(rearrangement)μ΄λ‚˜ 이름바꾸기(renaming)λΌ ν•΄μ„œ μ–»λŠ”λ‹€κ³  λ³Ό 수 μžˆλ‹€. μ΄λΌ λ‹€μŒκ³Ό 같이 ν‘œμ‹œν•  수 μžˆλ‹€.(p.164μ°Έμ‘°)
( a b c d e f )
( c d f b e a )
μˆœν™˜ ν‘œμ‹œ(a cycle notation)둜 μ“°λ©΄ λ‹€μŒκ³Ό κ°™λ‹€
( a c f ) ( b d )
ν•΄μ„€ : aκ°€ c둜 λ°”λ€ŒλŠ” 것(a goes to c)을 a->c라고 ν‘œμ‹œν•œλ‹€. λ”°λΌμ„œ μœ„μ˜ ν‘œν˜„μ€ a->c->f->a, b->d->bλΌ λ‚˜νƒ€λ‚Έλ‹€.e->e같이 λ³€ν•˜μ§€ μ•ŠλŠ” 것은 μƒλž΅ν•œλ‹€.

2.2.1. Products of permutations

두 μˆœμ—΄μ„ κ³±ν•œλ‹€. (ν•©μ„±ν•¨μˆ˜μ™€ λΉ„μŠ·ν•˜λ‹€.)
(a b c d e f ) Γ— (a b c d e f )
(c d f b e a ) (b d c a f e )
= (a b c d e f )
(c a e d f b )
μ΄λΌ a cycle notation으둜 μ“°λ©΄
(a c f ) (b d )(a b d )(e f) = (a c e f b)
과정은 μ™Όμͺ½λΆ€ν„° μ‹œμž‘ν•΄μ„œ 였λ₯Έμͺ½μœΌλ‘œ κ°€λ©΄μ„œ μ°ΎλŠ” 방식이닀. aλΆ€ν„° μ‹œμž‘ν•˜λ©΄ a->c이고, cμ—μ„œ μ‹œμž‘ν•˜λ©΄ c->f->e이런 μ‹μœΌλ‘œ 찾을 수 μžˆλ‹€. 이 과정을 μ»΄ν“¨ν„°λ‘œ μ‹œλ„ν•΄λ³΄μž.

2.2.2. Algorithm A

A1. λͺ¨λ“  μ™Όμͺ½ κ΄„ν˜Έμ— 흔적을 남긴닀. 였λ₯Έμͺ½ κ΄„ν˜ΈλΌ μ™Όμͺ½ κ΄„ν˜Έ λ‹€μŒ 문자둜 λ°”κΎΈκ³  흔적을 남긴닀.
예) (a c f g) -> (a c f g a
A2. μ™Όμͺ½μ—μ„œ 였λ₯Έμͺ½μœΌλ‘œ κ°€λ©΄μ„œ 흔적이 μ—†λŠ” 첫번째 λ¬ΈμžλΌ START라고 ν•œλ‹€. μ™Όμͺ½ κ΄„ν˜Έμ™€ κ·Έ λ¬ΈμžλΌ μΆœλ ₯ν•˜κ³  흔적을 남긴닀. λͺ¨λ“  λ¬Έμžμ— 흔적이 남을 경우 μ’…λ£Œν•œλ‹€.
A3. λ‹€μŒλ¬ΈμžλΌ CURRENT둜 μ„ΈνŒ…ν•œλ‹€.
A4. 였λ₯Έμͺ½μœΌλ‘œ κ°€λ©΄μ„œ CURRENT와 같은 λ¬ΈμžλΌ μ°ΎλŠ”λ‹€. 찾은 경우 흔적을 남기고 A3둜 κ°„λ‹€. (λͺ» μ°Ύκ³  였λ₯Έμͺ½ λκΉŒμ§€ κ°€λ©΄ A5둜 κ°„λ‹€.)
A5. STARTβ‰  CURRENT이면 CURRENTλΌ μΆœλ ₯ν•˜κ³  식 μ™Όμͺ½λΆ€ν„° μ‹œμž‘ν•΄μ„œ A4둜 κ°„λ‹€.( κ°™μœΌλ©΄ A6둜 κ°„λ‹€.)
A6. (μ™„μ „ν•œ 사이클을 μ°Ύμ•˜μœΌλ€λ‘œ) 였λ₯Έμͺ½ κ΄„ν˜ΈλΌ λ‹«κ³  A2둜 κ°„λ‹€.
* Timing
잘 λͺ¨λ₯΄κ² λ‹€.

2.2.3. Another Approach(Algorithm B)

What is this computer-oriented method for permutation multipulication?
였λ₯Έμͺ½μ—μ„œ μ™Όμͺ½μœΌλ‘œ μ˜€λ©΄μ„œ 닡을 μ°ΎλŠ” 방법이닀.
(μ—¬κΈ°μ„œλŠ” 책에 μžˆλŠ” Table2(p.173)λΌ λ΄μ•Ό ν•œλ‹€. μ„Έλ‘œ ν•œ μ„이 TiλΌ λ‚˜νƒ€λ‚Έλ‹€. κ·Έ 밖에 i, j, Z 값을 적어 λ†“μœΌλ©΄ 이해할 수 μžˆλ‹€. n은 문자의 κ°œμˆ˜μ΄λ‹€.)
B1. λͺ¨λ“  1≀k≀n에 λŒ€ν•΄μ„œ Tk ← k. 였λ₯Έμͺ½λΆ€ν„° 읽을 μ€λΉ„λΌ ν•œλ‹€.
B2. 식을 였λ₯Έμͺ½λΆ€ν„° ν•˜λ‚˜μ”© μ½μœΌλ©΄μ„œ
) 이면 Z←0ν•˜κ³  B2반볡
( 이면 B4둜.
κ·Έ μ™Έμ—λŠ” i인 xiλΌ κ°€μ§€κ³  B3둜
B3. Z↔TiλΌ ν•˜κ³  λ‚˜μ„œ Ti = 0이면 j←iλΌ ν•œ λ’€ B2둜.
B4. Tj ← Z 후에 B2둜.
  • Timing
    μ—°μŠ΅λ¬Έμ œ10에 μžˆλ‹€.

2.2.4. Inverse

μˆœμ—΄ 연산을 μ›λž˜λŒ€λ‘œ λŒλ¦¬λŠ” μˆœμ—΄(μ—­ν–‰λ ¬κ³Ό λΉ„μŠ·ν•˜λ‹€.)
λ©”λͺ¨λ¦¬λΌ 많이 μ“°λ©΄ μ‰½κ²Œ ν•΄κ²°( Y[Xk ← k )
ν•˜μ§€λ§Œ 재λΈμ‚Όμ•„ nγ…£ 맀우 크고 λ‚¨λŠ” λ©”λͺ¨λ¦¬κ°€ μ—†λ‹€κ³  ν•΄λ³΄μž.

2.2.5. Algorithm I

(μ΄λ²ˆμ—λ„ Table 3(p.177)λΌ λ³΄λ©΄μ„œ ν•˜λ©΄ λœλ‹€.)

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:28:09
Processing time 0.0396 sec