전산학,compsci

컴퓨터과학, 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]from)

같은 영단어: 통계에서 class는 계급,class.
QQQ category와 차이?
}
객체,object
{
An object is a set of functions that operate upon encapsulated data elements. ([http]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


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

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




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


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

}





1. 계산 computation

계산,computation - 작성중

1.1. 계산가능성 computability

1.2. 계산복잡도 computational complexity

2. 컴퓨터 computer


tmp

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


기계식 컴퓨터 mechanical computers




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)


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

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

2022-03-12
(당연하지만) 자동기계,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

}

2.1. 컴퓨터구조 computer architecture

CPU
pipeline
ALU
메모리,memory
memory hierarchy
virtual memory
DMA
storage
I/O, interrupt
data path
von Neumann vs Harvard

3. 기계

여러 기계들

QQQ 추상기계=오토마톤?


자동기계,automaton
{
자동기계, 오토마톤, 오토머튼[2], automaton, pl. 오토마타, 오토머터[3], 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 symbols 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는 DFA로 변환 가능하다는 것이 증명되어 있다.


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


}





계산가능성이론과 계산복잡도이론(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..." 참조

}






무한상태기계
{
Wiki:InfiniteStateMachine
}

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






4. 이론

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


펌핑보조정리,pumping_lemma
WpKo:펌핑_보조정리
{
형식언어,formal_language에 대해.
크게 두 가지:
}
WpEn:Pumping_lemma (for regular language, context-free language, etc.)



6. 문제 Problems


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

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


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

6.1. 정지문제 halting problem

정지문제,halting_problem AKA 중단문제, 멈춤문제

6.2. 결정문제 decision problem

7. Misc

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


tmp links ko
http://pl.skuniv.ac.kr/Lecture/Compiler/cdt-3/sld007.htm (page 7, 여기부터 10개의 slides. 여기선 '정규표현'으로 번역.)
AKA regexp, regex
Twins:
WpKo:정규_표현식
https://pub.mearie.org/정규표현식


암달_법칙,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에 비유하여 설명함


8. Book


공개 무료 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


9. 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.


----