1. 미크로네시아 연방 (Federated States of Micronesia) 의 국가 코드
2. 날아다니는 스파게티 괴물 (Flying Spaghetti Monster) 의 줄임말
3. 자유 언론 운동 (Free Speech Movement)
미국 UC 버클리에서 시작된 언론의 자유 운동. 베트남전 당시 언론과 speech에 대한 통제에 대한 반발로, Mario Savio의 주도로 이루어졌다. 현재 UC 버클리에서는 이 일을 기념하는 까페가 도서관 내에 있다.4. 유한 상태 기계 (Finite State Machine)
|
'''
이론 컴퓨터 과학 {{{#!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> 이론 | ||||
| 기본 대상 | 수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | #s-4 · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^ 고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축( 무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(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 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
컴퓨터의 수학적 모델의 일종이다. 컴퓨터 내에 유한한 상태(finite state)를 가지는 기계가 있다고 가정하고, 컴퓨터는 한 순간에 오로지 하나의 상태에만 있을 수 있으며 각 상태별 동작과 상태끼리의 전이에 대한 내용을 설계하게 된다. 요컨대, 순서도와 비슷한 것이며, 공대를 가게 되면 여러모로 써먹게 된다.
FSM의 상태(state) 수가 과도하게 많으면 메모리 요구량 및 설계 난이도를 높인다. 따라서 FSM의 상태 수를 최소화하고, 상태를 적절하게 할당해야 할 필요가 있다. FSM의 상태 수를 줄이는 방법으로는 implication chart 등이 있고, 상태를 효율적으로 할당하기 위한 방법으로는 one-hot 인코딩, Heuristic 알고리즘 등이 있다.
위의 내용들은 컴퓨터공학에 가까운 내용이고, 이것보다 좀 더 추상적인 오토마타 이론에서는 FSM을 명령어, 메모리 같이 기술에 종속된 개념 없이 순수하게 해석하는 편이다. 어차피 두 개념은 기술적으로 동형인데 좀 더 추상적인 설명을 원하면 오토마타 이론 쪽을 보도록 하자.
4.1. 분류
학문적으로 동작 방식에 따라 무어(Moore) FSM과 밀리(Mealy) FSM로 종류가 나뉜다. 밀리 FSM은 상태와 입력에 따라 출력이 결정되고, 무어 FSM은 상태에만 따라 출력이 결정된다.4.2. 예시: CPU
CPU도 일종의 FSM이다. 예를 들어서, MIPS로 설계된 멀티 사이클 CPU는 fetch(명령어 읽기), decode(명령어 해석), execute(명령어 실행), memory access(메모리 접근), writeback(쓰기)와 같이 5개의 상태로 구성된 FSM이라고 볼 수 있다. CPU의 상세한 동작 원리는 CPU/구조와 원리 문서를 참고하자.- fetch 상태: 메모리에서 명령어를 가져옴
- 다음 상태: decode 상태로 전이됨
- decode 상태: 명령어를 해석하고, 필요시 분기 처리를 위한 주소를 계산함
- 다음 상태: execute 상태로 전이됨
- . execute 상태: ALU를 사용하여 연산을 수행하거나 주소를 계산함
- 다음 상태: decode 상태에서 명령어 해석 결과에 따라서 수행할 연산과 전이될 상태가 달라짐
- R타입 명령어: ALU 연산 결과를 레지스터에 쓴 후 writeback 상태로 전이됨
- J타입 명령어: 점프 주소로 이동 후 fetch 상태로 돌아감
- LOAD 명령어: 메모리 주소 계산 후 memory access 상태로 전이됨
- memory access 상태: 명령어 해석 결과에 따라서 메모리에 데이터를 읽거나 씀
- 다음 상태: writeback 상태로 전이됨
- writeback 상태: 연산 결과나 데이터를 레지스터에 저장함
- 다음 상태: fetch 상태로 돌아감
실제로는 MIPS에 다양한 명령어가 존재하기 때문에 CPU의 자세한 설계는 더 복잡해진다. 하지만 기본적으로는 각 명령어를 처리하기 위해 필요한 상태를 정의하고, 레지스터의 쓰기 권한을 활성화할지, 메모리에 접근할지, 혹은 점프를 수행할지와 같은 동작을 상태값으로 표현하여 CPU를 마치 순서도처럼 구현한다. FSM은 순서도와는 다르게 시작(start)은 있어도 끝(end) 없지만.
5. 폴란드의 없어진 자동차 브랜드
|
{{{#!wiki style="margin: 0 -10px -5px;" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -6px -1px -11px" |
|
|
|
|
|||||||||
| CWS | FSO | PZInż | FSM | ||||||||||