Search

이 책은 알고리즘의 분석과 디자인, 과학적 연산, 몬테카를로 시뮬레이션, 병렬 알고리즘에 이르기까지 다양한 내용을 다룹니다. 이 책에는 알고리즘에 대한 엄밀한 증명은 담지 않았습니다. 대신, 알고리즘의 정의와 이를 응용한 실제 코드 구현에 초점을 맞췄습니다. 각 코드는 알고리즘을 구현하는 데 필요한 수식과 함께 자세히 설명합니다. 모든 학문의 기초가 되는 알고리즘을 통해 금융과 물리, 생물, 컴퓨터 분야의 다양한 문제를 해결하는 방법을 배워봅시다.

문제를 해결하는 알고리즘의 코드 구현
이 책은 알고리즘의 분석과 디자인, 과학적 연산, 몬테카를로 시뮬레이션, 병렬 알고리즘에 이르기까지 다양한 내용을 다룹니다. 이 책에는 알고리즘에 대한 엄밀한 증명은 담지 않았습니다. 대신, 알고리즘의 정의와 이를 응용한 실제 코드 구현에 초점을 맞췄습니다. 각 코드는 알고리즘을 구현하는 데 필요한 수식과 함께 자세히 설명합니다. 코드는 모듈 형태로 만들고 재사용해서 추가 연산을 최소화하였습니다.

다양한 분야의 응용 예제
흔히 지식을 영역별로 구분하지만, 학문의 기초를 이루는 아이디어와 방법론은 그리 다양하지 않습니다. 이 책에서는 금융과 물리, 생물, 컴퓨터 분야의 예제를 제시하여 학제 간에 상호 접근이 가능하게 했습니다. 또한, 코드에서 정의한 함수는 여러 업무에서 응용할 수 있는 예제로 이해를 도왔습니다.
여러분은 이 책을 통해 다양한 분야에서 컴퓨터를 사용하여 문제를 푸는 방법을 배울 수 있습니다.

이 책의 구성
- 1장에서는 이 책에 대해 전반적인 내용을 소개한다.

- 2장에서는 프로그래밍 언어로 파이썬을 소개한다. 이 책의 독자는 기본 프로그래밍 개념, 즉 조건문과 반복문, 함수 호출 등을 알고 있다고 가정한다. 여기서는 파이썬의 기초 구문을 설명한다. 특히나 과학 분야의 응용프로그램에서 중요한 내장 모듈(math, cmath, decimal, random) 등을 중점적으로 설명한다.

- 3장에서는 알고리즘의 일반 이론을 살펴보고 어디에 적용하는지 알아본다. 간단한 반복문에서 복잡한 재귀 알고리즘까지 실행 시간을 측정하는 방법도 알아본다. 리스트와 배열, 스택, 큐, 트리, 그래프와 같이 정보를 저장하는 기본 자료구조에 대해서도 살펴본다. 분할 정복(divide-and-conquer) 알고리즘과 동적 프로그래밍, 탐욕(greedy) 알고리즘도 검토해 본다. 예제를 통해서 샤논-파노(Shannon-Fano) 압축과 미로(maze) 해법, 클러스터링 알고리즘, 신경망 같이 복잡한 알고리즘도 간단히 다룬다.

- 4장에서는 전통적인 수치 알고리즘과 선형 대수, 문제 풀이 해법(solver), 최적화, 적분기(integrator), 푸리에-라플라스(Fourier-Laplace) 변환 등을 다룬다. 먼저 테일러 급수의 개념을 살펴보고 근사치와 오류 원인, 수렴 등의 개념을 배우게 된다. 이들 개념을 사용하면 더 복잡한 알고리즘을 만들 수 있고 1차 선형 근사치를 좀 더 개선해서 체계적으로 구할 수 있다. 선형 대수는 다변수 함수를 근사하거나 구현할 때 사용하면 좋다.

- 5장에서는 확률과 통계를 살펴보고, 파이썬의 기본 함수를 구현해서 확률 변수의 통계 분석을 수행해 본다.

- 6장에서는 다양한 분포로부터 난수를 만드는 알고리즘을 토론해 본다. 파이썬에는 난수를 만드는 내장 모듈이 있는데 이는 7장에서 사용하기로 한다. 이 장에서는 의사(pseudo) 난수 생성기(generator)가 작동하는 방식과 단점이 있다면 무엇인지 알아본다.

- 7장에서는 몬테카를로 시뮬레이션을 해본다. 이 수치 기법은 결정론적인 문제를 푸는 데에도 난수를 사용한다. 예를 들어, 4장에서는 일차원 수치 적분에 대해 설명한다. 그런데 그때 사용한 알고리즘은 2차원 이상에서 수치 적분을 할 수 있도록 확장할 수 있으나 차원 수가 많아지면 사용할 수 없다. 변수가 늘어나면 선택지에 오르는 적분법도 많아지는데 몬테카를로 적분이 하나의 해법이다. 몬테카를로 시뮬레이션을 어떻게 응용하는지 알아본다.

- 8장에서는 병렬 알고리즘에 대해 알아본다. 병렬 프로그램에는 많은 패러다임(paradigm)이 존재하고 이질적인 아키텍처(architecture)를 지향하는 경향이 있다. 여기서는 여러 유형의 아키텍처 중에서도 성공적인 세 가지 프로그래밍 패러다임에 중점을 둔다. 바로 메시지 전달(message-passing)과 맵-리듀스(map-reduce), 다중 스레드 GPU 프로그래밍이다. 메시지 전달에서는 간단하게 파이썬으로 병렬 시뮬레이터를 만든다. 그럼으로써 메시지 전달에 대한 기본 원리와 서로 다른 네트워크 토폴로지에서 발생하는 문제를 이해하게 된다. GPU에서는 pyOpenCL과 ocl, Python-to-OpenCL 컴파일러를 사용한다. 파이썬으로 코드를 작성하고 이를 실시간으로 OpenCL로 변환하여 GPU에서 실행해본다.

1장 서론
1 주요 아이디어
2 파이썬에 대하여
3 이 책의 구성
4 이 책에서 사용하는 소프트웨어

2장 파이썬 개요
1 파이썬에 대하여
2 변수의 자료형
3 파이썬 제어문
4 클래스
5 파일 입/출력
6 모듈 가져오기

3장 알고리즘 이론
1 알고리즘의 연산 증가 차수
2 재귀와 점화식
3 알고리즘의 유형
4 알고리즘의 시간 측정
5 자료구조
6 트리 알고리즘
7 그래프 알고리즘
8 탐욕 알고리즘
9 인공 지능과 기계 학습
10 긴 반복과 무한 반복

4장 수치 알고리즘
1 우량 조건이고 안정적인 문제
2 근사치와 오차 분석
3 표준 전략
4 선형 대수
5 희소 행렬 역변환
6 비선형 방정식의 해법
7 1차원에서 최적화
8 다변수 함수
9 비선형 피팅
10 적분
11 푸리에 변환
12 미분 방정식

5장 확률과 통계
1 확률
2 조합론과 이산 확률 변수

6장 난수와 분포
1 무작위성과 결정론, 혼돈, 질서
2 실제 무작위성
3 엔트로피 생성기
4 의사 무작위성
5 병렬 생성기와 독립 수열
6 주어진 분포에서 난수 생성하기
7 연속 확률 변수의 확률 분포
8 리샘플링
9 비닝

7장 몬테카를로 시뮬레이션
1 소개
2 오차 분석과 부트스트랩
3 범용 몬테카를로 엔진
4 몬테카를로 적분
5 확률 과정과 마르코프 과정, 위너 과정
6 옵션 가격 결정
7 메트로폴리스
8 모의 담금질

8장 병렬 알고리즘
1 병렬 아키텍처
2 병렬 지표
3 메시지 전달
4 mpi4py
5 마스터-워커와 맵-리듀스
6 pyOpenCL

찾아보기