알고리즘 산책: 수학에서 제네릭 프로그래밍까지

1장 이 책에 관하여

__1.1 프로그래밍과 수학

__1.2 역사적인 관점

__1.3 미리 알아야 할 것

__1.4 로드맵



2장 첫 번째 알고리즘

__2.1 이집트인의 곱셈

__2.2 알고리즘 개선

__2.3 마무리



3장 고대 그리스의 정수론

__3.1 정수의 기하학적인 성질

__3.2 소수 걸러내기

__3.3 코드 구현 및 최적화

__3.4 완전수

__3.5 공측도

__3.6 공측도 개념의 치명적인 약점

__3.7 마무리



4장 유클리드의 알고리즘

__4.1 아테네와 알렉산드리아

__4.2 유클리드의 최대 공약수 알고리즘

__4.3 수학이 없는 밀레니엄

__4.4 영의 기묘한 역사

__4.5 나머지와 몫 알고리즘

__4.6 코드 공유

__4.7 알고리즘 유효성 검증

__4.8 마무리



5장 근대 정수론의 시초

__5.1 메르센 소수와 페르마 소수

__5.2 페르마의 작은 정리

__5.3 상쇄

__5.4 페르마의 작은 정리 증명

__5.5 오일러의 정리

__5.6 모듈러 산술 응용

__5.7 마무리



6장 수학에서의 추상화

__6.1 군

__6.2 단항과 반군

__6.3 군에 관한 정리 몇 가지

__6.4 부분군과 순환군

__6.5 라그랑주 정리

__6.6 이론과 모형

__6.7 범주 이론과 비범주 이론의 예

__6.8 마무리



7장 제네릭 알고리즘 유도 방법

__7.1 알고리즘 요구조건 매듭 풀기

__7.2 A에 대한 요구조건

__7.3 N에 대한 요구조건

__7.4 새로운 요구조건

__7.5 곱셈에서 거듭제곱으로

__7.6 연산 일반화

__7.7 피보나치 수 계산

__7.8 마무리



8장 기타 대수구조

__8.1 스테빈, 다항식 그리고 최대 공약수

__8.2 괴팅겐과 독일의 수학자들

__8.3 뇌터와 추상대수학의 탄생

__8.4 환

__8.5 행렬곱과 반환

__8.6 응용: 소셜 네트워크와 최단 경로

__8.7 유클리드 영역

__8.8 체와 기타 대수구조

__8.9 마무리



9장 수학 지식 체계화 과정

__9.1 증명

__9.2 첫 번째 정리

__9.3 유클리드와 공리적 방법

__9.4 비유클리드 기하학

__9.5 힐베르트의 형식주의 접근법

__9.6 페아노와 그의 공리

__9.7 산술 구축하는 법

__9.8 마무리



10장 기초 프로그래밍 개념

__10.1 아리스토텔레스와 추상화

__10.2 값과 유형

__10.3 개념

__10.4 반복자

__10.5 반복자의 범주와 연산, 속성

__10.6 구간

__10.7 선형 검색

__10.8 이진 검색

__10.9 마무리



11장 순열 알고리즘

__11.1 순열과 호환

__11.2 구간 맞바꾸기

__11.3 회전

__11.4 순환 사용법

__11.5 뒤집기

__11.6 공간 복잡도

__11.7 메모리 적응형 알고리즘

__11.8 마무리



12장 GCD 확장

__12.1 하드웨어의 제약과 더 효율적인 알고리즘

__12.2 슈타인 알고리즘 일반화

__12.3 베주 항등식

__12.4 확장된 GCD

__12.5 GCD의 응용

__12.6 마무리



13장 실전 응용

__13.1 암호학

__13.2 소수 여부 검사법

__13.3 밀러 - 라빈 테스트

__13.4 RSA 알고리즘의 작동 원리

__13.5 마무리



14장 결론



15장 읽을거리



부록 A 표기법



부록 B 일반적인 증명 기법

__B.1 귀류법

__B.2 수학적 귀납법

__B.3 비둘기집 원리



부록 C C++의 기초

__C.1 템플릿 함수

__C.2 개념

__C.3 선언 구문과 유형이 정해진 상수

__C.4 함수 객체

__C.5 전제 조건, 사후 조건 그리고 assert 구문

__C.6 STL 알고리즘과 자료구조

__C.7 반복자와 구간

__C.8 C++11의 using을 이용한 유형 앨리어스와 유형 함수

__C.9 C++11의 리스트 초기화

__C.10 C++11의 람다 함수

__C.11 inline 지시자에 관하여



부록 D 참고문헌

알렉산더 A. 스테파노프 저자 알렉산더 A. 스테파노프 (Alexander A. Stepanov)

모스크바 국립대학교에서 1967년부터 1972년까지 수학을 공부했다. 프로그래밍은 1972년부터 시작했는데 처음에는 소련에서, 그리고 1977년 후로는 미국에서 계속 프로그래밍을 했다. 운영 체제, 프로그래밍 툴, 컴파일러와 라이브러리를 만들었다. GE, 폴리테크닉 대학교, 벨 연구소, HP, SGI, 어도비의 지원을 받아 프로그래밍 기초에 관한 일을 해 왔으며 2009년부터는 아마존의 검색 기술 자회사인 A9.com에서 일하고 있다. 1995년에는 C++ 표준 템플릿 라이브러리(Standard Template Library, STL) 설계에 대한 공로를 인정받아 Dr. Dobb's Journal의 Excellence in Programming Award를 받았다.