cha2y0ung

오토마타(Automata) - 자동기계 장치라는 뜻 - 일반적으로 입력 장치, 출력 장치, 저장 장치, 제어 장치를 가지고 있음 오토마타의 특성 1) 오토마타는 입력 데이터를 읽을 수 있는 입력 기능을 가지고 있다 입력 데이터는 입력 파일에 쓰여져 있는 알파벳상의 스트링들로 이루어져 있는데, 입력 파일은 네모꼴의 셀(cell)들로 이루어져 있으며 각 셀에는 오직 하나의 심볼만 존재 2) 오토마타는 특정 형태의 출력 기능을 가지고 있다 0이나 1의 출력을 생성할 수 있으며 인식(accept) 또는 기각(reject)의 출력도 생성 3) 오토마타는 무한개의 셀들로 이루어진 임시 저장장치를 가질 수 있다 각 셀은 하나의 심볼만을 가질 수 있는데, 오토마타는 작동에 따라 셀들의 내용을 읽어내거나 변경할 수 있음..

알고리즘(algorithm) : 주어진 문제를 해결하기 위해 필요한 여러 가지 단계들을 체계적으로 명시해놓은 것 1) 입력(input) : 문제를 풀기 위한 입력이 있어야함 2) 출력(output) : 문제를 해결했을때 답이 나와야함 3) 유한성(finiteness) : 유한번의 명령이 수행된 후에는 끝나야함 4) 정확성(correctness) : 주어진 문제를 정확하게 해결해야함 5) 확정성(definiteness) : 각 단계가 실행된 후에는 결과가 확정됨 6) 일반성(generality) : 같은 유형의 문제에 모두 적용됨 7) 효율성(effectiveness) : 정확하면서도 효율적이어야함 유사코드(pseudo code) : 알고리즘을 프로그래밍 언어와 유사한 형태로 풀어써놓은 것 순서도(flow..

0과 1의 조합으로 연산되는 것을 부울 대수라고 함 1. 부울식 두 원소를 가지는 집합과 이항 연산자 그리고 단항 여난자로 표현되는 식을 말한다 1) 상수 0과 1 그리고 부울 변수는 부울식이다 2) 두 부울식이 같은 진리표(truth table)을 가질 경우 두 부울식을 동치(equivalent)라고 함 2. 부울식의 표현 부울 함수(Boolean function) : 부울 변수와 부울 연산자로 구성된 부울식으로 표현할 수 있음 n개의 부울 변수로 만들어지는 진리표에서 변수의 각 항을 최소항(Minterm)이라고 한다 n개의 변수가 있으면 2의 n제곱 개의 최소항이 있다 3. 부울 함수의 간소화 1) 부울식의 기본법칙 사용 2) 카노우맵 사용 카노우맵(Karnaugh map) : 부울 변수들에 대한 최..

1. 행렬(Matrix) 행렬은 m개의 행(row)과 n개의 열(column)을 가지고 있음 가로의 n 순서쌍을 행벡터(row vector), 세로의 m 순서쌍을 열벡터(column vector)라고도 부른다 행의 개수와 열의 개수가 같은 경우에 이를 정방행렬(square matrix)라고 한다 n개의 행과 n개의 열을 가지는 행렬을 n차 정방행렬(square matrix of order of n)이라고 한다 주대각선(main diagonal) 2. 행렬 연산 - 합과 차 3. 행렬 연산- 곱(multiplication) 행렬의 곱이 정의되기 위해서는 A의 열의 개수와 B의 행의 개수가 같아야한다 행렬에서 덧셉의 교환 법칙은 성립하지만 곱셈에서는 일반적으로 교환법칙이 성립하지 않는다 4. 행렬 연산 - ..

경우의 수 - 트리를 이용하는 방법과 표를 이용하는 방법 1) 합의 법칙(rule of sum) 2) 곱의 법칙(rule of product) 서로 다른 원소들을 순서를 고려하여 일렬로 배열하는 것을 순열(permutation)이라고 한다 서로 다른 n개의 원소 중에서 순서를 생각하지 않고 r개를 택할 때, 이것을 n개의 원소에서 r개를 택하는 조합(combination)이라고 한다 이항 정리(binomial theorem)과 이항 계수(binomial coefficient) -> 파스칼의 삼각형!! 파스칼의 삼각형 1) 각 행에 있는 첫 번째 숫자와 마지막 숫자는 1이다 2) 삼각형 안의 다른 숫자들은 파스칼의 삼각형과 같이 모두 그 숫자 위로부터 연결된 두 수들을 더함으로써 구해질 수 있다 확률이란 ..

트리 그래프 모양이 나무를 거꾸로 세워놓은 것처럼 생겼다 그래프의 특별한 형태로서 컴퓨터를 통한 자료 처리와 응용에 있어서 매우 중요한 역할을 담당 이진 트리의 경우 산술적 표현이나 자료 구조 등을 매우 간단하게 표현할 수 있는 장점 트리는 하나 이상의 노드(node)로 구성된 유한 집합으로서 다음의 2가지 조건을 만족한다 1) 특별히 지정된 노드인 루트(root)가 있다 2) 나머지 노드들은 다시 각각 트리이면서 연결되지 않는 서브 트리로 나누어진다. 트리의 응용 분야 - 최적화 문제의 해결 - 알고리즘(데이터구조, 정렬) - 분자구조식 설계와 화학결합의 표시, 유전학 - 언어들 간의 번역, 언어학 - 자료의 탐색, 정렬, 데이터베이스 구성 - 사회과학 등 트리의 용어 1) 루트(root) : 주어진 ..

1. 함수의 정의 관계의 특수한 형태로서, 첫번째 원소가 같지 않은 순서쌍들의 집합 한 집합의 원소가 다른 집합의 원소들 간의 관계를 나타내는 순서쌍 중에서 앞에 있는 집합의 모든 원소가 한번씩만 순서쌍에 포함될 경우를 말함 정의역/ 공변역/치역 같은 정의역과 공변역을 가지는 경우 두 함수는 서로 같다고 한다 2. 함수 그래프 2차함수 그래프..등등 3. 단사 함수, 전사함수, 전단사 함수 단사함수 : 일대일 함수 전사함수 : 공변역의 모든 원소가 정의역에 대응(=치역) 전단사함수 : 단사함수인 동시에 전사함수 -> 일대일 대응 함수 4. 여러가지 함수들 합성함수/항등함수/역함수/상수함수/특성함수/올림함수/내림함수

1. 관계와 이항 관계 관계 : 객체들 간의 연관성을 표현하는 구조. 집합에서의 원소들 간의 순서를 고려한 것 두개 이상인 원소에 대한 관계는 n-ary 관계라고 함 A와 B가 집합일때, 순서쌍의 첫번째 요소는 집합 A의 원소이고 두번째 요소는 B의 원소로 구성된 모든 순서쌍의 집합을 A와 B의 카티시안 곱 또는 곱집합이라고 한다 집합 A에서 B로의 관계 R에 대한 역관계는 집합 B에서 A로의 관계를 나타낸다 2. 관계의 표현 1) 서술식 방법 2) 나열식 방법 - 화살표 도표(Arrow Diagram) - 좌표 도표(Coordinate Diagram) - 방향그래프(Directed Graph) - 관계 행렬(Relation Matrix) 3. 합성 관계 합성 관계는 주어진 두 관계로부터 새로운 관계를 ..

1. 증명의 방법론 증명: 논리적 법칙을 이용하여 주어진 가정으로부터 결론을 유도해내는 추론의 한 방법 2. 여러가지 증명 방법 연역법 : 주어진 사실들과 공리들에 입각하여 추론을 통하여 새로운 사실을 도출 귀납법 : 관찰과 실험에 기반한 가설을 귀납 추론을 통하여 일반적인 규칙을 입증하는 것 수학적 귀납법 :n이 1일때 성립하는지 보이고 모든 양의 정수 n에 대해 성립한다고 가정하면 n+1의 경우에도 성립함을 보여주면 된다 모순 증명법 : 주어진 명제를 부정해 놓고 논리를 전개함. 그 결과 모순됨을 보임으로써 본래의 명제가 사실임을 증명하는 방법 직접 증명법 : 주어진 정보로부터 추론을 통하여 목적하는 결론에 도달할 수 있도록 유도하는 증명법 대우 증명법 : 대우 관계로서 논리적 동치가 됨을 이용하여 ..