http://www.ebs.co.kr/HOMEPAGE/?progcd=0001327
EBS 오디오북 : 유료
라디오 문학관 : 무료
한국단편 50선
세계단편 50선
우리소설 100선
베니스 상인 같은 경우 20분짜리 3편임.
대략 분량은 초등학교 6학년 수준이 읽는 책 정도 됨.
1시간만에 세세한 것까지 소화할 수 없으므로.
참고로 고우영 삼국지가 mp3로 20분짜리가 몇백회였던 것 같다.
TV나 책을 읽기는 쉽지 않을 때, 가볍게 들으면 좋겠다.
. Foundations : partial, total functions
. Undefined operation(Error termination)
ex) division by zero
. 3/0 has no value - mathematically undefined
. imprementation may halt with error condition
. Evalutino of the expression cannot proceed because of a conflict between operator and operand.
. Nontermination - 무한루프, divergenece 등
. f(x) = if x = 0 then 1 else f(x -2)
. This is a partial function : not defined on all arguments
. cannot be detected at compile-time; This is halting problem
. proceeds indefinitely
. These two cases are
. Mathematically equivalent
. Operationally different
. Partial and total functions
. Total function : f(x) has a value for every x
. Partial functino : g(x) does not have a value for every x
. 우리가 푸는 것은 recursive partial function이므로 못 푸는 문제가 존재한다.
. Functions and graphs
. mathematics : afunctions is a set of ordered pairs(graph of function)
. Partial and total functions
. total function f: A->B is a subset f in AxB with
. For every x in A, there is some y in B with (x,y) in f (total)
. If (x,y) in f and (x, z) in f then y = z (single-valued)
. partial function f: A->B is a subset f in AxB with
. If (x,y) in f and (x, z) in f then y = z (single-valued)
. programs define partial functions for two reasons
. partial operations (like division) - 바로 termination가능
. nontermination
f(x) = if x = 0 then 1 else f(x-2)
. Halting problem
. Computable
. Partial recursive functinos(recursion을 허용하는 partial function)
. = Lambda calculus
. = Turing machine
. symbol manipulating devices
. Tape, head, state register, action table(transition function)으로 구성
. Halting problem(A noncomputable function)
. Given a program P that requres exactly one string input and
a string x, determine whether P halts on input x.
(Say yes or no)
. Undecidable - dkanfl aksgdms tlrksdmf wnjeh dkf tn djqtek.
. Computability
. Definition
Function f is computable if some program P coumputes it:
For any input x, the computation P(x) halts with output f(x)
. Terminology
. Partial recursive functions
= Partial functions (int to int) that are computable
. Halting function
. Decide whether program halts on input
. Given program P and input x to P
. Halt(P, x) = yes if P(x) halts, no otherwise
. Clarifications
. Assume program P requires one string input x
Write P9x) for output of P when run in input x
Program P is string input to Halt
. Fact : There is no program for Halt.
. Unsolvability of the halting problem
. Suppose P solves variant of halting problem
. On input Q, assume, P(Q) = yes if Q(Q) halts, no otherwise
. Build program D - P로 D를 만들자
. D(Q) = run forever if Q(Q) halts, if Q(Q) runs forever
. Does this make sense? What can D(D) do?
. If D(D) halts, then D(D) runs forever.
. IF D(D) runs forever, then D(D) halts
. Contradiction : program P must not exist
. Main points about computability
. Some functions are computable, some are not
. Halting problem
. Programming langage implementation
. Can report error if program result is undefined due to division by zero, other undefined basic operation
. Cannot report error if program will not terminate
. RE(Regular expression) < CFG(Context Free Grammar)
< TM (Turing Machine) != not computable
. RE = DFA, NFA, e-DFA
. RE + stack = Push-down automata = CFG
. CFG + Tape = TM = Computable
. Diversion
. C : Kills the people once saved
. C++ : The empire strikes back
. Java - Don't drink don't smoke - what do you do?
. C++이 복잡해서 필요한 것만 넣음.
strong typed, 그런데 결국은 다시 복잡해짐.
. Perl : Feel free to substitute your favorite error prone language
. scripting language
. Automating simple computer tasks
. Connecting diverse pre-existing components to accomplish a new related task
. Rapid development
윈도우 미디어 플레이어(Window media player)에서
스트리밍(streaming)이 재생되지 않을 때.
시작 -> 프로그램 -> 윈도우 미디어 플레이어
-> 도구 -> 옵션 -> 네트워크 -> 스트리밍 프로토콜
-> 멀티캐스트, UDP, TCP, HTTP 모두 check
. scoping
. 여러 scope에 같은 variable name이 출현할 때, 어디에 binding 할지 정하는 것
. static scoping
. = lexical scoping
. a variable always refers to its nearest enclosing binding
. unrelated to the runtime call stack
. compile time에 binding을 결정
ex)
int x = 0;
int f () { return x; }
int g () { int x = 1; return f(); }
g()는 0을 retrun 함
. dynamic scoping
. control flow를 따라 global x stack에 값을 push, pop함.
. run time에 binding을 결정
ex)
int x = 0;
int f () { return x; }
int g () { int x = 1; return f(); }
g()는 1을 retrun 함
. idempotence
. http://en.wikipedia.org/wiki/Idempotent
. binary operation일때, 자기 자신을 연산하면 자신이 나옴.
ex) binary number system의 multiplication
. unary operation일때, 자기 자신에게 두번 연산을 apply하면 한번 연산했을 때와 같은 결과가 나옴.
ex) min, max
. fixed point
http://en.wikipedia.org/wiki/Fixed_point
f(x) = x
idempotence의 조건과 비슷함.
. attractive fixed point
http://en.wikipedia.org/wiki/Fixed_point_%28mathematics%29
어떤 x를 넣든 x를 f에 n번 apply하면 x0에 가까워짐.
f(f(f(x))) ... = x0
. Attractor
http://en.wikipedia.org/wiki/Attractor
. Invariant
. does not change under a set of transformations.
. Abstract algebra - ring, group
. set, group, ring, field를 정의하고
마지막에 5차 이상 대수방정식의 일반해가 없다는 것을 증명
. rings(환)
http://en.wikipedia.org/wiki/Ring_%28mathematics%29
. 합에 대해 가환군이 되고
. 곱에서는 결합법칙이 성립하고
. 합, 곱 사이에는 분배법칙이 성립할 때
. commutative ring(가환환)
. 교환법칙이 성립하는 ring
. groups(군)
http://en.wikipedia.org/wiki/Group_%28mathematics%29
http://100.naver.com/100.nhn?docid=23289
곰셈에 대하여
. 결합법칙
. 단위원
. commutative group = abelian group(가환군, 아벨군)
. 교환법칙이 성립하는 group
. fileds
http://en.wikipedia.org/wiki/Field_%28mathematics%29
. homomorphism
. pi : X->Y
. pi(u*v) = pi(u)+pi(v)
. * : operation on X
. + : operation on Y
. Morphism
. two mathematical structure간의 structure-preseving process.
. set theory에서는 functions
. group theory에서는 group homomorphisms
. topology에서는 continuous functions
. universal algebra에서는 homomorphisms
. category theory에서는 domain와 codomain의 relationship
. identity morphism이 있어서 그것과 composite해도 자기 자신이 나온다.
. associativity가 있어야 한다.
x*(y*z) = (x*y)*z
. one-to-one(injective)
일대일
x의 모든 원소가 y에 대응됨.
. onto(surjective)
y의 모든 원소가 x에 대응됨.
. bijective : injective and surjective
일대일대응
. monomorphism
. f*g1 = f*g2이면 g1 = g2 일 때, f는 monomorphism이다.
. f : X->Y
. g1, g2 : Z->X
. f*g1, f*g2 : Z->Y
. injective homomorphism
. split monomorphism
. left-inverse를 가지는 monomorphism
. epimorphism
. http://en.wikipedia.org/wiki/Epimorphism
. g1*f = g2*f이면 g1 = g2 일 때, f는 epimorphism이다.
. f : X->Y
. g1, g2 : Y->Z
. g1*f, g2*f : X->Z
. right-cancellable
. surjective homomorphism
. monomorphism와 dual 관계
. bimorphism
. epimorphism and monomorphism
. isomorphism
. bijective homomorphism
. morphism : f : X->Y 일때
f*g = idY and g*f = idx인 g:Y->X가 존재한다.
. morphism has both left-inverse and right-inverse, then
left-inverse and right-inverse are equal.
. http://en.wikipedia.org/wiki/Isomorphic
. bijective(one-to-one and onto) map, f and f^-1이 homomorphism하다.
. 두 structure가 isomorphic하면 structurally identical하다고 할 수 있다.
. 한 structure에서 theorem이 증명되었으면
새로운 structure와 isomorphism이라는 것만 증명하면
그것들을 그대로 옮겨와서 사용할 수 있다.
. 모든 isomorphism은 bimorphism이다. (역은 아님)
. endomorphism
. http://en.wikipedia.org/wiki/Endomorphism
. f:X -> X인 f를 endomorphism of X라고 함.
. automorphism
. http://en.wikipedia.org/wiki/Automorphism
. endomorphism and isomorphism
. closure : 2개의 endomorphism의 composite는 또 다른 endomorphism이 됨.
. associativity : morphism은 정의상 항상 associative하다.
. identity : morphism은 정의상 항상 identity를 가진다.
. inverses : 정의상 inverses를 가진다.
. antihomomorphism
. http://en.wikipedia.org/wiki/Antiautomorphism
. pi : X->Y
. pi(xy) = pi(y)pi(x)
. 곱셈의 순서를 reverse함.
. diffeomorphism
. f:M->N이 bijective map이고
f:M->N, f^-1:N->M 이 모두 dirrentiable할 때
. Polymorphism
. http://en.wikipedia.org/wiki/Polymorphism_%28computer_science%29
. single definision이 different types of data에 사용될 수 있을 때
. ML에서 사용됨.
. holomorphism
. http://en.wikipedia.org/wiki/Holomorphism
. open subset of the complex number plane C 정의된 모든 값이
differentiable할 때.
. U : open subsete of C
. f : U -> C, complex diffentiable at z0
. f'(z0) = lim z->z0, (f(z)-f(z0))/(z-z0)
. isometry
. isometric isomorphism
. congruence mapping
. disstance-preserving isomorphism
. f : X->Y
. X, Y be metric space with dx, dy
. dy(f(x), f(y)) = dx(x, y)
. global isometry
. bijective distance preserving map
. path isometry
. arcwise isometry
. preserve the lengths of curves
. idempotence
. http://en.wikipedia.org/wiki/Idempotent
. binary operation일때, 자기 자신을 연산하면 자신이 나옴.
ex) binary number system의 multiplication
. unary operation일때, 자기 자신에게 두번 연산을 apply하면 한번 연산했을 때와 같은 결과가 나옴.
ex) min, max
