미르카, 수학에 빠지다 4

프롤로그 / 소년 소녀, 수학의 숲에서 놀다

1. 절대 지지 않는 게임
1. 주사위 던지기
2개의 주사위
2. 동전 던지기
2개의 동전
1개의 동전
복권의 기억
3. 몬티홀 문제
봉투 3개
신의 관점

2. 우직하게 한 걸음 두 걸음
1. 고등학교
테트라
리사
선형 검색
워크 스루
선형 검색의 해석
선형 검색의 해석(v가 있는 경우)
선형 검색의 해석(v가 없는 경우)
2. 알고리즘의 해석
미르카
알고리즘의 해석
경우 통합하기
의미 생각하기
보초를 세운 선형 검색
역사를 만들다
3. 집
우직한 한 걸음

3. 171억 7986만 9184의 고독
1. 순열
서점
이해한 느낌
구체적인 예시
규칙성
일반화
길 만들기
그 녀석
2. 조합
도서실
순열
조합
아스파라거스
이항정리
3. 2°의 분배
파스칼의 삼각형
비트 패턴
지수적 폭발
4. 거듭제곱의 고독
귀갓길
집

4. 확률의 불확실함
1. 확률의 확실함
나눗셈의 의미
2. 확률의 불확실함
같은 확률
진정한 무기
3. 확률 실험
인터프리터
주사위 게임
룰렛 게임
4. 확률의 붕괴
확률의 정의
확률의 의미
수학의 적용
의문에 대한 답
5. 확률의 공리적 정의
콜모고로프
표본공간과 확률분포
확률의 공리
부분집합과 사건
확률의 공리 P1
확률의 공리 P2
확률의 공리 P3
아직 모르겠어요
짝수가 나올 확률
찌그러진 주사위, 옆면으로 세워진 동전
약속
기침

5. 기댓값
1. 확률변수
엄마
테트라
확률변수의 예시
확률분포의 예시
쏟아지는 용어들
기댓값
공평한 게임
2. 선형성
미르카
합의 기댓값은 기댓값의 합
3. 이항분포
동전 이야기
이항분포의 기댓값
합으로 나누다
인디케이터 확률변수
즐거운 숙제
4. 모든 사건이 일어날 때까지
언젠가
전부 쏟아 낼 수 있을까?
배운 것 써먹기
전부 다 쏟아 내기
생각지 못한 말

6. 붙잡기 힘든 미래
1. 그날의 약속
강가
2. 오더
빠른 알고리즘
많아야 n의 오더
퀴즈
많아야 f(n)의 오더
log n
3. 탐색
이진 탐색
예시
해석
정렬
4. 정렬
거품 정렬
예시
해석
오더의 계층
5. 동적 시점, 정적 시점
비교는 몇 번 필요할까?
결정 트리
log n!의 추정
6. 전하다, 그리고 배우다
전하다
배우다

7. 행렬
1. 도서실
미즈타니 선생님
테트랄리에인
2. 유리
불능
부정
정칙
편지
3. 테트라
도서실
행과 열
행렬과 벡터의 곱
연립방정식과 행렬
행렬의 곱
역행렬
4. 미르카
숨은 수수께끼 간파하기
선형 변환
회전
5. 귀갓길
대화

8. 나 홀로 랜덤 워크
1. 집
비 내리는 토요일
티타임
피아노 문제
멜로디의 예시
해법 1: 끈기 게임
해법 2: 아이디어 게임
일반화
흔들리는 마음
2. 아침의 등굣길
랜덤 워크
3. 낮에 교실에서
행렬 연습
흔들리는 마음
4. 방과 후 도서실
떠돌이 문제
A2의 의미
행렬의 n제곱으로
1차 준비: 대각 행렬
2차 준비: 행렬과 역행렬의 샌드위치
고윳값으로
고유 벡터로
An을 구하자
5. 집
약속은 의지의 표현
비 내리는 밤

9. 강하게, 바르게, 아름답게
1. 집
비 내리는 토요일
2. 도서실
논리 퀴즈
충족 가능성 문제
3-SAT
충족하다
할당 연습
NP 완전 문제
3. 귀갓길
서약과 약속
학회
4. 도서실
3-SAT를 푸는 무작위 알고리즘
랜덤 워크
정량적 평가를 향해
또 하나의 랜덤 워크
라운드에 주목
5. 집
행운 평가
합을 간단하게
횟수 평가
6. 도서실
독립과 배반
정밀 평가
스털링의 근사
7. 귀갓길
올림픽
8. 집
논리

10. 무작위 알고리즘
1. 패밀리 레스토랑
비
2. 학교
점심시간
퀵 정렬 알고리즘
기준점으로 하는 수열의 분할(두 날개)
부분 수열의 정렬(재귀)
실행 스텝 수 해석
경우 나누기
최대 실행 스텝 수
평균 실행 스텝 수
귀갓길
3. 집
형태를 바꿔서
Hn과 log n
4. 도서실
미르카
무작위 퀵 정렬
비교 관찰
기댓값의 선형성
인디케이터 확률변수의 기댓값은 확률과 같다
5. 패밀리 레스토랑
다양한 무작위 알고리즘
준비
6. 나라비쿠라 도서관
아이오딘
긴장
발표
전하다
옥시젠
잇다
뜰
약속의 증표
에필로그 / 시간을 초월하여 ‘영원’과 닿아 있는 수학
맺음말
감수의 글