[이산수학] 오토마타 / 형식 언어 / 문법

컴퓨터 수학적 모델 오토마타와 형식 언어, 문법에 대해 알아보자 오토마타, 형식 언어, 문법에 관한 연구는 매우 추상적임 컴파일러, 문서 편집기, 엘리베이터 등 다양한 분야에 응용이 됨 오토마타란? 오토마타 디지털 컴퓨터의 수학적 모델인 **‘오토마톤’**의 복수형으로 **‘자동기계 장치’**라는 뜻 일반적으로 입력, 출력, 저장, 제어 장치를 가지는 컴퓨터의 이론적 메커니즘 단순한 오토마타로는 고대 이집트의 모래시계부터 현대의 뻐꾸기 시계도 포함 실생활에서 만나는 오타마타 이론적인 자판기 오토마타 50원과 100원짜리 동전을 투입가능하고 투입한 돈이 300원이나 그 이상일때 커피나 음료수를 내주고 거스름돈을 돌려주지 않는 가정 → 투입 액수에 따라 상태가 변화 동전 투입 시 액수가 변화해야하며 300원..

• format_list_bulleted Computer Science/Discrete Mathematics
• · 2023. 8. 27.
• textsms

[이산수학] 알고리즘을 통한 문제 해결

알고리즘을 통해 여러 문제를 해결하는 방법을 알아보고 해당 문제들이 실생활에 적용되는 방법을 알아보기 알고리즘? 알고리즘 알고리즘이란 특정한 일을 수행하는 명령어들의 유한 집합 수학에서는 문제를 풀기 위해 정의나 정리를 활용 = 컴퓨터에서는 수행 가능한 효율적인 알고리즘 사용 주어진 문제를 해결하기 위해 필요한 여러 가지 단계들을 체계적으로 명시해 놓은 것 → ‘어떤 문제를 해결하는 한 방법의 상세한 특징을 기술하는 것’ 알고리즘의 7가지 주요 특성 입력 : 문제를 풀기 위한 입력 출력 : 문제를 해결했을 때 답이 나와야함 유한성 : 유한 번의 명령이 수행된 이후에는 끝이 나야함 정확성 : 주어진 문제를 정확하게 해결해야 함 확정성 : 각 단계가 실행된 후에는 결과가 확정됨 일반성 : 같은 유형의 문제에..

• format_list_bulleted Computer Science/Discrete Mathematics
• · 2023. 8. 22.
• textsms

[이산수학] 부울 대수

부울식의 기본 연산과 부울식의 법칙 및 표현 방법을 설명하고 부울 대수에 관련된 전반적인 논제를 확인 부울식 부울 대수 영국의 수학자 부울이 수학적 논리 형태로 소개 → 샤넌이 부울 대수의 기본 개념을 이용하여 회로 함수에 대한 설계로 발전 전기 장치나 컴퓨터 회로는 켜짐과 꺼짐의 두 가지 상태로 나타냄 스위치나 회로는 닫힘과 열림의 두 가지 상태 중 하나인 참 또는 거짓, 1 또는 0으로 표현 0과 1의 조합으로 연산되는 것을 부울 대수 부울식 부울 식은 두 원소를 가지는 집합 A = {0,1}와 이항 연산자 OR, AND /단항 연산자 NOT으로 표현되는 식 ‘ (NOT) > · (AND) > + (OR) 의 연산 우선 순위를 가짐 부울식의 법칙 p,q,r을 부울 변수라고 할 때 멱등 법칙 p · p..

• format_list_bulleted Computer Science/Discrete Mathematics
• · 2023. 8. 21.
• textsms

[이산수학] 행렬과 행렬식

행렬과 행렬식의 개념을 정의하고 그와 관련된 전반적인 논제에 대해 학습합니다 행렬과 행렬의 연산 선형방정식의 풀이는 여러 가지 공학적인 문제들의 해결에 매우 중요 행렬은 선형방정식을 간단하게 표현할 수 있으며, 보다 쉽게 연산이 가능하도록 해줌 행렬식은 행렬을 통한 응용에 있어서 매우 유용한 도구를 제공해줌 행렬 행렬은 수 또는 문자를 배열의 형태로 나타내는 것 행렬은 m개의 행과 n개의 열을 가지고 있음 i와 j를 통해 행과 열을 표시하여 해당 행렬의 값을 찾아갈 수 있음 #1 행렬의 크기 m x n의 행렬과 같이 m, n으로 행렬의 크기를 나타냄 #2 행벡터, 열벡터 각 행은 가로의 n 순서쌍 → 행벡터 각 열은 세로의 m 순서상 → 열벡터 #3 정방행렬 행과 열의 개수가 같은 경우 → 정방행렬 n개..

• format_list_bulleted Computer Science/Discrete Mathematics
• · 2023. 8. 15.
• textsms

[이산수학] 순열, 이산적 확률, 재귀적 관계

순열, 이산적 확률, 재귀적 관계에 연관된 전반적인 논제들을 고찰하고 그에 따른 문제 해결 방법을 습득할 수 있음 경우의 수 어떤 사건이 일어나는 경우의 수를 구하기 위해 모든 경우를 일정한 기준에 따라 빠짐없이, 중복되지 않게 해야함 경우의 수를 구하는 방법에는 구하는 방법에는 트리를 이용한 방법과 표를 구하는 방법이 있음 #1 합의 법칙 두 사건 A, B가 일어날 경우의 수를 n(A) = m, n(B)=n이라 하면 , A 또는 B가 일어날 경우의 수는 m+n #2 곱의 법칙 두 사건 A, B가 일어날 경우의 수를 n(A) = m, n(B)=n이라 하면, A,B가 동시에 일어날 경우의 수는 m*n 순열 서로 다른 원소들을 순서를 고려하여 일렬로 배열하는 것 1부터 n까지의 모든 자연수의 곱을 n의 계승..

• format_list_bulleted Computer Science/Discrete Mathematics
• · 2023. 8. 14.
• textsms

[이산수학] 트리

트리의 개념을 익히고 트리의 응용 방법을 고찰한다 트리의 기본 개념 트리 그래프의 모양이 나무를 거꾸로 세워 놓은 것처럼 생겼다하여 불리는 이름 그래프의 특별한 형태로 컴퓨터를 통한 자료 처리와 응용에 있어 매우 중요한 역할 이진 트리는 산술적 표현이나 자료 구조를 매우 간단히 표현 가능 → 컴퓨터 기술의 발전에 따라 수 많은 분야에 적용 가능 트리는 하나 이상의 노드로 구성된 유한 집합으로 특별히 지정된 루트가 있으며 나머지 노드 들은 다시 각각 트리이며 연결되지 않는 서브 트리로 나뉜다 트리의 응용 분야 최적화 문제 해결, 언어들 간의 번역, 알고리즘, 자료 탐색/정렬, 등 트리의 구조 루트 : 주어진 그래프의 시작 노드로서 통상 트리의 가장 높은 곳에 위치 차수 : 어떤 노드의 차수는 그 노드의 서..

• format_list_bulleted Computer Science/Discrete Mathematics
• · 2023. 8. 13.
• textsms