[이산수학] 그래프

그래프 용어 정리  그래프는 꼭지점(vertex)과 변(edge)의 집합 G = (V, E)loop = 동일한 꼭지점을 연결하는 집합 동형 isomorphic: 꼭지점과 변의 이름을 제외하고 모두 동일한 그래프  방향 그래프 directed graph: 변이 뱡향을 가지고 있음무향 그래프 undirected graph: 변이 방향을 가지고 있지 않음 (꼭지점들 사이에 전후 관계가 없음)  단순 그래프 simple graph: 루프나 병렬 변을 가지지 않는 무향 그래프  부분 그래프 subgraph: H의 모든 꼭지점이 G의 꼭지점이고, H의 모든 변이 G의 변인 경우 H는 G의 부분 그래프V' ⊆ V, E' ⊆ E 신장 부분 그래프 spanning subgraph: 부분 그래프 중 H와 G의 꼭지점이 완..

• format_list_bulleted TIL/CS
• · 2024. 5. 17.
• textsms

[이산수학] 부울대수

부울대수: 부울값(0, 1) 또는 부울변수에 대한 논리연산을 다루는 수학부울함수: 부울식으로 표현된 함수  부울함수에 대한 진리표는 하나하나의 진리표를 만족하는 부울함수는 여러 개 => 가장 단순화된 논리회로도 구현하는 것이 중요   부울대수의 기본 정리 1. X + 0 = X2. X * 1 = X3. X + 1 = 14. X * 0 = 05. X + X = X6. X * X = X7. X + X' = 18. X * X' = 09. X'' = X 10. X + Y = Y + X 교환법칙11. XY = YX  교환법칙 12. X + (Y + Z) = (X + Y) + Z   결합법칙 13. X(YZ) = (XY)Z   결합법칙 14. X(Y + Z) = XY + XZ  분배법칙 15. X + YZ = (X..

• format_list_bulleted TIL/CS
• · 2024. 5. 16.
• textsms

[이산수학] 행렬(Matrix)

행렬 기본  행렬에 관한 연구 시작: 더 쉽고 체계적으로 선형방정식 문제 해결 위해행렬 사용: 자료구조에서는 행렬을 2차원 배열로 구현해 자료 저장, 머신러닝에서는 데이터의 특성을 행렬로 표현 행렬: 수 또는 문자를 네모꼴로 배열한 것m개의 행과 n개의 열로 이루어진 행렬은 m x n 행렬 i 번째 행의 j 번째 열의 수는 (i, j) 원소  영행렬(zero matrix) = 모든 원소가 0인 행렬    행렬의 연산 행렬의 합A + B : 크기가 같은 두 행렬에서 같은 위치의 원소값을 더함 행렬의 차A - B : 크기가 같은 두 행렬에서 같은 위치의 원소값을 뺌 행렬의 스칼라 곱kA : A의 각 원소에 k를 곱한다  행렬의 합과 스칼라 곱의 연산법칙교환법칙: A + B = B + A결합법칙: A + (B..

• format_list_bulleted TIL/CS
• · 2024. 4. 27.
• textsms

[이산수학] 증명

증명: 새로운 수학적 진술이 참임을 입증하는 데 필요한 논증. 특정 공리들을 가정하고 그 가정 하에 제안된 명제가 참임을 입증한다.공리: 다른 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정. 별도의 증명 없이 참으로 이용된다정리: 공리들을 바탕으로 논리적으로 증명된 결론  직접증명법 (연역)명제 변형 없이 공리와 정의, 이미 증명된 정리를 논리적으로 직접 연결해 증명 수학적 귀납법모든 자연수 n에 대해 명제 성립 증명하는 데 유용함기본단계 > 귀납가정 > 귀납단계 간접증명법명제를 증명하기 쉬운 형태로 변형대우증명법모순증명법p → ~q를 가정하면 모순임을 증명반례증명법구성적 존재증명법P(x)를 참으로 만드는 x를 주어진 정의역에서 찾는다비구성적 존재증명법직접적으로 x를 찾지 않고 우회적인 방법..

• format_list_bulleted TIL/CS
• · 2024. 4. 1.
• textsms

[운영체제] 프로세스, 쓰레드

프로세스 프로세스: 실행에 들어간 프로그램 (자원을 할당받아 동작 시작) (ex. 작업 관리자에서 프로세스들 볼 수 있음) 프로세스의 동작: CPU가 그 프로세스들의 명령 실행 운영체제는 프로세스들이 CPU 배정받아 작업을 처리할 수 있도록 관리 프로세스는 "동작" 한다는 것이 가장 중요한 개념 프로세스의 구성 메모리 구조: 프로그램 실행에 직접적으로 필요한 코드, 데이터 코드 영역 저장장치에 들어 있는 프로그램 자체 실행이 되어야 하니까 어셈블리 형태의 코드들이 들어 있을 것임 데이터 영역 상수, 변수의 값 등 실행에 필요한 데이터 코드 중에서 서브프로그램 호출 관련 내용이 있다면 들어 있음 정적 데이터 영역 상수, 항상 관리되어야 하는 변수 등 스택 영역 서브 프로그램, 그 안의 지역 변수 등 힙 영..

• format_list_bulleted TIL/CS
• · 2024. 3. 26.
• textsms

[이산수학] 논리

명제와 논리연산 명제 proposition: 참과 거짓을 구별할 수 있는 문장이나 수학적 식 합성명제 compound proposition: 하나 이상의 명제와 논리연산자들이 결합되어 만들어진 명제 논리연산: 참, 거짓을 구별할 수 있는 명제를 대상으로 하는 연산 논리합(or, ∨) disjunction 하나라도 T가 있으면 T 논리곱(and, ∧) conjunction 하나라도 F가 있으면 F 부정(not, ~) negation T → F, F → T 배타적 논리합(xor, ⊕) exclusive disjunction 2개 중 1개만 T인 경우 T (T, T 거나 F, F면 F) p ⊕ q = (p ∧ ~q) ∨ (~p ∧ q) or인데 and를 포함하지 않은 경우 (두개가 동일한 경우를 배제) 두개가..

• format_list_bulleted TIL/CS
• · 2024. 3. 22.
• textsms