| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
Checksum.한자어로는 검사합(檢査合)이라고 한다. 번호 등에 오류가 존재하는 바의 여부를 확인하기 위해 추가로 끼워넣는 번호로 대개 0~9 중 하나다.
2. 상세
보통 바코드, 주민등록번호에 사용된다.경우에 따라 IBAN처럼 두 자리 이상의 숫자를 사용하기도 한다.
간혹 순환 중복 검사(CRC)와 체크섬을 혼용하여 쓰는 사람이 있다. 그러나 이 둘은 엄연히 다른 개념. 체크섬이 단순한 합산이나 XOR(보수연산, ~)으로 이루어지나 CRC는 나눗셈을 통해 얻어지기 때문이다.
간단하게 둘의 차이점으로는 자원사용량과 무결성이다. 체크섬은 연산에 큰 자원이 들어가지않아 빠른 속도를 제공함과 동시에 자원사용량을 낮출 수 있지만 문제는 다중 비트 오류나 순서가 변경(Bit flip) 되는 경우에 취약하다는 점.
반대로 CRC는 일반적으로 이진 다항식 나눗셈을 기반으로 하기 때문에 자원사용량이 높다. 대신 그 만큼 무결성에서는 매우 신뢰할만하다.
컴퓨터 사양이 좋아진 최근에서는 사실상 성능이 상향평준화되어 목적에 따라 알맞게 사용하면 된다.
그냥 (전기가 아닌) 활력 충전, UEFI BIOS 같은 용어 혼용일 뿐이다. 해시섬이라고도 한다. 단, 실제 해시를 체크섬 용도로 써서 해시섬이라고 할 경우에는 기술적으로도 정확한 용어 사용이 된다.
과거에는 컴퓨터 프로그래밍 관련 개념으로 알려져있었는데, 1980년대까지 게임이나 유틸리티 등 프로그램을 배포 및 공유하는 방법은 컴퓨터 잡지의 몇 페이지에 걸쳐 깨알 같이 적혀있는 16진수 기계어를 보면서 직접 입력하는 것이었다. 하늘이 노랗게 보일 정도의 엄청난 작업이지만 당시엔 별다른 방법이 없었기에 주로 시험이 끝난 학생들이 1~2일 간 숙식을 같이하며 번갈아 입력을 하곤 했는데 순간의 오타가 모든걸 날려먹는 도미노 준비와 비슷한 작업에 가까웠기에 중반부터는 각 라인 끝단에 체크섬 코드를 추가해 기계어 리스트를 전수 검사할 필요가 없이 체크섬만 간편하게 확인하는 방식으로 진화되었다. 물론 운이 아주 나쁜 경우 같은 라인에 2군데 이상 오류가 있고 그 오류의 합이 서로를 절묘하게 보합해 체크섬만 보면 오류가 없는 것처럼 나오기도 한다.
2.1. 주민등록번호에서의 활용
물론 체크섬은 10개 중 하나니 찍어도 10%의 확률로 맞출 수는 있다. 단, 이 체크섬을 통해 주민등록번호가 악용되거나 하는 사고를 어느정도 방지할 수 있다.그런데 문제는 간혹 공무원의 실수로 체크섬이 잘못 부여되는 일이 존재한다는 거다. 물론 모든 시스템이 전산으로 처리되는 지금은 발생할 수 없는 일이지만 이런 일을 수기로 하던 시절엔 자주 있던 일이다.