상세정보

대수학과 이산구조의 기초 지식을 습득한 전산관련 공학도들이 쉽게 이해할 수 있도록 알고리즘 설계, 알고리즘 복잡도 분석, 계산 복잡도를 균형있게 소개한 전공서이다. 수학적 개념을 보다 알기 쉽게 해설하고 기초개념을 부록에 정리했다.

정보제공 :

목차
제1장 알고리즘 : 효율, 분석, 그리고 차수 = 1
 1.1 알고리즘 = 2
 1.2 효율적인 알고리즘 개발의 중요성 = 11
 1.3 알고리즘의 분석 = 19
 1.4 차수 = 29
 1.5 이 책의 개요 = 49
 연습문제 = 50
제2장 분할정복법 = 55
 2.1 이분검색 = 56
 2.2 합병정렬 = 61
 2.3 분할정복식 접근 방법 = 69
 2.4 빠른정렬(분할교환정렬) = 70
 2.5 쉬트라센의 행렬곱셈 알고리즘 = 77
 2.6 큰 정수 계산법 = 83
 2.7 임계값의 결정 = 90
 2.8 분할정복법을 사용할 수 없는 경우 = 95
 연습문제 = 96
제3장 동적계획법 = 103
 3.1 이항계수 구하기 = 104
 3.2 최단경로를 구하는 플로이드 알고리즘 = 109
 3.3 동적계획법과 최적화 문제 = 118
 3.4 연쇄행렬곱셈 = 120
 3.5 최적 이진검색 트리 = 130
 3.6 외판원 문제 = 141
 연습문제 = 149
제4장 탐욕적인 방법 = 153
 4.1 최소비용 신장 트리 = 158
 4.2 단일출발점 최단경로 문제를 푸는 다익스트라 알고리즘 = 173
 4.3 스케줄짜기 = 177
 4.4 탐욕적인 방법과 동적계획법의 비교 : 배낭채우기 문제 = 188
 연습문제 = 196
제5장 되추적 = 201
 5.1 되추적 기술 = 202
 5.2 n-여왕말 문제 = 211
 5.3 몬테칼로 알고리즘을 사용한 되추적 알고리즘의 효율성 추정 = 216
 5.4 부분집합의 합 구하기 = 220
 5.5 그래프 색칠하기 = 226
 5.6 해밀튼의 회로 문제 = 231
 5.7 0-1 배낭채우기 문제 = 235
 연습문제 = 246
제6장 분기한정법 = 251
 6.1 분기한정을 0-1 배낭채우기 문제로 설명하기 = 254
 6.2 외판원 문제 = 265
 6.3 확률적 추론(진단) = 275
 연습문제 = 285
제7장 계산복잡도의 소개 : 정렬 문제 = 289
 7.1 계산복잡도 = 290
 7.2 삽입정렬과 선택정렬 = 292
 7.3 한 번 비교에 최대한 하나의 역이 제거되는 알고리즘의 하한 = 298
 7.4 합병정렬(재검토) = 301
 7.5 빠른정렬(재검토) = 307
 7.6 힙정렬 = 309
 7.7 합병정렬, 빠른정렬, 힙정렬의 비교 = 321
 7.8 키의 비교만으로 정렬하는 경우의 하한 = 322
 7.9 분배에 의한 정렬(기수정렬) = 333
 연습문제 = 338
제8장 계산복잡도 : 검색 문제 = 345
 8.1 키를 비교만 하여 검색하는 경우의 하한 = 346
 8.2 보간검색 = 357
 8.3 트리에서의 검색 = 361
 8.4 해쉬하기 = 368
 8.5 선택문제 : 반대자(적)논법의 소개 = 373
 연습문제 = 403
제9장 계산복잡도와 다루기 힘든 정도 = 409
 9.1 다루기 힘든 정도 = 410
 9.2 입력크기(재검토) = 412
 9.3 문제의 3가지 일반적인 분류 = 417
 9.4 NP 이론 = 419
 9.5 NP-난해 문제의 취급 = 444
 연습문제 = 455
제10장 병렬 알고리즘의 소개 = 459
 10.1 병렬 구조 = 462
 10.2 PRAM 모델 = 469
 연습문제 = 484
부록A 필요한 수학의 복습 = 487
 A.1 표기법 = 487
 A.2 함수 = 489
 A.3 수학적 귀납법 = 490
 A.4 정리와 보조정리 = 497
 A.5 대수 = 499
 A.6 집합 = 504
 A.7 순열과 조합 = 505
 A.8 확률 = 509
 연습문제 = 522
부록B 재현식의 해 구하기 : 재귀 알고리즘 분석에의 응용 = 527
 B.1 귀납법을 이용하여 재현식의 해 구하기 = 527
 B.2 특성식을 이용하여 재현식의 해 구하기 = 531
 B.3 치환에 의한 재현식의 해 구하기 = 550
 B.4 n을 b(양의 상수)의 거듭제곱으로 하여 얻은 결과를 모든 n으로 확장하기 = 553
 B.5 정리의 증명 = 561
 연습문제 = 563
부록C 서로소집합의 데이터 구조 = 569
참고문헌 = 581
찾아보기 = 585