컴퓨터 과학을 위한 수학 (2018) [PDF]

• MIT에서 제공하는 컴퓨터 과학 전공자를 위한 수학 교재로, 논리와 증명부터 확률, 재귀, 그래프 이론까지 핵심 수학 개념을 체계적으로 다룸
• 증명, 구조, 카운팅, 확률, 점화식의 다섯 파트로 구성되어 있으며, 각 파트는 이론적 기초와 컴퓨터 과학 응용을 함께 다룸
• 논리식, 수학적 귀납법, 상태 기계, 그래프, 확률 변수 등 프로그래밍과 알고리듬 분석에 필수적인 주제를 포함
• RSA 암호화, Turing의 코드, Monty Hall 문제 등 실제 사례와 응용 문제를 통해 수학 개념의 활용을 보여줌
• MIT와 Google 연구진이 공동 집필한 교재로, Creative Commons BY-SA 3.0 라이선스로 공개되어 학습과 재사용이 자유로움

---

교재 개요

• Mathematics for Computer Science (MCS) 는 MIT의 컴퓨터 과학 및 전기공학 학부 과목(6.042) 교재로, 논리적 사고와 수학적 모델링 능력을 기르기 위한 자료
• 저자는 Eric Lehman (Google Inc.) , F. Thomson Leighton (MIT, Akamai Technologies) , Albert R. Meyer (MIT)
• 2018년 6월 6일 개정판으로, Creative Commons Attribution-ShareAlike 3.0 라이선스 하에 배포

I. Proofs (증명)

• 명제, 술어, 공리적 방법, 귀류법, 경우 나누기 증명 등 수학적 증명의 기본 원리를 다룸
• Well Ordering Principle(정렬 원리) 과 귀납법의 관계를 설명하고, 소인수분해와 같은 예시를 통해 적용
• 논리식과 명제 논리, SAT 문제, 수학적 데이터 타입(집합, 함수, 관계) 등을 포함

II. Structures (구조)

• 정수론, 그래프 이론, 네트워크 구조를 중심으로 컴퓨터 과학의 수학적 기반을 제시
  • 소수, 최대공약수, 모듈러 산술, RSA 암호화 등 수 이론 응용
  • 방향 그래프, 부분 순서, 네트워크 라우팅, 단순 그래프, 평면 그래프 등 구조적 모델 설명
• Turing의 코드와 SAT 문제의 연관성을 다루며, 계산 이론과 암호학의 연결을 보여줌

III. Counting (계산 및 조합)

• 합, 곱, 점근적 표기법, 조합 규칙, 생성함수 등 조합론적 계산 기법을 다룸
• 비둘기집 원리, 포함-배제 원리, 포커 손 패 예제 등 실전적 예시 포함
• 생성함수와 선형 점화식 해법을 통해 알고리듬 분석과 수열 계산에 응용

IV. Probability (확률)

• 확률 공간, 조건부 확률, 확률 변수, 분산, 표본 추정, 랜덤 워크 등 확률 이론의 전 범위를 포괄
• Monty Hall 문제, Simpson의 역설, 생일 문제 등 직관적 사고를 시험하는 사례 포함
• Markov, Chebyshev 정리와 무작위 샘플링을 통한 데이터 분석 기초 제공

V. Recurrences (점화식)

• 하노이의 탑, 병합 정렬, 분할정복 점화식 등 알고리듬 분석의 핵심 주제 다룸
• 선형 점화식 해법과 재귀적 사고 방식을 통해 효율적 계산 구조를 설명

부록

• 참고문헌, 기호 해설, 색인을 포함하여 학습 및 참고에 용이
• 전체 교재는 MIT CSAIL 웹사이트에서 PDF 형태로 무료 제공

[GN⁺]

Hacker News 의견들

• Thomson Leighton이 Akamai의 창립자임을 언급하며, 그가 진행한 강의 시리즈를 추천함
  인터넷 관련 강의 중 가장 인상 깊게 본 콘텐츠였음

  • 추가 자료로 MIT OCW의 최신 강의 영상과, 교재 저자 중 한 명인 Albert Meyer가 진행한 Open Learning Library 강의를 함께 소개함
  • Akamai가 스캐너나 스크립트 키디들이 사용하는 IPv4 대역 문제에 더 신경 써줬으면 좋겠다는 의견을 덧붙임

• 각 섹션의 구성은 꽤 표준적이지만, 인용마다 모든 출처로의 역참조가 달려 있는 점이 마음에 듦
  이런 식으로 만든 책이 더 많았으면 좋겠음

  • 내용 선택이 오히려 비표준적이라 흥미로웠고, MIT 특유의 유머가 녹아 있음
    다만 2018년 이후로 집필이 중단된 점이 아쉬움

• 이 책을 정말 좋아함. 난이도는 높지만 각 단락에서 1~2페이지 정도는 이해할 수 있었음
  함수가 입력과 출력의 끝없는 리스트라는 통찰을 얻었고, 수학적 표기 속 유머도 인상 깊었음
  죽기 전에 완전히 이해하고 싶음

  • “단락마다 1~2페이지 이해한다”는 표현이 빅토르 위고식 장문을 떠올리게 해 웃겼음
  • “1~2페이지”라니, 농담으로는 “-1페이지”쯤 된다고 함

• 컴퓨터 과학에서 꼭 읽어야 할 책 5권만 꼽을 수 있냐는 질문을 던짐

  • 단 5권으로는 불가능하다고 하며, 자신만의 Top 10 리스트를 공유함
    Brookshear, Forta, Stallings, CLRS, Kurose & Ross, Sipser, Aumasson, Russell & Norvig 등을 포함함
    Python이 사실상 공용어가 되었고, Matthes의 Python Crash Course 3rd Edition도 추천함
  • 컴퓨터공학 전공이 아니라면 TeachYourselfCS.com을 추천함
    시간이 부족할 때 읽을 핵심 2권도 안내되어 있음
  • 어떤 분야를 하느냐에 따라 달라진다고 함. “어떤 언어를 배워야 하나?”와 비슷한 질문임
  • 이 책은 수보다 관계에 초점을 덜 둔 것 같다고 하며, type theory나 category theory도 함께 공부하길 권함
  • 모두가 동의할 만한 리스트는 없다고 함. 스스로 탐색하며 알고리즘, 오토마타, 언어, 운영체제, 머신러닝 등 각자에게 맞는 책을 찾는 게 중요함

• 이 책의 확률 파트가 특히 좋았음
  Monty Hall 문제를 ‘4단계 방법’으로 명쾌하게 설명해 영화보다 훨씬 이해하기 쉬웠음

  • 2017년판이 영국에서 주문형 인쇄로 구할 수 있음을 발견함
    종이책으로 부분적으로 공부하기에 좋음

• 목차를 보니 2장이 Well-Ordering Principle이라 놀랐음
  Zermelo의 정리와 달리, 자연수의 순서를 전제로 두는 방식이 낯설었음
  보통은 Peano 공리로부터 순서를 정의하고 그 후에 원리를 증명하는 식으로 배웠기 때문임

  • Well-Ordering Principle, Axiom of Choice, Zorn’s Lemma가 서로 동등하다는 점을 설명함
    실수에도 잘 정렬이 존재하지만, 그 순서를 실제로 표현할 수 없다는 점이 흥미로움
    “선택 공리는 자명히 참, 정렬 원리는 자명히 거짓, Zorn의 보조정리는 모르겠다”는 농담도 인용함
  • CS 교육에서는 주로 수학적 귀납법의 기초로만 다루며, 이후 알고리즘 수업에서는 거의 언급되지 않음

• 15.8장의 비둘기집 원리를 Dijkstra의 접근으로 다시 설명함
  보스턴의 50만 명이 머리카락을 1~20만 개 가지고 있다면, 평균이 2.5명이므로 최소 3명이 같은 머리카락 수를 가짐을 증명함
  평균이 최대값 이하라는 단순한 사실로 해결되는 점이 흥미로움

• 문제집 형태의 책을 처음 접했는데, 해답이 있는지 궁금하다고 함
  몇 문제를 풀어봤지만 정답을 확인할 수 없었음

  • Math Academy의 Discrete Math 과정은 답안을 제출하면 풀이를 보여주고, 반복 학습 기능도 있음
  • 해답이 없으면 독학이 어렵다고 느꼈음. Susanna Epp의 Discrete Mathematics With Applications도 좋은 대안임
  • 이런 문제들은 LLM으로 쉽게 해결할 수 있다고 함
  • 실제로 LLM이 증명 오류를 잡아준 경험을 공유함. Gemini가 잘못된 증명을 지적해줘서 유용했음
  • 대학들이 해답집을 공개하지 않는 이유는 문제 재사용 때문임. 제한된 문제 풀을 여러 해에 걸쳐 돌려 쓰기 때문임

• 매우 유용한 자료라며 감사 인사를 전함

• Hacker News 덕분에 찾고 있던 PDF를 발견했다며 기뻐함
  PDF를 읽을 수 있는 스크린 리더 추천을 요청함

  • LaTeX 수식이 포함된 PDF를 읽을 수 있는 리더가 있을지 의문을 제기함
    자신도 수식 기호 대부분을 읽지 못한다고 함