Bài giảng Tin học đại cương - Trần Quang Diệu - Chương 3: Tổng quan phương pháp giải bài toán trên máy tính

TIN HỌC ĐẠI CƯƠNGChương 3:Tổng quan Phương pháp giải bài toán trên máy tính Dùng cho nhóm ngành: Công trình + Cơ khíTin học đại cương - Chương 32Nội dungKhái niệm về vấn đề và bài toánCác bước giải quyết bài toán bằng máy tínhThuật toán và thuật giảiBiểu diễn thuật toán và thuật giảiMột số thuật toán thường gặpTin học đại cương - Chương 332.1. Khái niệm bài toán và thuật toánBài toánTrong phạm vi tin học, bài toán được hiểu là một công việc nào đó mà ta muốn máy tính thực hiện.2 yếu tố quan trọng của bài toán:Input: dữ liệu đưa vào Output: kết quả cần tìm của bài toán.Vd: Viết một dòng chữ ra màn hình. Bài toán giải phương trình bậc 2; Bài toán quản lý điểm..v.vThuật toánLà một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho khi thực hiện dãy thao tác đó thì từ Input của bài toán ta sẽ có Output cần tìmTin học đại cương - Chương 342.2. Các bước giải bài toánBước 1 - Xác định bài toánXác định rõ Input và Output của bài toán.Cần xác định input, output một cách cẩn thận vì nó sẽ ảnh hưởng tới việc lựa chọn thuật toán giải quyết. Trong tin học, đôi khi việc xác định input/output còn phụ thuộc vào ngôn ngữ lập trình sử dụng.Bước 2 - Thiết kế thuật toánLà bước quan trọng nhất để giải bài toánMột bài toán có thể có nhiều thuật toán để giải quyếtCần quan tâm tới tính hiệu quả của thuật toán (về bộ nhớ, về thời gian thực hiện..v.v)Tin học đại cương - Chương 352.2. Các bước giải bài toán (tt)Bước 3 – Viết chương trìnhLựa chọn ngôn ngữ lập trình phù hợp với nhu cầu và khả năng của bản thânCần tận dụng các tiện ích mà các IDE (Integrated Deverlopment Environment)Bước 4 – Hiệu chỉnh, làm tinh chương trìnhCần đưa nhiều bộ số liệu khác nhau vào kiểm thửĐôi khi cần có kinh nghiệm và đầu óc phán đoán lỗi.Bước 5 – Viết tài liệuLà hướng dẫn sử dụng, kết quả thử nghiệm, hoặc mô tả chi tiết thuật toánTin học đại cương - Chương 362.3. Thuật toán – Thuật giảiĐịnh nghĩa:Thuật toán (algorithm) là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho khi thực hiện dãy thao tác đó thì từ Input của bài toán ta sẽ có Output cần tìm.Các đặc trưng của thuật toánTính hữu hạnTính xác địnhTính đúng đắnTính chi tiết: thao tác trong thuật toán phải chặt chẽ, đủ chi tiết để 1 đối tượng có thể thực hiện được thuật toán.Tính phổ dụngTin học đại cương - Chương 37Từ giải thuật đến chương trìnhGiải thuật chỉ là “phương pháp”.Sử dụng giải thuật như thế nào để giải quyết bài toánCần phải có máy tính.Lập trình: Mô tả (cài đặt) giải thuật lên máy tính.Biểu diễn đối tượng xử lý bởi dữ liệu (data) trong chương trình (có nhiều kiểu dữ liệu với cấu trúc khác nhau).Thuật giải + cấu trúc dữ liệu = chương trìnhALGORITHMSDATA STRUCTURESPROGRAM+=Tin học đại cương - Chương 38Có phải mọi bài toán đều có thuật giải ?Có những bài toán không có giải thuật tổng quát để giải quyết.Có những bài toán chưa có giải thuật hữu hiệu để giải quyết.Có những bài toán chưa có giải thuật tìm lời giải.Tin học đại cương - Chương 392.4. Biểu diễn thuật toánLiệt kê từng bướcSử dụng sơ đồ khốiSử dụng giả ngôn ngữ lập trìnhTin học đại cương - Chương 310Phương pháp liệt kê từng bướcCác thao tác của giải thuật được liệt kê từng bước.Tại mỗi bước, sử dụng ngôn ngữ tự nhiên để diễn tả công việc phải làm.Bước đứng trước (có số thứ tự nhỏ hơn) được thực hiện trước.Ưu nhược điểmDễ hiểu, dễ làmPhụ thuộc vào “cách hành văn” của người diễn đạtVới những giải thuật phức tạp, cách diễn đạt này trở nên rườm ràTin học đại cương - Chương 311Ví dụGiải thuật “Tìm vị trí xuất hiện đầu tiên của một số nguyên trong dãy số nguyên đã cho”:Bước 1: Nhập dãy số nguyên a1, a2, ., aNBước 2: Nhập số nguyên sBước 3: Gán vị trí p ban đầu = 0 và vị trí i đang xét = 1 p = 0, i=1Bước 4: So sánh ai với sNếu ai =s thì ghi nhận vị trí p = i  Sang Bước 5Nếu ai ≠ s và i c) và (b+c>a) và (a+c>b) thì sang bước 3Nếu không thì thông báo “không tạo thành tam giác” và kết thúcB3. Tính chu vi C = (a+b+c)B4. Tính nửa chu vi p = C/2B5. Tính diện tích tam giác theo công thức Hê-rôngS =B6. In kết quả C,SSơ đồ thuật toánTin học đại cương - Chương 317Biểu diễn thuật toán bằng giả ngôn ngữGiả ngôn ngữDựa trên ngôn ngữ lập trình bậc cao.Gần với ngôn ngữ tự nhiên của con người.Ví dụ:Ngôn ngữ giả Pascal (tựa Pascal) có các ký pháp khá giống với ngôn ngữ lập trình Pascal, được rút gọn sao cho dễ diễn đạt.Giả ngôn ngữ được đưa ra với mục đích diễn đạt các giải thuật sao cho gần với ngôn ngữ lập trình và ngôn ngữ tự nhiên.Sử dụng giả ngôn ngữ khiến việc chuyển từ giải thuật sang chương trình dễ dàng hơn.Tin học đại cương - Chương 318Giải thuật tính tổng N số tự nhiên đầu tiênNhập Ni:=0S:=0REPEATS:=S+ii:=i+1UNTIL (i>N)In STin học đại cương - Chương 319Thiết kế thuật toánCác bước giải bài toán trên máy tính:Xác định bài toánThiết kế giải thuậtViết chương trìnhHiệu chỉnh, làm tinhViết tài liệuThiết kế giải thuật là từ yêu cầu của một bài toán, diễn đạt một giải thuật giải quyết bài toán đó.Mô-đun hoá việc giải quyết bài toán.Tinh chỉnh từng bước.Phân tích giải thuậtXem xét các tiêu chuẩn của giải thuật có được thoả mãn không, nếu có thì đến mức độ nào.Tin học đại cương - Chương 320Thiết kế từ trên xuốngCác bài toán lớn đòi hỏi giải thuật có quy mô lớn.Mô-đun hoáBài toán = nhiều mô-đunMô-đun lớn = nhiều mô-đun con.Việc giải quyết một mô-đun ở mức thấp nhất là “đủ đơn giản”Chia để trị.Thiết kế từ trên xuống (top-down design): Bài toán được xem xét từ tổng quát đến chi tiết.BÀI TOÁNABCA1A2A2.1A2.2C1C2A2.3Tin học đại cương - Chương 321Bài toán giải phương trình bậc 2GIẢI PHƯƠNG TRÌNH BẬC IINHẬP HỆ SỐXỬ LÝHIỂN THỊ KẾT QUẢTRƯỜNG HỢP SUY BIẾNTRƯỜNG HỢP KHÔNG SUY BIẾNTÍNH DELTATÍNH NGHIỆM THEO DELTATin học đại cương - Chương 322Phương pháp tinh chỉnh từng bướcPhương pháp tinh chỉnh từng bước (stepwise refinement)Ban đầu, sử dụng ngôn ngữ tự nhiên để diễn tả những công việc chính của giải thuật.Các bước sau, các công việc được chi tiết hoá dần dần, ngôn ngữ tự nhiên được thay thế dần dần bằng giả ngôn ngữ.Cuối cùng, giả ngôn ngữ được chuyển sang ngôn ngữ lập trìnhĐặc điểmThể hiện rõ ý tưởng thiết kế từ trên xuốngGắn liền việc thiết kế giải thuật với việc lập trìnhTin học đại cương - Chương 323Bài toán sắp xếp dãy số (tăng dần)Phác thảo “thô” với những “ý tưởng cơ bản”“Từ dãy các số chưa được sắp xếp, tìm số nhỏ nhất và đưa lên đầu”Lặp lại quy trình trên tới khi dãy chưa được sắp xếp trở thành rỗng.Ban đầu, dãy chưa sắp xếp là dãy đã cho, dãy đã sắp xếp là rỗng.Lưu trữ dãy bằng “mảng” (danh sách các số), đưa số nhỏ nhất (aj) lên đầu danh sách là đổi chỗ nó với số đầu tiên.Đổi chỗSố trung gian := ajaj := số đầu tiênSố đầu tiên : = số trung gian, cuối cùng ta được chương trình với ngôn ngữ cụ thểTin học đại cương - Chương 324Phân tích thuật toánTính đúng đắnChạy thử nghiệm, đối chiếu kết quả  phát hiện được tính sai.Dùng công cụ toán học để chứng minh  tính đúng đắn.Tính đơn giảnGiải thuật có dễ hiểu, dễ lập trình không?Tính hiệu quảĐơn giản chưa chắc đã hiệu quả.Đối với nhiều bài toán, tính hiệu quả là quan trọng, các giải thuật đơn giản lại gây tốn tài nguyên, chạy chậm.Thời gian tính toán  Độ phức tạp tính toánNhững giải thuật hiệu quả phải có độ phức tạp (thời gian) tính toán chấp nhận được.Tính hữu hạn dừngChứng minh, suy luậnChạy thửTin học đại cương - Chương 325Độ phức tạp của thuật toánĐộ phức tạp thời gian: Là thời gian máy tính sử dụng để giải bài toán theo giải thuật đang xét. (với bộ input có kích thước xác định)Có thể biểu diễn thông qua số lượng các phép tính được dùng bởi thuật toán.Độ phức tạp không gianLà dung lượng bộ nhớ cần thiết mà máy tính sẽ sử dụng để giải bài toán theo giải thuật đang xét (với bộ input có kích thước xác định)Ví dụ:Bài toán tìm số lớn nhất trong dãy số a1, a2,,aN.Nếu coi phép so sánh 2 số của thuật toán cần 1 đơn vị thời gian  Độ phức tạp thời gian của thuật toán sẽ là n-1 (nếu Tin học đại cương - Chương 326Độ phức tạp của thuật toán (tt)Thuật toán 1S = a0;For i = 1 To n S = S + ai*x0iSố phép tính(* và + ) là: n(n+3)/2Thuật toán 2S = 0;For i = 1 To n S = x*(an-i+1 + S )Số phép tính(* và + ) là: 2nBài toán tính giá trị đa thức: P(x) = anxn + an-1xn-1 + + a1x + a0 Khi x = x0Tin học đại cương - Chương 327Độ phức tạp của thuật toán (tt)Hàm thể hiện độ phức tạp của thuật toánĐể so sánh độ phức tạp của các thuật toán người ta coi độ phức tạp của mỗi thuật toán như là cấp của hàm biểu hiện thời gian thực hiện thuật toán đó.Định nghĩa Big-Ohàm f(n) có cấp thấp hơn hoặc bằng hàm g(n) nếu tồn tại hằng C > 0 và một số tự nhiên n0 sao cho |f(n)| ≤ C|g(n)| với mọi n ≥ n0 Ta viết f(n) = O(g(n)) hay còn nói hàm f(n) thỏa mãn quan hệ Big-O với g(n)vd: f(n) = n(n+3)/2 và g(n) = n2 khi đó f(n) = O(g(n)) = O(n2) vì f(n) ≤ 3 g(n) với n≥3Tin học đại cương - Chương 328Độ phức tạp của thuật toán (tt)Định nghĩanếu một thuật toán có độ phức tạp là f(n) trong đó f(n) = O(g(n)) thì ta nói thuật toán đó cũng đồng thời có độ phức tạp là “O lớn g(n)”nếu bài toán có 2 thuật toán với độ phức tạp lần lượt là O(g1(n)) và O(g2(n)) mà bậc của g1(n) thấp hơn bậc của g2(n) thì ta nói thuật toán 1 hiệu quả hơn thuật toán 2 Một cách tổng quát: nếu f(n) = aknk + ak-1nk-1+...+a1n+a0 thì f(n) = O(nk)(f1 + f2)(n) = O(max(|g1(n)|,|g2(n)|), (f1f2)(n)) = O(g1(n)g2(n))Tin học đại cương - Chương 329Độ phức tạp của thuật toán (tt)Các thuật ngữ thường dùngTin học đại cương - Chương 330Độ phức tạp của thuật toán (tt)Độ phức tạp thuật toán và Thời gian thực hiệnTin học đại cương - Chương 3312.5. Một số thuật toán thường gặpBài toán tìm kiếmThuật toán tìm kiếm tuyến tínhThuật toán tìm kiếm nhị phânBài toán tìm số USCLN của 2 sốThuật toán lặp, kiểm tra các giá trị từ 1,2,...,min(a, b)Thuật toán phân tích các số nguyên đã cho thành các thừa số nguyên tố.Thuật toán euclideBài toán sắp xếp dãy tăng/giảm dầnThuật toán nổi bọt (bubble sort)Thuật toán chọn trực tiếp (selection sort)Thuật toán chèn trực tiếp (insertion sort)Thuật toán sắp vun đống (heap sort)Tin học đại cương - Chương 3322.5. Một số thuật toán thường gặpThuật toán đệ quyĐịnh nghĩa: Một thuật toán được gọi là đệ quy nếu nó giải bài toán bằng cách rút gọn liên tiếp bài toán ban đầu tới bài toán đồng dạng với dữ liệu đầu vào nhỏ hơn.Ví dụ:Bài toán tính n!Bài toán tìm số thứ n của dãy số FibonaciBài toán tìm USCLN của 2 số a, bBài toán tìm kiếm nhị phânBài toán tháp Hà NộiTin học đại cương - Chương 333Bài tậpVẽ sơ đồ biểu diễn thuật toán tìm trung bình cộng của dãy số a1, a2, , anVẽ sơ đồ biểu diễn thuật toán tìm TBC các số chẵn và chia hết cho 5 trong dãy số a1, a2, , anVẽ sơ đồ biểu diễn thuật toán đếm xem trong dãy số a1, a2, , an có bao nhiêu cặp có chỉ số liên tiếp (vd: a2, a3) thỏa điều kiện tích chúng chia hết tổng của chúng.Vẽ sơ đồ khối biểu diễn thuật toán kiểm tra xem 1 số nguyên N có là số nguyên tố hay không?Tin học đại cương - Chương 334Bài tập (tt)Hãy vẽ sơ đồ thuật toán tìm và in ra các số là số nguyên tố trong dãy số a1, a2,...,aNHãy vẽ sơ đồ thể hiện thuật toán tính giá trị của biểu thức Hãy vẽ sơ đồ thuật toán tìm trong số các phần tử của dãy a1, a2,...,aN có bao nhiêu cặp (ai, aj) với i≠j thỏa điều kiện ai+aj = xHãy vẽ sơ đồ thể hiện thuật toán đổi một số nguyên dương N sang hệ đếm cơ số 2 (hệ nhị phân).Hãy vẽ sơ đồ thể hiện thuật toán giải phương trình bậc 2 ax2+ bx + c = 0Hãy vẽ sơ đồ thể hiện toán tìm tích của 2 ma trận Amxn và BnxpHãy vẽ sơ đồ thể hiện thuật toán tìm độ dài của đường gấp khúc đi qua N điểm trên mặt phẳng M1(x1, y1), M2(x2, y2),....,Mn(xn, yn).Vẽ sơ đồ thể hiện thuật toán sắp xếp lại dãy số a1, a2,...,an theo thứ tự giảm dần.Vẽ sơ đồ thể hiện thuật toán tìm các phần tử trong dãy a1, a2,...,an thỏa điều kiện ai = ai-1 + ai-2 + ...+ a2+ a1Vẽ sơ đồ thể hiện thuật toán tìm trung bình cộng của các phần tử là số chính phương trong dãy a1, a2,...,aNTin học đại cương - Chương 335