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)

Computer architecture (コンピュータ構成)

von Neumann, John (1903–1957). Hungarian‑American mathematician

shaped modern computing, physics, economics, etc.

defined the basic structure that almost all computers use today
⇒ one of the fathers of the modern computer

von Neumann architecture (ノイマン型コンピュータ)

the conceptual blueprint created by von Neumann

A computer stores programs and data in the same memory
A central processing unit (CPU) executes instructions one by one
The system includes input, output, memory, and processing as an integrated whole

Integrated circuit, IC (集積回路): a chip with electronic circuit‑building components integrated into it
Naming by integration scale (number of components)

Small scale integration, SSI　　　　　　　 < 100
Medium scale integration, MSI　　　　　 = 100-1000
Large scale integration, LSI　　　　　　　 > 1000
Very large scale integration, VLSI　　　 > 10000
Ultra large scale integrationm, ULSI　> 1000000

This classification has not been used since the 1990s because integrated circuits have grown far beyond the ULSI category

Recently used:

nanometer process: manufacturing scale or generation

how fine the fabrication is

technology node: official name of a manufacturing generation

which process generation it belongs to

transistor count; number of transistors on a chip

how complex or capable the chip is

Evolution of computer
ith Generation:
First(1940s–1950s): vacuum tube computers
Second (1950s–1960s): transistor computers
Third (1960s–1970s): integrated circuit (IC) computers
Fourth (1970s–present): microprocessor computers
Fifth (1980s–present): artificial intelligence and parallel processing

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
  1. a•b = b•a
  2. (ab)c = a(bc)
  3. a•1 = a
  4. aa = a
  1. aa' = 0
  2. a + a' = 1
  3. 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

Operation system, OS (オペレーションシステム)

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

フッター