1
TIN HỌC ĐẠI CƯƠNG
www.uit.edu.vn
BÀI 6
BÀI 6
PHƯƠNG PHÁP GIẢI CÁC
PHƯƠNG PHÁP GIẢI CÁC
BÀI TOÁN TRONG TIN HỌC
BÀI TOÁN TRONG TIN HỌC
Tin học đại cương
2
NỘI DUNG

Khái niệm về vấn đề và bài toán.

Các bước giải quyết vấn đề - bài
toán trên máy tính.

Thuật toán và thuật giải.

Biểu diễn thuật toán và thuật giải.
Tin học đại cương
3
KHÁI NIỆM VỀ VẤN ĐỀ - BÀI TOÁN

Bài toán và giải quyết bài toán được biểu
diễn dưới dạng:
A → B
giả thiết giải pháp mục tiêu


Nhằm phát biểu chính xác vấn đề - bài toán, làm rõ
những yêu cầu, xác định tính khả thi.
Bước 2: Lựa chọn phương pháp giải.
Thường có nhiều cách khác nhau → Tùy theo nhu
cầu thực của bài toán mà chọn lựa p/pháp phù hợp.
Bước 3: Xây dựng thuật toán hoặc thuật giải.
Chi tiết hóa phương pháp đã lựa chọn. Thường theo
cấu trúc phân tích → Vấn đề TOP-DOWN.
Bước 4: Cài đặt chương trình.
Từ thuật giải, dùng NNLT để hiện thực hóa.
Bước 5: Hiệu chỉnh & Thực hiện chương trình.
Sửa lỗi, gồm: lỗi cú pháp và lỗi ngữ nghĩa.
Bước 6: Lưu trữ, Bảo trì.
Tin học đại cương
6
XÁC ĐỊNH CẤU TRÚC DỮ LIỆU

Niklaus Wirth:
Cấu trúc dữ liệu + Thuật giải = Ch. trình

Dữ liệu và cấu trúc dữ liệu đóng vai trò
quan trọng trong việc kết hợp và đưa ra
cách giải quyết bài toán.

Một số lưu ý về CTDL:

Phải biểu diễn đầy đủ thông tin.

Phù hợp các thao tác của thuật toán.



Có những bài toán không xác định (có)
thuật toán cụ thể.

Hoặc có thuật toán nhưng không thực
hiện được (chẳng hạn vì thời gian dài).

Hoặc có cách giải vi phạm thuật toán
nhưng vẫn được chấp nhận.

Heuristic: Giải quyết bài toán với kết quả
đúng (gần đúng) trong p. vi cho phép.
Tin học đại cương
9
BIỂU DIỄN THUẬT TOÁN

Ngôn ngữ tự nhiên.

Sơ đồ khối.

Mã giả.

Ngôn ngữ lập trình.
Tin học đại cương
10
NGÔN NGỮ TỰ NHIÊN

NN tự nhiên thông qua các bước được
tuần tự liệt kê để BD thuật toán.


LƯU ĐỒ
Tính F = N!
Tin học đại cương
13
MÃ GIẢ

Ngôn ngữ tựa ngôn ngữ lập trình.

Dùng cấu trúc chuẩn hóa, chẳng hạn
tựa Pascal, C.

Dùng các ký hiệu toán học, biến, hàm.

Ưu điểm:

Đỡ cồng kềnh hơn lưu đồ khối.

Nhược điểm:

Không trực quan bằng lưu đồ khối.
Tin học đại cương
14
MÃ GIẢ
Algorithm LargestNumber
Input: Danh sách khác rỗng các con số L.
Output: largest - giá trị số lớn nhất trong d. sách
L.
largest ← L
0


Lỗi và cách sửa.

Lỗi thuật toán.

Lỗi trình tự.

Lỗi cú pháp.

Xây dựng bộ test.

Cập nhật, thay đổi chương trình theo yêu
cầu (mới).
Tin học đại cương
17
TIÊU CHUẨN CỦA CHƯƠNG TRÌNH

Tính tin cậy.

Giải thuật + Kiểm tra cài đặt.

Tính uyển chuyển.

Đáp ứng quy trình làm phần mềm.

Tính trong sáng.

Dễ hiểu và dễ chỉnh sửa.

Tính hữu hiệu.



Ngôn ngữ lập trình Pascal, Quách Tuấn
Ngọc, NXB GD, 1996.

Lập trình căn bản, Đoàn Nguyên Hải ( ), ĐH
BK Tp. HCM, 1994.

Cẩm nang thuật toán - Ứng dụng và cài đặt
bằng C, Nguyễn Phúc Trường Sinh, NXB TK,
2002.

20
www.uit.edu.vn