컴퓨터과학, computer science, CS
Sub:
자료구조,data_structure
알고리듬,algorithm
복잡도,complexity
재귀,recursion
열거,enumeration
반복,iteration
귀납,induction - CS에선 넓은 의미의
철학,philosophy의 일반적 귀납 말고
수리논리,mathematical_logic에서의
수학적귀납법,mathematical_induction만을 뜻함?
람다대수,lambda_calculus
부동소수점,floating_point
고정소수점,fixed_point - p FixedPoint
memory_management 기억장치관리 메모리관리
메모리,memory MM
클래스와 객체
{
비유.
클래스 | blueprint: 청사진, 도면 |
객체 | structure: 건물, 실제 물건 |
}
클래스,class
{
비슷한
객체,object들의 특성을....
A class is the specification of a set of similar objects. (
from(http://blog.cleancoder.com/uncle-bob/2019/06/16/ObjectsAndDataStructures.html))
같은 영단어: 통계에서 class는
계급,class.
QQQ category와 차이?
}
객체,object
{
An object is a set of functions that operate upon encapsulated data elements. (
from(http://blog.cleancoder.com/uncle-bob/2019/06/16/ObjectsAndDataStructures.html))
의미는 매우 다양하다. PL에선 보통 data type의 instance?
Life and Scope of an Object
- life of an object : 객체가 (프로세스,process의) 메모리,memory에 있는지 여부를 결정. (determines whether the object is in memory (of the process))
- scope of an object : 객체에 접근할 수 있는 코드의 범위(section)를 결정. (determines the section of code where the object can be accessed)
객체가 live이지만 not visible한 경우는 가능. (메모리에 있으나 스코프 내에 없다? - 가능)
객체가 visible이지만 not live인 경우는 없음. (스코프 내에 있으나 메모리에 없다? - 불가능)
(최린)
(MKLINK
,scope)
PL API에선 가장 근본이 되는(abstract) 클래스 계층의 root에 위치하는 클래스의 이름으로 쓰이기도 함. ex. java.lang.Object
}
1.1. 계산가능성 computability ¶
1.2. 계산복잡도 computational complexity ¶
2. 컴퓨터 computer ¶
tmp
기계식 컴퓨터 mechanical computers
해석기관(Analytical_Engine)
by Charles_Babbage (not built)
이런것들이 가능한 이유는 아마
논리게이트,logic_gate가 전자부품만으로 구현가능한 게 아니니까. "논리 게이트는 주로 전자 회로의 스위치로 작동하는 다이오드 또는 트랜지스터를 사용하여 구현되지만 진공관, 전자기 릴레이 (릴레이 로직), 유체 논리, 공압 논리, 광학, 분자 또는 기계 요소와 같은 다양한 구성 성분을 사용하여 구현할 할 수 있다" (sic)
}
2.1. 컴퓨터구조 computer architecture ¶
CPU
pipeline
ALU
메모리,memory
memory hierarchy
virtual memory
DMA
storage
I/O, interrupt
data path
von Neumann vs Harvard
여러 기계들
QQQ 추상기계=오토마톤?
자동기계,automaton
{
자동기계, 오토마톤, 오토머튼, automaton, pl.
오토마타, 오토머터, automata
유한상태기계,finite-state_machine,FSM 또는 유한오토마톤,finite_automaton,FA
유한 상태 기계(finite-state machine, FSM) 또는 유한 오토마톤(finite automaton, FA)
유한_상태_기계
{
상태,state가
사건,event에 의해
전이,transition.
}
http://foldoc.org/Finite State Machine (FSM or "Finite State Automaton", "transducer")
결정적 유한 오토마타 (Deterministic Finite Automata, DFA)
A DFA
is a 5-tuple
: a finite set of states
: a finite set of input
symbols called the alphabet
: a transition function
: an initial state
: a set of accept states
- 상태들의 집합
- 입력의 집합
- 전이 함수
- 초기 상태
- 최종 상태
결정적_유한_상태_기계
Deterministic_finite_automaton
모든 NFA는 DFA로 변환 가능하다는 것이 증명되어 있다.
어원: 그리스어 αὐτόματος, 뜻 "self-acting, self-willed, self-moving"
}
유한상태기계 finite_state_machine,FSM
{
wpen에 의하면 state machine과 동의어라는데, infinite state machine은 없음? - c2 wiki에서 찾음. not practical.
AKA FSA: finite state automaton/automata
6. 문제 Problems ¶
k-clique problem - k-clique_problem - see
클릭,clique
충족가능성문제 satisfiability_problem 충족 가능성 문제 satisfiability problem SAT
충족_가능성_문제
6.1. 정지문제 halting problem ¶
6.2. 결정문제 decision problem ¶
9. History ¶
David Hilbert가 질문한 결정문제 혹은 수리명제자동판결문제(decision problem, Entscheidungsproblem)를 증명하기 위해
Alan_Turing이
튜링기계,Turing_machine AKA 튜링머신 를 고안함.