알고리즘

제1장 알고리즘: 효율, 분석 그리고 차수
1.1 알고리즘
1.2 효율적인 알고리즘 개발의 중요성
1.3 알고리즘의 분석
1.4 차 수
1.5 이 책의 개요
연습문제

제2장 분할정복법
2.1 이분검색
2.2 합병정렬
2.3 분할정복식 접근 방법
2.4 빠른정렬(분할교환정렬)
2.5 쉬트라센의 행렬곱셈 알고리즘
2.6 큰 정수 계산법
2.7 임계값의 결정
2.8 분할정복법을 사용할 수 없는 경우
연습문제

제3장 동적계획법
3.1 이항계수 구하기
3.2 최단경로를 구하는 플로이드 알고리즘
3.3 동적계획법과 최적화 문제
3.4 연쇄행렬곱셈
3.5 최적 이진검색 트리
3.6 외판원 문제
연습문제

제4장 탐욕적인 방법
4.1 최소비용 신장 트리
4.2 단일출발점 최단경로 문제를 푸는 다익스트라 알고리즘
4.3 스케줄짜기
4.4 허프만 코드
4.5 탐욕적인 방법과 동적계획법의 비교: 배낭채우기 문제
연습문제

제5장 되추적
5.1 되추적 기술
5.2 n-여왕말 문제
5.3 몬테칼로 알고리즘을 사용한 되추적 알고리즘의 효율성 추정
5.4 부분집합의 합 구하기
5.5 그래프 색칠하기
5.6 해밀튼의 회로 문제
5.7 0-1 배낭채우기 문제
연습문제

제6장 분기한정법
6.1 분기한정을 0-1 배낭채우기 문제로 설명하기
6.2 외판원 문제
6.3 확률적 추론(진단)
연습문제

제7장 계산복잡도의 소개: 정렬 문제
7.1 계산복잡도
7.2 삽입정렬과 선택정렬
7.3 한 번 비교에 최대한 하나의 역이 제거되는 알고리즘의 하한
7.4 합병정렬(재검토)
7.5 빠른정렬(재검토)
7.6 힙정렬 278
7.7 합병정렬, 빠른정렬, 힙정렬의 비교
7.8 키의 비교만으로 정렬하는 경우의 하한
7.9 분배에 의한 정렬(기수정렬)
연습문제

제8장 계산복잡도: 검색 문제
8.1 키를 비교만 하여 검색하는 경우의 하한
8.2 보간검색
8.3 트리에서의 검색
8.4 해시하기
8.5 선택 문제: 반대자(적) 논법의 소개
연습문제

제9장 계산복잡도와 다루기 힘든 정도
9.1 다루기 힘든 정도
9.2 입력크기: 재검토
9.3 3가지 일반적인 문제
9.4 NP이론
9.5 NP-난해 문제의 취급
연습문제

제10장 정수론적 알고리즘
10.1 정수론 개관
10.2 최대공약수 계산
10.3 모듈 산수 개관
10.4 모듈 1차방정식 풀기
10.5 모듈 거듭제곱 계산
10.6 큰 소수 찾기
10.7 RSA 공개키 암호체계
연습문제

제11장 병렬 알고리즘의 소개
11.1 병렬 구조
11.2 PRAM 모델
연습문제

부록 A필요한 수학의 복습
A.1 표기법
A.2 함수
A.3 수학적 귀납법
A.4 정리와 보조정리
A.5 대수
A.6 집합
A.7 순열과 조합
A.8 확률
연습문제 531

부록 B 식의 해 구하기
B.1 귀납법을 이용하여 재현식의 해 구하기
B.2 특성식을 이용하여 재현식의 해 구하기
B.3 치환에 의한 재현식의 해 구하기
B.4 n을 b(양의 상수)의 거듭제곱으로 하여 얻은 결과를 모든 n으로 확장하기
B.5 정리의 증명
연습문제

부록 C서로소집합의 데이터구조

참고문헌
찾아보기