컴퓨터과학[2-1]/knou_[2-1]이산수학23 이산수학 문제풀이 2015. 6. 20. 이산수학 기말시험 핵심노트 이산수학 기말시험 핵심노트 1.계수행렬:각방정식의 계수들을 순서대로 모아서 만든 행렬2.일차연립방정식의 확장행렬: 계수행렬 + 상수들을 순서대로 모아서 만든행렬3.단위행렬:대각원소가 1 이고 나머지 원소는 0인 행렬4.대각행렬:대각원소 이외의 원소가 0인 행렬(대각원소가 0이어도 되고 아니어도 됨)5.관계:화살표도표, 방향그래프, 부울행렬,순서쌍의 집합, 함수 아님6.방향그래프: A에서 A로 가는 그래프만 관계표현 가능7.전사함수:치역과 공역이 같다.8.합의정리: XY + ~XZ + YZ = XY + ~XZ 2015. 6. 17. 촘스키 계층구조Chomsky Hierarchy 촘스키 계층구조Chomsky Hierarchy ......... 언어는 그 언어를 생성하는 최대로 제한되는 문법의 정도에 따라 구분한다.이는 촘스키 계층 (Chomsky hierachy) 이라고 하는, 제한된 문법의 형태 (따라서 각 문법에 의하여 생성되는 언어도 제한됨) 를 정의하는 한 가지 방법이다 .............촘스키 계층 (Chomsky hierachy) 는 형식언어 (Formal Language) 를 생성하는 형식문법 (Formal Grammar) 들을 분류해 놓은 계층구조이다. 1956 년에 Noam Chomsky 가 처음 서술하였다. 그 계층구조는 다음과 같이 구분한다.Type-0 문법 (unrestricted grammars) 은 모든 형식문법을 포함한다. 튜링기계 (Turing .. 2015. 5. 21. 이산수학 - 오토마타[Automata]개념정리 이산수학 - 오토마타[Automata]개념정리 정의 오토마타는 이산시간 동안 주어진 입력에 의존해 문제를 푸는 [수학적 기계 :계산능력이 있는 추상기계(자동기계)]이다. 일반적으로 오토마타는 유한한 상태를 갖고, 입력을 받아 입력에 따라 일정하게 상태를 전이하며 출력을 내놓는다. 이는 알고리즘이 요구하는것, 즉 계산문제를 해결할 능력과 같다. 계산문제는 일반적으로 오토마타의 능력에 맞게 결정문제로 환산되며, 이 때 추상기계와 형식언어, 형식문법은 불가분의 관계가 된다. 따라서 오토마타는 언어와 문법과 같은 계층분류를 갖는다. 오토마타는 컴퓨터구조 설계와 컴파일러 설계, 파싱, 정형모델의 정형 검증등의 중요한 요소이다. 2015. 5. 19. Algorythms Big-O (or Big-oh) notation Big-O (or Big-oh) notation 계산 복잡도 이론에서 사용되는 점근 표기법. 입력 데이터의 크기와 알고리즘의 소요 시간 또는 메모리의 상관관계를 나타낸다. 1.1. 정의 모든 n(n은 어떤 n0보다 크거나 같다)에 대해 |f(n)|= 2015. 5. 12. Algorithms 알고리즘의 정의 알고리즘의 정의문제를 해결하기 위한 명령어들의 유한집합어떤 문제에 대해 입력 받아서 출력을 내기위해서 컴퓨터에 의해 샐행, 유한 번 수행후에 종료되는 명확 명령어들의 나열 알고리즘의 조건입력 (input)출력 (output)명확성 (definiteness)유한성 (finiteness)유효성 (effectiveness) 2015. 5. 3. 이전 1 2 3 4 다음
