1
IT1110 Tin h c đi c ngọ ạ ươ
Ph n II Gi i quy t bài toánầ ả ế
Nguy n Bá Ng cễ ọ
Ôn t p n i dung ph n Iậ ộ ầ
Ph n I: TIN H C CĂN B Nầ Ọ Ả
Thông tin
Bi u di n d li u trong máy tínhể ễ ữ ệ
Máy tính và m ng máy tínhạ
H đi u hành và các h th ng ng d ngệ ề ệ ố ứ ụ
3
N i dung ph n IIộ ầ
Ch ng 1: Gi i quy t bài toán b ng máy tínhươ ả ế ằ
Khái ni m v bài toánệ ề
Quá trình gi i quy t bài toán b ng máy tínhả ế ằ
Các ph ng pháp gi i quy t bài toán b ng máy tínhươ ả ế ằ
Phân lo i bài toánạ
Ch ng 2: Thu t toánươ ậ
Đnh nghĩa thu t toánị ậ
Bi u di n thu t toánể ễ ậ
M t s thu t toán thông d ngộ ố ậ ụ
Thu t toán đ quyậ ệ
Thu t gi i heuristicậ ả
4
N i dung ph n IIộ ầ
Ch ng 1: Gi i quy t bài toán b ng máy tínhươ ả ế ằ
Khái ni m v bài toánệ ề
Quá trình gi i quy t bài toán b ng máy tínhả ế ằ
Các ph ng pháp gi i quy t bài toán b ng máy tínhươ ả ế ằ
Phân lo i bài toánạ
Ch ng 2: Thu t toánươ ậ
Đnh nghĩa thu t toánị ậ
Bi u di n thu t toánể ễ ậ
M t s thu t toán thông d ngộ ố ậ ụ
Thu t toán đ quyậ ệ
Thu t gi i heuristicậ ả
5
1.1. Khái ni m v v n đ và bài toánệ ề ấ ề
V n đ r ng h n bài toán?ấ ề ộ ơ
Pitago chia v n đ ra:ấ ề
Theorema là v n đ c n đc kh ng đnh đúng-saiấ ề ầ ượ ẳ ị
Problema là v n đ c n tìm gi i pháp đ đt đc m t ấ ề ầ ả ể ạ ượ ộ
m c tiêu xác đnh t nh ng đi u ki n ban đu.ụ ị ừ ữ ề ệ ầ
Di n đt b ng s đ: A ễ ạ ằ ơ ồ B
A là gi thi t, đi u ki n ban đuả ế ề ệ ầ
B là k t lu n, m c tiêu c n đtế ậ ụ ầ ạ
là suy lu n, gi i pháp c n xác đnhậ ả ầ ị