|
수와
연산 Numbers and Operations |
|||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" |
<colbgcolor=#765432> 수 체계 | 자연수 ( 수학적 귀납법 · 홀수 · 짝수 · 소수 · 합성수) · 정수 · 유리수 ( 정수가 아닌 유리수) · 실수 ( 무리수 · 초월수) · 복소수 ( 허수) · 사원수 | |
| 표현 | 숫자 ( 아라비아 숫자 · 로마 숫자 · 그리스 숫자) · 기수법( 자연어 수 표기법 · 과학적 표기법 · E 표기법 · 커누스 윗화살표 표기법 · 콘웨이 연쇄 화살표 표기법 · BEAF · 버드 표기법) · 진법 ( 십진법 · 이진법 · 8진법 · 12진법 · 16진법 · 60진법) · 분수 ( 분모 · 분자 · 기약분수 · 번분수 · 연분수 · 통분 · 약분) · 소수 { 유한소수 · 무한소수 ( 순환소수 · 비순환소수)} · 환원 불능 · 미지수 · 변수 · 상수 | ||
| 연산 | 사칙연산 ( 덧셈 · 뺄셈 · 곱셈 구구단 · 나눗셈) · 역수 · 절댓값 · 제곱근 ( 이중근호) · 거듭제곱 · 로그 ( 상용로그 · 자연로그 · 이진로그) · 검산 · 연산자 · 교환자 | ||
| 방식 | 암산 · 세로셈법 · 주판 · 산가지 · 네이피어 계산봉 · 계산기 · 계산자 | ||
| 용어 | 이항연산( 표기법) · 항등원과 역원 · 교환법칙 · 결합법칙 · 분배법칙 | ||
| 기타 | 수에 관련된 사항 ( 0과 1 사이의 수 · 음수 · 작은 수 · 큰 수) · 혼합 계산 ( 48÷2(9+3) · 111+1×2=224 · 2+2×2) · 0으로 나누기( 바퀴 이론) · 0의 0제곱 | }}}}}}}}} | |
|
'''
이론 컴퓨터 과학 {{{#!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. 개요
이항연산을 표현하는 방법으로, 연산자와 피연산자의 위치를 어떻게 적는지를 다룬다.2. 명칭
전위/후위 표기법은, 수식 표기법과 관련된 폴란드의 학자 Jan Łukasiewicz(얀 우카시에비치)의 이름/지역/국가 명을 붙여 부르기도 한다. 그 가운데는 (역) 폴란드 표기법을 가장 많이 쓴다.전위 표기법: Łukasiewicz / Warsaw / Polish notation
후위 표기법: reverse Łukasiewicz / Warsaw / Polish notation
3. 종류
간단한 예제| 방법 | 표기 |
| 전위 | +12 |
| 중위 | 1+2 |
| 후위 | 12+ |
3.1. 전위 표기법
prefix notation, Polish notation(PN)연산자를 피연산자 앞에 배치하는 방법이다.
영어권에서는 후위 표기법보다 사용하기에 편하다. 왜냐하면 영어에서 수식을 읽을 때 전위 표기법의 순서와 같은 순서로 읽기 때문이다.[1] 예를 들어 3+4는 'Add 3 and 4'라고 읽으므로 전위 표기법의 순서와 같다.[A] 따라서 후위 표기법보다 읽기 쉽고 중위 표기법보다 프로그램 구현이 간단하므로, LISP, 엑셀등의 일부 언어는 전위 방식을 사용한다.
3.2. 중위 표기법
infix notation연산자를 피연산자 사이에 배치하는 방법이다.
일반인들은 모두 이 방법으로 계산을 배우고 사용한다. 특정 분야의 사람들이 아니라면 중위 표기법만 배운다.
다른 표기법들과 다르게 연산의 우선순위[3]를 정해야 하고, 뺄셈이나 나눗셈 같은 비가환 연산(non-commutative operation)도 신경써야 한다. #
3.3. 후위 표기법
postfix notation, reverse Polish notation(RPN)연산자를 피연산자 뒤에 배치하는 방법이다.
한국어에서 사람이 수식을 읽는 순서와 같은 방식이다. 예를 들어 (3+4)×2는 '3과 4를 더한 것에 2를 곱한다.'로 읽힌다.[A]
스택을 사용하며 괄호가 필요없기 때문에 수식의 표현이 간단해지는 장점이 있다.
예를 들어 (4 + 5) / (2 - 1)은 역폴란드 표기법으로 4 5 + 2 1 - /로 표기하며 계산 순서는 다음과 같다.
- 4와 5를 스택에 넣는다.
- 스텍에서 값 2개를 빼서 덧셈을 계산하고 결과를 스택에 넣는다.
- 2와 1을 스택에 넣는다.
- 스텍에서 값 2개를 빼서 뺄셈을 계산하고 결과를 스택에 넣는다.
- 스텍에서 값 2개를 빼서 나눗셈을 계산하고 결과를 스택에 넣는다.
장점은 프로그램의 구현이 간단해지기 때문에 초기의 프로그래밍 언어[5]에서 많이 쓰였다. 하지만 복잡한 수식을 표현하는데 어려움이 있으며 계산 순서가 틀릴 경우 어디가 잘못됐는지 알아차리기 힘들다. 수기로 작성하기에 불편하단 단점도 있다.
4. 표기법 변환
원래 표기법에 해당하는 '연산자 1개와 피연산자 2개' 단위로 괄호를 계속 친 다음, 순서대로 바꾸려는 새 표기법으로 변환한다. 괄호가 필요없어지면 지우면 끝이다.예시
- 중위표기법 1+2×3 을 후위표기법으로 바꿀 때, 1+(2×3) → 1+(23×) → 1(23×)+ → 123×+
- 중위표기법 1+2×3 을 전위표기법으로 바꿀 때, 1+(2×3) → 1+(×23) → +1(×23) → +1×23
5. 관련 문서
[1]
VO어순을 갖는 다른 언어에서도 마찬가지다.
[A]
물론 중위 표기법으로 읽을 수도 있다. 수식을 중위 표기법으로 읽을 수 없는 인간 언어는 존재하지 않는다.
[3]
괄호 >
하이퍼 연산 >
거듭제곱,
제곱근,
로그,
삼각식,
계승 >
곱셈,
나눗셈 >
덧셈,
뺄셈 > (
함수)
[A]
[5]
유닉스 계열 운영체제에 기본적으로 깔려있는
dc(desk calculator)라는 계산기 프로그램이 이 표기법을 사용하는데, 이는 심지어
C 언어보다도 오래된 프로그램이다.
Java를 컴파일하면 나오는 흔히
바이트코드라 일컬어지는 Java Instructions Set도 이에 해당한다.