Mathematics & Computing Logic

1. Overview

수학과 컴퓨팅 논리(Mathematics & Computing Logic, MCL)는 모든 계산 모델과 데이터 구조의 뿌리가 되는 수리적 표준을 정의합니다. 본 카테고리는 단순한 수학 공식을 넘어, 현실 세계의 복잡한 문제를 컴퓨터가 처리 가능한 형식적 언어(Formal Language)로 모델링하고, 알고리즘의 효율성과 시스템의 신뢰성을 연역적으로 증명하는 능력을 배양합니다.

CS2023의 Mathematical Foundations (MS) 지식 영역을 근간으로 삼아, 현대 소프트웨어의 중추인 이산 구조, 논리적 추론, 그리고 데이터 중심 아키텍처의 기반인 확률 및 정보 이론을 체계적으로 다룹니다.

2. Scope & Boundaries

In-Scope

• 이산 구조(Discrete Structures): 집합론, 관계, 그래프 이론, 조합론 등 컴퓨터가 다루는 유한/이산적 대상의 수리 모델링.
• 형식 논리(Logic & Proofs): 명제 및 술어 논리, 귀납법/모순 증명 등 시스템 무결성 검증을 위한 논리의 정석.
• 확률 및 통계(Probability & Stats): 불확실성 하에서의 알고리즘 효율성 분석, 대기열 이론, 베이지안 추론.
• 정보 이론(Information Theory): 엔트로피, 부호화, 전송 효율 극대화의 수리적 한계 연구.

Out-of-Scope

• 구체적 구현 코드: 알고리즘과 자료구조의 실제 프로그래밍 구현 (04. DS&A 노드로 위임).
• 고수준 엔지니어링 실무: 머신러닝 라이브러리 사용법이나 서비스 아키텍처 설계 (11. ML&AI 및 07. SADS로 위임).
• 순수 기하학/해석학: 컴퓨팅 논리와 직접적 연관이 적은 연속 수학 영역.

Boundaries

• MCL은 계산의 **'가능성(Correctness)'**과 **'한계(Capacity)'**를 수학적으로 규정하는 데 집중하며, 이를 실제 하드웨어/소프트웨어 자원으로 변환하는 작업은 인접 하위 도메인에서 수행합니다.

3. Counterexample

• 단순한 산술 연산 학습: 행렬 곱셈이나 미분 공식을 외우는 것은 MCL 학습이 아닙니다. 현실의 트래픽을 **포아송 분포(Poisson Distribution)**로 모델링하여 시스템 용량을 설계하는 것이 MCL의 역할입니다.
• 공리적 증명에만 매몰됨: 실질적인 시스템 제약 조건과 상관없는 순수 수학적 난제에 집중하는 것은 공학적 관점의 MCL에서는 지양해야 합니다.

4. Prerequisites

• CS&E Root (Basic): 전체 지식 체계 내에서 MCL이 갖는 기반 기술로서의 위치를 이해해야 합니다.
• 기초 논리학 (Recommended): 'If-Then' 조건문의 논리적 함의와 진리표 작성이 가능해야 합니다. (P1)
• 정보 모델링 사고 (Practical): 복잡한 상황을 변수와 관계로 추상화하는 능력이 요구됩니다.

5. Learning Map

1. Discrete Structures: 집합론과 관계를 통해 데이터의 논리적 연결과 기초 수리 모델을 구축합니다. (P1)
2. Logic & Verification: 명제와 증명 기법을 통해 시스템 무결성을 연역적으로 보장하는 법을 익힙니다. (P1)
3. Linear Geometry: 고차원 데이터의 기하학적 변환과 대수적 최적화 물리 파이프라인을 다룹니다. (Secondary)
4. Information Entropy: 확률 분포와 엔트로피를 통해 불확실성과 전송 효율의 물리적 한계를 정복합니다. (P1)

6. Learning Topics

Basic

Core Topic 01: 이산적 모델링 기초 (Discrete Modeling Foundations)

• Why to Learn: 디지털 시스템은 연속적인 수치 대신 명확히 구분되는 이산 상태를 처리하므로, 현실 문제를 컴퓨터 규격에 맞춰 추상화하기 위함입니다.
• What to Learn:
  • Concepts: 집합론 기초(Power Sets, Partitioning), 관계와 함수의 대수적 성질(Equivalence Relations, Partial Orderings), 부울 대수(Boolean Algebra).
  • Skills: 추상적 문제를 벤 다이어그램(Venn Diagrams)으로 시각화하기, 논리적 포함 관계 정의.
  • Tools: State Machine Diagrams, Logic Gate Basics.
  • Trade-offs: 상태 폭발(State Explosion) 문제와 상태 공간 압축 기법의 균형.
• How to Learn:
  • 1단계: 실생활의 네트워크 친구 관계를 그래프(Graph) 모델로 매핑해 봅니다.
  • 2단계: 유한 상태 기계(FSM)를 사용하여 특정 비즈니스 로직의 가능한 모든 상태를 정의합니다.
• Implement: 특정 로직의 상태 전이 설계도 및 관계 행렬(Adjacency Matrix).

Recommended

Core Topic 02: 형식적 시스템 증명 (Formal Proof Techniques)

• Why to Learn: 단위 테스트만으로는 증명할 수 없는 시스템의 '항상 올바름'을 수리적으로 수용하고 보장하기 위함입니다.
• What to Learn:
  • Concepts: 명제 논리(Propositional Logic), 술어 논리(Predicate Logic), 수학적 귀납법(Structural Induction), 순환 논증 방지.
  • Skills: 정렬 알고리즘의 루프 불변성(Loop Invariant) 증명, 호어 논리(Hoare Logic) 기초.
  • Tools: Coq, TLA+, Truth Tables.
  • Trade-offs: 증명의 엄밀함과 개발 속도 사이의 실무적 타협.
• How to Learn:
  • 1단계: 간단한 조건문 조합에 대한 논리적 무결성 분석 레포트를 작성합니다.
  • 2단계: 재귀 함수의 기저 사례(Base Case)와 유도 단계를 통해 정확성을 입증합니다.
• Implement: 알고리즘 무결성 증명 초안 또는 Formal Specification 문서.

Practical

Core Topic 03: 불확실성 하의 성능 모델링 (Probabilistic Performance Modeling)

• Why to Learn: 서버 지연이나 장애 발생과 같은 확률적 현상을 예측하고 가동률(SLA)을 과학적으로 산정하기 위함입니다.
• What to Learn:
  • Concepts: 베이지안 추론(Bayesian Inference), 포아송 분포(Poisson), 지수 분포(Exponential Distribution), 대기열 이론(Queueing Theory: Kendall's Notation).
  • Skills: 장애 로그 기반 다음 장애 발생 기대 시간(MTBF) 계산, 트래픽 폭주 확률 예측.
  • Tools: R, Python (SciPy/NumPy for stats modelling).
  • Trade-offs: 모델의 정확도와 계산 복잡도 간의 트레이드오프.
• How to Learn:
  • 1단계: 과거 트래픽 데이터를 바탕으로 특정 시간대 서버 부하를 확률 모델로 표현합니다.
  • 2단계: 몬테카를로 시뮬레이션을 통해 시스템 병목 지점을 수치화합니다.
• Implement: 트래픽 시뮬레이션을 통한 목표 가용성(SLA) 산정 계산기.

Advanced

Core Topic 04: 계산 가능성 및 정보 한계 (Computability & Information Limits)

• Why to Learn: 해결 불가능한 문제(Undecidable)를 식별하여 헛된 개발 비용 투입을 방지하고, 데이터 최적화의 수학적 임계치를 이해하기 위함입니다.
• What to Learn:
  • Concepts: 튜링 머신(Turing Machines), Halting Problem, P vs NP 문제의 본질, 정보 엔트로피(Shannon Entropy).
  • Skills: 문제 간의 리덕션(Reduction)을 통한 복잡도 등급 판별, 최적 압축률 계산.
  • Tools: Complexity Class Maps, ECC (Error Correction Code) models.
  • Trade-offs: 정보 밀도와 오류 복구 능력 간의 섀넌 한계(Shannon Limit).
• How to Learn:
  • 1단계: '모든 버그를 찾는 프로그램'이 이론적으로 왜 불가능한지 정지 문제를 통해 논증합니다.
  • 2단계: 데이터 저장소 설계 시 엔트로피 분석을 통해 압축 효율의 물리적 한계를 계산합니다.
• Implement: 특정 알고리즘의 한계 증명서 또는 복잡도 분석 논평.

7. Terminology

8. References

Primary References

• [P1] CS2023: MS — ACM/IEEE-CS Mathematical Foundations.
• [P4] DS-BoK: DI — Data Science Body of Knowledge: Data Interpretation.

Secondary References

• [MIT 6.042J] Mathematics for Computer Science — MIT OpenCourseWare.
• [Concrete Mathematics] Graham, Knuth, Patashnik — 전산학 수학의 정석.

Industry References

• [AWS Builders' Library] Reliability with Amazon Aurora — 데이터 정복 및 확률 모델 실제 사례.
• [Google SRE] Embracing Risk — 확률 기반 시스템 설계 실무.

9. Final Checklist

Primary Checklist

• 실세계를 집합과 관계로 모델링하여 시스템의 상태 공간을 정의할 수 있는가? (P1-MS-DS)
• 귀납법을 사용하여 특정 알고리즘이 모든 입력에 대해 올바름을 증명할 수 있는가? (P1-MS-LP)

Secondary Checklist

• Big-O 표기법의 수학적 엄밀함을 이해하고 복잡도 증명 프로세스를 수행했는가?
• 논리적 추론을 통해 코드 내부의 데드락(Deadlock) 가능성을 연역적으로 식별했는가?

Industry Checklist

• 베이지안 필터링 원리를 이해하고 이상 탐지(Anomaly Detection) 로직에 적용했는가?
• 정보 이론 기반의 엔트로피 분석을 통해 데이터 저장소 설계 시 압축 효율을 제안했는가?