전산학,compsci

컴퓨터과학, computer science


Sub:
자료구조,data_structure
알고리즘,algorithm
복잡도,complexity
재귀,recursion
부동소수점,floating_point
고정소수점,fixed_point
클래스,class
{
비슷한 객체,object들의 특성을....
A class is the specification of a set of similar objects. ([http]from)
}
객체,object
{
An object is a set of functions that operate upon encapsulated data elements. ([http]from)
}
명세,specification - 사양,




2. Problems

k-clique problem - see 클릭,clique

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

3. Misc

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

4. History

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

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

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

중단문제,정지문제,halting_problem
'튜링 기계와 입력이 주어져 있을 때 튜링 기계가 이 입력에 대해 유한시간 내에 계산을 끝내고 멈출 것인가 아니면 영원히 멈추지 않을 것인가'를 판별하는 문제
결론부터 말하면, 어떤 알고리즘,algorithm도 프로그램의 중단 여부를 판단할 수 없음. 결정불가능성,undecidability 문제임. (계산 불가능 혹은 결정 불가능)