'''컴퓨터과학, 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
 [[garbage_collection]] 쓰레기수집 가비지컬렉션 GC
클래스와 객체
{
비유.
||클래스 ||blueprint: 청사진, 도면    ||
||객체   ||structure: 건물, 실제 물건 ||
}
[[클래스,class]]
{
비슷한 [[객체,object]]들의 특성을....
A class is the specification of a set of similar objects. ([http://blog.cleancoder.com/uncle-bob/2019/06/16/ObjectsAndDataStructures.html from])

같은 영단어: 통계에서 class는 [[계급,class]].
QQQ category와 차이?
}
[[객체,object]]
{
An object is a set of functions that operate upon encapsulated data elements. ([http://blog.cleancoder.com/uncle-bob/2019/06/16/ObjectsAndDataStructures.html from])
의미는 매우 다양하다. PL에선 보통 data type의 instance?

[[메모리,memory]] 상의 어떤 위치([[주소,address]])에 존재.

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]])

OOP 언어에선 ([[클래스,class]]와 대비되어) [[인스턴스,instance]] (+ 그 인스턴스에 대한 method) 의미로 쓰이기도. - CHK

PL API에선 가장 근본이 되는(abstract) 클래스 계층의 root에 위치하는 클래스의 이름으로 쓰이기도 함. ex. `java.lang.Object`

[[WpEn:Object_(computer_science)]]

QQQ [[인스턴스,instance]]와 비슷한데 뉘앙스 차이같은게? 정확히.

MKLINK
[[변수,variable]]
}
[[변수,variable]] - local에서도 writing
{
일단
[[변수,variable#s-5]]에 CS/CE/PL의 변수
[[변수,variable#s-6]]에 이론적 CS/logic의 변수

그리고 writing:
[[global_variable]]
[[local_variable]]
[[static_variable]]
[[static_local_variable]]
}
[[명세,specification]] - 사양,

[[인공지능,artificial_intelligence]]
[[컴파일러,compiler]]

[[컴퓨터그래픽스,computer_graphics,CG]]
{
Links

Introduction to Computer Graphics
온라인 교과서 (Version 1.2, 2018)
http://math.hws.edu/graphicsbook/index.html
https://news.ycombinator.com/item?id=24526845

A trip through the Graphics Pipeline (2011)
https://fgiesen.wordpress.com/2011/07/09/a-trip-through-the-graphics-pipeline-2011-index/
https://news.ycombinator.com/item?id=24649402
Part 1-13

Learn Computer Graphics From Scratch!
32 lessons, 166 chapters, 450,000 words, C++ source code
https://www.scratchapixel.com/

Ask HN: How to self-learn graphics programming?
https://news.ycombinator.com/item?id=26156783

}

[[메소드,method]]
 [[formal_method]] - writing ... WpEn:Formal_methods
[[형식,form]] ?
 [[formal_method]]

[[처리,processing]]
[[참조,reference]]
...

----
[[TableOfContents]]

= 계산 computation =
[[계산,computation]] - 작성중

== 계산가능성 computability ==
[[계산가능성,computability]] - 작성중

== 계산복잡도 computational complexity ==
curr [[복잡도,complexity]] ... 나중에 [[계산복잡도,computational_complexity]]? - 작성중

= 컴퓨터 computer =
[[컴퓨터,computer]]
{
NandGame – Build a Computer from Scratch
http://nandgame.com/
https://news.ycombinator.com/item?id=25282507
컴퓨터를 만드는 게임. [[불_대수,Boolean_algebra]] [[논리회로,logic_circuit]] [[논리게이트,logic_gate]]

tmp

What if you knew how computers work?
https://www.xorpd.net/
https://news.ycombinator.com/item?id=24736099
xchg rax, rax 책 저자?


기계식 컴퓨터 mechanical computers

A Do-It-Yourself Paper Digital Computer, 1959.
2-register, 1-bit
https://longstreet.typepad.com/thesciencebookstore/2010/11/a-do-it-yourself-paper-digital-computer-1959.html

https://en.wikipedia.org/wiki/Digi-Comp_I
3 [[플립플롭,flip-flop]]s

CARDIAC
https://www.cs.drexel.edu/~bls96/museum/cardiac.html

LOGIC
골판지+핫글루+구슬로 만든 컴퓨터
4-bit
https://lapinozz.github.io/learning/2016/11/19/calculator-with-caordboard-and-marbles.html

Mechanical Turing Machine in Wood
https://www.youtube.com/watch?v=vo8izCKHiF0

I Made A Water Computer And It Actually Works
https://www.youtube.com/watch?v=IxXaizglscw

해석기관(Analytical_Engine)
by Charles_Babbage (not built)

기타등등: [[WpEn:Category:Mechanical_computers]]

이런것들이 가능한 이유는 아마 [[논리게이트,logic_gate]]가 전자부품만으로 구현가능한 게 아니니까. "논리 게이트는 주로 전자 회로의 스위치로 작동하는 다이오드 또는 트랜지스터를 사용하여 구현되지만 진공관, 전자기 릴레이 (릴레이 로직), 유체 논리, 공압 논리, 광학, 분자 또는 기계 요소와 같은 다양한 구성 성분을 사용하여 구현할 할 수 있다" (sic)[* https://terms.naver.com/entry.naver?docId=5810601&cid=60217&categoryId=60217 물리학백과: 논리게이트]

[[Date(2021-12-28T19:36:04)]]
rod_logic 이라는 표현도 있음 - https://everything2.com/title/rod+logic
 기계식(컴퓨터)와 같은 뜻인지? chk.
WpEn:Molecular_logic_gate - 이 외에 각종 _computing들이 있는데 저기서 좀만 찾아보면 됨

[[Date(2022-03-11T19:59:38)]]
(당연하지만) [[자동기계,automaton]] cellular_automaton 로도 컴퓨터 구현 가능. rel. game_of_life or life_game
Let’s BUILD a COMPUTER in CONWAY's GAME of LIFE (다큐)
https://youtu.be/Kk2MH9O4pXY

}

== 컴퓨터구조 computer architecture ==
CPU
 pipeline
 ALU
[[메모리,memory]]
 memory hierarchy
 virtual memory
 DMA
storage
I/O, interrupt
data path
von Neumann vs Harvard

= 기계 =
'''''여러 기계들'''''

QQQ 추상기계=오토마톤?

[[추상기계,abstract_machine]]
{
http://foldoc.org/abstract+machine
[[WpKo:추상_기계]]
[[WpEn:Abstract_machine]] 
}

[[자동기계,automaton]]
{
'''자동기계, 오토마톤, 오토머튼[* wpko 자동기계 첫줄], automaton''', pl. '''오토마타, 오토머터[* wpko 자동기계 첫줄], automata'''

유한상태기계,finite-state_machine,FSM 또는 유한오토마톤,finite_automaton,FA
유한 상태 기계(finite-state machine, FSM) 또는 유한 오토마톤(finite automaton, FA)
WpKo:유한_상태_기계
{
[[상태,state]]가 [[사건,event]]에 의해 [[전이,transition]].
}
http://foldoc.org/Finite+State+Machine (FSM or "Finite State Automaton", "transducer")

그럼 [[상태기계,state_machine]]와 같은건지 아님 차이가 있는지 tbw
이것들 모두 [[추상기계,abstract_machine]]의 일종? chk

결정적 유한 오토마타 (Deterministic Finite Automata, DFA)
A DFA $M$ is a 5-tuple $(Q,\Sigma,\delta,q_0,F)$
 $Q$ : a finite set of states
 $\Sigma$ : a finite set of input [[기호,symbol|symbol]]s called the alphabet $\Sigma$
 $\delta$ : a transition function 
 $q_0$ : an initial state
 $F$ : a set of accept states $F\subseteq Q$
 * 상태들의 집합
 * 입력의 집합
 * 전이 함수
 * 초기 상태
 * 최종 상태
[[WpKo:결정적_유한_상태_기계]]
[[WpEn:Deterministic_finite_automaton]]


NFA: 
WpEn:Nondeterministic_finite_automaton
WpKo:비결정적_유한_상태_기계 (비결정적 유한 오토마타)

모든 NFA는 DFA로 변환 가능하다는 것이 증명되어 있다.

세포자동자? 세포적자동기계? [[cellular_automaton]], CA
http://www.aistudy.co.kr/biology/alife/cellular_automata.htm

어원: 그리스어 αὐτόματος, 뜻 "self-acting, self-willed, self-moving"[* wpen Automata_theory]

Twins:
[[WpKo:자동기계]] (← 오토마타)
[[WpKo:오토마타_이론]]
[[WpEn:Automata_theory]]
https://encyclopediaofmath.org/wiki/Automata,_theory_of

}
----
[[푸시다운자동기계,pushdown_automaton,PDA]]
{
[[스택,stack]]을 사용하는 [[자동기계,automaton]]의 한 종류.

[[WpKo:푸시다운_자동_기계]]
[[WpEn:Pushdown_automaton]]

https://esolangs.org/wiki/Push-down_automaton
}
----
[[신탁기계,oracle_machine]]
{
WpKo:신탁_기계
WpEn:Oracle_machine

계산가능성이론과 계산복잡도이론(see [[계산,computation]], [[계산가능성,computability]])에서 [[결정문제,decision_problem]]를 다루기 위해 쓰이는 [[추상기계,abstract_machine]].

oracle에 대해:
Semi-twin:
 https://mathworld.wolfram.com/Church-TuringThesis.html 의 중간 세번째문단 "If there were a device which could answer questions beyond..." 참조

}
----
[[튜링_기계,Turing_machine]]
{
MKLINK
[[상태기계,state_machine]]
[[자동기계,automaton]]

docs:
http://www.aistudy.co.kr/paper/pdf/turing_kim.pdf

[[WpKo:튜링_기계]]
[[WpEn:Turing_machine]]
http://www.aistudy.com/computer/turing_machine.htm
https://encyclopediaofmath.org/wiki/Turing_machine
http://foldoc.org/Turing+Machine

https://esolangs.org/wiki/Turing_machine
}
----
상태머신 [[상태기계,state_machine]] ?
[[Wiki:StateMachine]]

무한상태기계
{
[[Wiki:InfiniteStateMachine]]
}

유한상태기계 finite_state_machine,FSM
{
wpen에 의하면 state machine과 동의어라는데, infinite state machine은 없음? - c2 wiki에서 찾음. not practical.
AKA '''FSA: finite state automaton/automata'''

[[WpKo:유한_상태_기계]]
[[Wiki:FiniteStateMachine]]

https://esolangs.org/wiki/Finite-state_automaton
}

[[레지스터기계,register_machine]]
{
[[레지스터,register]]

https://mathworld.wolfram.com/RegisterMachine.html
[[WpEn:Register_machine]]
}

[[가상기계,virtual_machine]] - writing

= 이론 =
[[결정가능성,decidability]]
WpKo:결정가능성
{
[[정지문제,halting_problem]]의 '''결정불가능성'''이 Church와 Turing에 의해 증명됨.
}


[[펌핑보조정리,pumping_lemma]]
[[WpKo:펌핑_보조정리]]
{
[[형식언어,formal_language]]에 대해.
크게 두 가지:
 * [[정규언어,regular_language]]에 대한 것
 * [[문맥자유언어,context-free_language,CFL]]에 대한 것
}
[[WpEn:Pumping_lemma]] (for regular language, context-free language, etc.)

바쁜 비버 busy beaver
WpKo:바쁜_비버
[[https://namu.wiki/w/%EB%B0%94%EC%81%9C%20%EB%B9%84%EB%B2%84 namu]]
WpEn:Busy_beaver
https://googology.wikia.org/wiki/Busy_beaver_function


= 기반 이론 =
[[조합론,combinatorics]]
[[이산수학,discrete_math]]
[[자료,data]]
[[정보,information]]
[[정보이론,information_theory]]
[[그래프,graph]]
[[그래프이론,graph_theory]]
[[논리,logic]]
[[집합론,set_theory]]

maybe?
[[확률,probability]]
[[통계,statistics]]

책:
Ask HN: Resources to learn math as a foundation for CS
https://news.ycombinator.com/item?id=16505805

Related:
 [[정보보안,infosec]] '''information security'''

= 문제 Problems =
[[문제,problem]]

k-clique problem - k-clique_problem - see [[클릭,clique]]

충족가능성문제 satisfiability_problem 충족 가능성 문제 satisfiability problem SAT
[[WpKo:충족_가능성_문제]]

[[https://ratsgo.github.io/data%20structure&algorithm/2017/11/30/NP/ P, NP 문제 (1)]] (ratsgo)
[[https://ratsgo.github.io/data%20structure&algorithm/2017/12/01/NP/ P, NP 문제 (2)]] (ratsgo)
https://seungkwan.tistory.com/6 - [[결정문제,decision_problem]]부터 설명.

TBW
문제의 정의? [[해,solution]]/해결책/풀이법을 구하고자 하는 것의 대상?? ... Google:definition+of+problem
여기선 CS의 문제 얘긴데 [[수학,math]] 등등의 문제와의 차이점은??

== 정지문제 halting problem ==
[[정지문제,halting_problem]] AKA 중단문제, 멈춤문제

== 결정문제 decision problem ==
[[결정문제,decision_problem]] AKA 판정문제

= Misc =
[[정규식,regular_expression,regexp]]
{
점프 투 파이썬 / 07장 유용한 파이썬 도구들 / 07-2 정규 표현식 시작하기
https://wikidocs.net/4308

mklink
[[정규문법,regular_grammar]] 
[[정규언어,regular_language]]

tmp links ko
http://pl.skuniv.ac.kr/Lecture/Compiler/cdt-3/sld007.htm (page 7, 여기부터 10개의 slides. 여기선 '정규표현'으로 번역.)
 related: [[생성규칙,production_rule]].

AKA '''regexp, regex'''
Twins:
[[WpKo:정규_표현식]]
https://pub.mearie.org/정규표현식

Up: [[정규,regular]] [[식,expression]]
}

[[암달_법칙,Amdahl_law]]
{
'''Amdahl's law'''

Zebras Hate You For No Reason: Why Amdahl's Law is Misleading in a World of Cats (And Maybe in Ours Too)
https://www.embeddedrelated.com/showarticle/1033.php
Kittens Game에 비유하여 설명함

https://everything2.com/title/Amdahl%2527s+law
}

= Book =
Programming book list
https://danluu.com/programming-books/

공개 무료 en
Theory of Computation by Jim Hefferon is a text for a first undergraduate Computer Science theory course. It is Free.
https://hefferon.net/computation/index.html


= History =
David Hilbert가 질문한 결정문제 혹은 수리명제자동판결문제(decision problem, Entscheidungsproblem)를 증명하기 위해
Alan_Turing이
[[튜링기계,Turing_machine]] AKA 튜링머신 를 고안함.

같은 시기에 프린스턴대의 Alonzo_Church도 독립적으로 [[람다대수,lambda_calculus]](튜링머신과 equiv.) 연구.

처치-튜링 논제 Church-Turing thesis
 : 수학 [[함수,function]]를 이용해 어떤 값을 구하는 방법이 있다면, 그 방법을 튜링머신으로도 구현할 수 있다.

최초의 CS PhD는 [[WpEn:David_Wheeler_(computer_scientist)]](1951), 이 사람은 WpEn:Bjarne_Stroustrup 의 doctoral advisor.

----
Twins:
https://wiki.haskell.org/Computer_science
https://everything2.com/title/computer+science
[[Wiki:ComputerScience]]
http://biohackers.net/wiki/ComputerScience