1
NHẬP MÔN LẬP TRÌNH
TIN HỌC ĐẠI CƯƠNG
2
BIỂU DIỄN BÀI TOÁN TRÊN MÁY TÍNH
I. Bài toán và thuật toán:

Khái niệm bài toán trong tin học.

Khái niệm thuật toán, các đặc trưng cơ bản của thuật toán.

Biểu diễn bài toán trên máy tính.

Biểu diễn thuật toán.
II. Ngôn ngữ lập trình Pascal

Khái niệm về ngôn ngữ lập trình và chương trình dịch.

Các lệnh cơ bản: lệnh nhập/xuất, lệnh rẽ nhánh (if), lệnh lặp
(while, for).

Sử dụng ngôn ngữ lập trình để giải một số bài toán cơ bản.
3
1. Vấn đề - bài toán
2. Máy tính và việc giải quyết vấn đề - bài
toán
3. Thuật toán - thuật giải
4. Các phương pháp biểu diễn thuật toán
5. Bài tập tổng hợp
I. BÀI TOÁN VÀ THUẬT TOÁN
4

2
+bx+c=0 với a,b,c
là các số cho trước.
A B
A : các số cho trước a,b,c
B : giá trị của x
1,
x
2

cách giải phương trình bậc 2
7
1. Vấn đề - bài toán
Ví dụ 2: Cho bản đồ như sau. Tìm đường đi ngắn nhất
từ thành phố a đến thành phố f
A : Các TP a,b,c,d,e,f và các khoảng cách
B : Độ dài ngắn nhất từ a đến f

phương pháp tìm đường đi ngắn nhất từ a đến f
5
4
8
9
10
3
2
3
a
b
c d


Mỗi loại máy có ngôn ngữ máy của riêng nó

Là tập hợp các dạng câu lệnh

Ưu điểm: cho phép khai thác triệt để và tối ưu khả năng
của máy tính

Nhược điểm: khó viết, chương trình nhận được cồng kềnh
và khó hiệu chỉnh
11
2.1.2. Hợp ngữ (Assembly)

Có cấu trúc rất giống ngôn ngữ máy

Mã lệnh được thay bằng tên viết tắt tương ứng

Chỉ chạy được sau khi đã được dịch ra ngôn ngữ máy
thông qua chương trình hợp dịch (Assembler)

Ưu điểm: khắc phục được nhược điểm của ngôn ngữ máy

Nhược điểm: không phù hợp với số đông người lập trình
12
2.1.3. Ngôn ngữ bậc cao

Mô phỏng ngôn ngữ tự nhiên, sử dụng các ký hiệu toán học
thống nhất chung

Không phụ thuộc vào loại máy tính cụ thể

Là kiểu dịch từng dòng lệnh để hiểu công việc cần làm và
thực hiện ngay chứ không nhất thiết phải tạo ra các
đoạn mã tương đương trong ngôn ngữ máy

Nếu một câu lệnh phải thực hiện nhiều lần thì cũng phải
dịch nhiều lần

Ứng dụng: môi trường đối thoại giữa người và hệ thống
17
2.2.3. Kỹ thuật biên dịch

Là kiểu dịch toàn bộ chương trình ban đầu thành một
chương trình tương ứng trong ngôn ngữ máy (chương
trình đích), sau đó nạp chương trình đích vào máy tính để
thực hiện

Ứng dụng: phù hợp với các chương trình ổn định và phải
thực hiện nhiều lần
18
Một số ngôn ngữ lập trình thông dụng

Basic được thiết kế bởi John G. Kemeny và Thomas
E. Kurtz tại ĐH Dartmouth vào 1963

Pascal được Niklaus Wirth phát thiết kế năm 1970

C do Dennis Richie thiết kế năm 1972 tại phòng thí
nghiệp Bell Telephone của hãng AT&T sử dụng
trong hệ điều hành Unix


thi

Tính hữu hạn
Số bước của thuật toán là hưu hạn và có tính chất dừng

Tính đúng đắn
Thuật toán phải cho kết quả đúng như mong muốn.
22
3.3 Đặc trưng của thuật toán

Đầu vào và đầu ra
Mọi thuật toán đều nhận kết quả ở đầu vào, xử lý và cho kết
quả cuối cùng

Tính hiệu quả
Khối lượng tính toán, không gian và thời gian được thi hành
là yếu tố quyết định để đánh giá, lựa chọn thuật toán giải
quyết vấn đề.

Tính tổng quát
Thuật toán phải áp dụng cho một họ bài toán
23
3.4 Thuật giải
Mở rộng hai tiêu chuẩn của thuật toán:
Tính xác định và tính đúng đắn được mở rộng để chấp
nhận các cách giải cho kết quả tốt, gần đúng nhưng ít
phức tạp và hiệu quả.
Các cách giải chấp nhận được nhưng không hoàn toàn đáp
ứng đầy đủ các tiêu chuẩn của thuật toán thường được
gọi là các thuật giải.