Giáo án lớp 9 môn Tin học - Chương 1: Ngôn ngữ lập trình và giải thuật

Chương 1: NGÔN NGỮ LẬP TRÌNH & GIẢI THUẬT
I/- Ngôn ngữ lập trình:
1)-Khái niệm:
	Con người liên lạc với nhau thông qua ngôn ngữ, tạo ra các mẫu từ ngữ và âm thanh. Ngôn ngữ lập trình cũng tương tự như vậy, đó là một tập từ ngữ và ký hiệu cho phép lập trình viên hoặc người dùng có thể giao tiếp với máy tính. Ngôn ngữ lập trình cũng có các luật được gọi là cú pháp(syntax) để đảm bảo ngôn ngữ đó được vận dụng một cách chính xác.
2)-Phân loại:
	Có hàng trăm loại NNLT khác nhau, mỗi loại NN đều có cú pháp riêng của nó. Một số NN thì được phát triển để dùng trên các loại máy tính chuyên biệt, một số NN khác thì do sự thành công của nó đã trở thành chuẩn và được áp dụng trên đa số các máy tính. NNLT có thể được phân chia làm 3 loại chính: NN máy, hợp ngữ và NN cấp cao.
a)- Ngôn ngữ máy:
	NN máy (mã máy) là NN nền tảng của bộ vi xử lý. Các chương trình được viết trong tất cả các loại NN khác cuối cùng đều được chuyển thành NN máy trước khi chương trình đó được thi hành.
	Lợi điểm của chương trình được viết bằng NN máy là lập trình viên có thể điều khiển máy tính trực tiếp và đạt được chính xác điều mình muốn làm.
	Bất lợi của NN máy là thông thường sẽ mất rất nhiều thời gian để viết hoặc bảo trì, rất khó đọc, theo dõi để tìm lỗi. Thêm vào đó, bởi vì chương trình được viết bằng tập lệnh phụ thuộc vào bộ vi xử lý nên chương trình chỉ chạy được trên những máy tính có cùng bộ vi xử lý mà thôi. NN máy cũng được gọi là NN cấp thấp (low level language).
b)- Hợp ngữ:
	Hợp ngữ được phát triển nhằm giúp các lập trình viên dễ nhớ các chỉ thị của chương trình hơn. Hợp ngữ tương tự như NN máy nhưng lại sử dụng các ký hiệu gợi nhớ để biểu diễn cho các mã lệnh của máy.
	Các chương trình hợp ngữ được chuyển sang mã máy thông qua một chương trình đặc biệt gọi là trình biên dịch (Assembler).
c)- Ngôn ngữ cấp cao:
	Ngôn ngữ cấp cao gần gũi hơn với ý niệm NN mà hầu hết mọi người điều biết, nó bao gồm các danh từ, động từ, ký hiệu toán học, liên hệ và thao tác luận lý. Các yếu tố này có thể được phối hợp, liên kết với nhau tạo thành một hình thức của câu. Chính vì những đặc điểm này, các lập trình viên dễ dàng đọc và dễ học NN cấp cao hơn so với NN máy hoặc hợp ngữ. Một lợi điểm quan trọng là NN cấp cao thông thường không phụ thuộc vào máy tính, nghĩa là các chương trình viết bằng NN cấp cao có thể chạy trên các loại máy tính khác nhau.
3/- Trình biên dịch:
	Mọi chương trình được viết bằng các NN không phải là NN máy cuối cùng đều phải được chuyển sang NN máy trước khi được thi hành. Việc dịch một chương trình viết bằng NN cấp cao sang NN máy do một chương trình đặc biệt đảm nhận gọi là chương trình dịch. Chương trình dịch sẽ chuyển đổi toàn bộ chương trình sang mã máy. Chương trình NN cấp cao được chuyển đổi gọi là chương trình nguồn (source program) và chương trình NN máy được tạo ra được gọi là chương trình đích.
II/- Giải thuật:
1)- Khái niệm giải thuật:
Thuật toán là một hệ thống chặt chẽ và rõ ràng các qui tắc nhằm xác định một dãy các thao tác trên những đối tượng, sao cho sau một số hữu hạn bước thực hiện các thao tác này, ta thu được kết quả mong muốn.
2)- Các đặt trưng của giải thuật:
Đại lượng vào(input): Mỗi giải thuật có thể có một hoặc nhiều đại lượng vào thường gọi là dữ liệu vào.
Đại lượng ra (output): Khi giải thuật kết thúc thì tuỳ theo chức năng mà giải thuật đảm nhận ta có thể thu được một số đại lượng ra (dữ liệu ra) xác định. 
Tính kết thúc: Một thuật toán phải kết thúc sau một số hữu hạn thao tác.
Tính rõ ràng: Từng thao tác của thuật toán phải rõ ràng không mập mờ.
Tính phổ dụng: Cùng giải quyết một yêu cầu, thuật toán nào sử dụng được rộng rãi hơn, tổng quát hơn thì tính phổ dụng cao hơn.
Tính hiệu quả: Cùng giải quyết một yêu cầu, thuật toán nào tốn kém ít hơn về số lượng thao tác, về vùng nhớ, về thời gian,...thì tính hiệu quả cao hơn.
3)- Cách thức diễn tả giải thuật:
Để biểu diễn thuật toán ta thường dùng hai phương pháp sau:
a)- Phương pháp liệt kê từng thao tác:
Phương pháp này chỉ ra từng bước cụ thể để thực hiện giải quyết bài toán.
Các thao tác cơ bản gồm:
Bắt đầu
Thông báo yêu cầu
Nhận giá trị ban đầu
Gán giá trị (lưu giá trị vào một tên biến nào đấy)
Thực hiện các phép toán số học, logic
Kiểm tra điều kiện để khẳng định điều kiện này Đúng hay Sai
Chuyển không điều kiện, chuyển có điều kiện đến thao tác khác.
Lặp lại từ thao tác nào đấy.
Kết thúc.
Ví dụ: Dùng pháp liệt kê từng bước để diễn tả thuật toán giải phương trình bậc hai:
 ax2 + bx + c = 0
B1. Yêu cầu cho biết giá trị của 3 hệ số a, b, c
B2. Nếu a = 0 thì
	+ Yêu cầu đầu vào không đảm bảo
	+ Kết thúc thuật toán
B3. Nếu a # 0 thì
	+ Tính giá trị D = b*b - 4*a*c
	+ Nếu D>0 thì 
	. Phương trình có hai nghiệm phân biệt x1 và x2
	. Giá trị của hai nghiệm được tính theo công thức sau:
	x1 = (-b-sqrt(D))/2*a 	(sqrt là hàm lấy căn bậc hai)
	x2 = (-b+sqrt(D))/2*a
	. Kết thúc thuật toán
	+ Nếu D = 0 thì
	. Phương trình có nghiệm kép x0
	. Giá trị của nghiệm kép là : x0 = -b/2*a
	. Kết thúc thuật toán
	+ Nếu D<0 thì
	. Phương trình vô nghiệm
	. Kết thúc thuật toán
c)- Phương pháp sơ đồ khối:
Phương pháp này dùng các hình để thể hiện các thao tác, ghi các thao tác vào giữa hình và dùng các mũi tên chỉ thao tác tiếp theo, tạo thành một sơ đồ biểu diễn thuật toán. Thường dùng các hình sau:
	+ Hình Elíp đại diện cho khối bắt đầu và kết thúc
+ Hình chữ nhật đại diện cho khối thao tác
	+ Hình thoi đại diện cho khối điều kiện
Ví dụ: Dùng pháp sơ đồ khối để diễn tả thuật toán giải phương trình bậc hai: ax2 + bx + c = 0
Begin
Input: a,b,c
a=0
D=b*b-4*a*c
Không phải ptb2
D>0
D=0
Pt vô nghiệm
Pt có nghiệm kép
Pt có 2 nghiệm phân biệt
X0= -b/2*a
X12= (-b +- sqrt(D))/2*a
End.
Đ
S
Đ
S
Đ
S