Top
ヘッダー

(Upload on Apirl 13 2016) [ 日本語 | English ]

Computer science (計算機科学)






Mount Usu / Sarobetsu post-mined peatland
From left: Crater basin in 1986 and 2006. Cottongrass / Daylily

Principle of optimality (最適性原理)
= Bellman equation, discovered by Richard Bellman (1953)
= dynamic programming equation
Bellman, Richard Ernest (1920–1984)

Theoretical computer science

Computational complexity theory (計算複雑性理論)
Classifying computational problems according to their resource usage and their related problems

⇒ algorithm

P versus NP problem (P問題とNP問題)
= one of the seven Millennium Prize Problems (unsolved problem in computer science)
Def. P or class P: the general class of questions that some algorithm can answer in polynomial time
索引
P problem (polynomial)

an algorithm that can be solved in polynomial time is present
Ex. The Seven Bridges of Königsberg

NP problem (non-deterministic polynomial)

that can determine whether a solution is correct or not in polynomial time when a solution is given in advance, although no algorithm has been found that solves the problem efficiently in polynomial time
NP-completeness (NP完全)

Prediction: P ≠ NP (P is not NP)

Boolean algebra (ブール代数)

Boole George (1815-1864, England)

differential equations and algebraic logic
Boolean algebra, introduced in the Laws of Thought (1854)

Boolean algebra

Axiom
  1. a + b = b + a
  2. (a + b) + c = a + (b + c)
  3. a + 0 = a
  4. a + a = a
  5. a•b = b•a
  6. (ab)c = a(bc)
  7. a•1 = a
  8. aa = a
  9. aa' = 0
  10. a + a' = 1
  11. a(b + c) = ab + ac
Prove:
1' = 0 → 1' = 1'•1 = 1•1' = 0
a + 1 = 1 → a + 1 = a + (a + a') = (a + a) + a' = a + a' = 1
a•0 = 0•a = 0 → a•0 = 0•a, a•0 = a(aa') = (aa)a' = aa' = 0
a + ab = a → a + ab = a•1 + ab = a(1 + b) = a•1 = a
a(a + b) = a → a(a + b) = aa + ab = a + ab = a
a(a + b + c) = a → aa + ab + ac = (aa + ab) + ac = a + ac = a
a + bc = (a + b)(a + c) →

a + bc = a(a + b + c) + bc = a(a + b) + ac + bc = a(a + b) + c(a + b) //

Q Solve simultaneous equation a + x = 1, ax = 0
A (x = a') is a root because of axiomatic system (a + a' =1)

set x0 as a root
x0 = x0•1 = x0(a + a') = x0a + x0a' = 0 + x0a'
= aa' + x0a' = (a + x0)a' = 1•a' = a'
only a' is the root //

Law. De Morgan's law (1)
→ (ab)' = a' + b'
Pr. (a' + b') + ab = (a' + b' + a)(a' + b' + b) = (b' + 1)(a' + 1) = 1•1 = 1

while (a' + b')ab = a'ab + b'ab = 0•b + 0•a = 0 + 0 = 0
(x = (ab)') is the only root that msut satisfy (x + ab = 0) and (xab = 0)
∴ (ab)' = a' + b //

Law. de Morgan's law (2)
→ (a + b)' = a'b'
Pr. (a + b)' = [(a')' + (b')']' = [(a'b')']' = a'b' //
Table. Case that Boolean algebra that has only specific factors (0, 1) 
    +  0  1    •  0  1    '
    -------    -------    ----
    0  0  1    0  0  0    0  1
    1  1  1    1  0  1    1  0
Table. Set {a, b} → subset φ, U = {a, b}, {a}, {b}
0 = π, 1 = U, 2 = {a}, 3 = {b}
    +  0  1  2  3    •  0  1  2  3    '
    -------------    -------------    ----
    0  0  1  2  3    0  0  0  0  0    0  1
    1  1  1  1  1    1  0  1  2  3    1  0
    2  2  1  2  1    2  0  2  2  0    2  3
    3  3  1  1  3    3  0  3  0  3    3  2

UNIX (Unix)

1969 Thompson K: developing the OS for mini-computer PDP-7 (DEC)

= beginning of UNIX
greatly-simplified functions
system files distributed by ASCII format - can be modified by users
→ causes of developing various UNIX local languages

Ex. ATT System V, UCB BSD, IBM AIX

1973 Richie D: unix kernel re-written by C language
1991.10.5 Linus T (Finland): opned Linux

distributed freely, independent of unix-OS system → becoming popular

EWS (engineering workstation)

Past:
high-spec computer for business use (the most of OS are UNIX)
→ system (computer) = EWS (hardware) + UNIX (OS) + Application software

office computer = EWS ↔ personal computer (PC)

Present:
≈ general-purpose computer (PC), because of upgrading PC

BSD, Barkeley Software Distribution

one of the UNIX OSs, developed by Univercity of Carfornia, Berkeley
functions of C Shell, vi, termcap, virtual memory, TCP/IP network

characterzied by high-spec job control
adopted by standard UNIX (= SVR4, UNIX System V Release 4)

COSE, Common Open Software Environment

projects and standards of six computer items, including desktop and network environments, drawn up common API proposed by UNIX vendors

R

フッター