PHƯƠNG PHÁP DẠY HỌC TIN
TIN HỌC TRONG TRƯỜNG PT
HỌC PHẦN 1 – 5 ĐVHT (75 TIẾT)
PHẦN CƠ BẢN
Lê Đức Long
Email:
[email protected];
[email protected]
Tp. Hồ Chí Minh, 10/2006
NỘI DUNG MÔN TIN HỌC
CUNG CẤP KHÁI NIỆM CƠ BẢN
VỀ TIN HỌC
Vấn đề 1: Khái niệm về Tin học
Vấn đề 2: Dữ liệu và thông tin
Vấn đề 3: Biểu diễn thông tin trong MT
Vấn đề 4: Các thành phần của PC
Nội dung môn Tin học
Chương trình Tin học trường PT
THỰC HÀNH SƯ PHẠM
THẢO LUẬN NHÓM
NỘI DUNG MÔN TIN HỌC
GÓP PHẦN PHÁT TRIỂN TƯ DUY
THUẬT TOÁN
Vấn đề 1: Vấn đề - bài toán
Vấn đề 2: Giải quyết bài toán trên máy tính
Vấn đề 3: Thuật toán - biểu diễn thuật toán
1
NỘI DUNG MÔN TIN HỌC
RÈN LUYỆN KỸ NĂNG LẬP TRÌNH
MÁY TÍNH VỚI NNLT BẬC CAO
Vấn đề 1: Mô hình hóa bài toán
Vấn đề 2: Rèn luyện khả năng phân tích bài toán
Vấn đề 3: Kỹ năng lập trình máy tính
NỘI DUNG MÔN TIN HỌC
DẠY HỌC CƠ SỞ DỮ LIỆU - HỆ
DBMS ACCESS
NỘI DUNG MÔN TIN HỌC
DẠY HỌC HĐH VÀ MỘT SỐ ỨNG
DỤNG
Vấn đề 1: Hệ điều hành - chức năng của HĐH
Vấn đề 2: Soạn thảo văn bản bằng Word
Vấn đề 3: Mạng máy tính - Internet
Vấn đề 4: Một số ứng dụng khác
NỘI DUNG MÔN TIN HỌC
Các điểm lưu ý - đề xuất …
Vấn đề 1: CSDL và hệ CSDL
Vấn đề 2: Cơ sở dữ liệu quan hệ
Vấn đề 3: Hệ quản trị CSDL MS Access
2
Thông tin - Dữ liệu – Tin học
Đầu vào
DỮ LIỆU
NỘI DUNG MÔN TIN HỌC
CUNG CẤP KHÁI NIỆM CƠ BẢN
VỀ TIN HỌC
Vấn đề 1: Khái niệm về Tin học
Vấn đề 2: Dữ liệu và thông tin
Vấn đề 3: Biểu diễn dữ liệu trong MT
Vấn đề 4: Các thành phần của PC
Personal Computer
o (PC)/Microcomputer
o Nhanh hơn PC 50-1.500 lần
o Phục vụ nghiên cứu là chính
o VD:Earth Simulator (NEC,
5104 CPUs, 35.600 GF)
PC
Super
Mini
Mainframe
Laptop Computer
Handheld Computer
o
Pocket PC,Palm, Mobile
devices
Laptop
• Thu nhận phân loại, lưu trữ
• Tính toán, thống kê
• Hỏi đáp, cập nhật, truy tìm
• Dự báo
Đầu ra
THÔNG TIN
Tin học là một ngành khoa học chuyên xử lý dữ liệu và xuất ra thông tin
một cách tự động, dựa trên công cụ là máy tính điện tử.
1970 - cuối 70: Computer Science
1980 - cuối 80: Informatique
1990 - cuối 90: Information Technology (IT)
2000 – nay: Information and Communication Technology (ICT)
Phân loại máy tính điện tử
Minicomputer
o Nhanh hơn PC 3-10 lần
Mainframe
o Nhanh hơn PC 10-40 lần
Supercomputer
Máy tính xử lý
Handheld
CÁC THÀNH PHẦN CƠ BẢN
CỦA MÁY TÍNH PC
Gồm 4 thành phần chính:
1.Bộ xử lý trung tâm – CPU (Central processing unit)
CU ALU Reg
2.Bộ nhớ (Main Memory)
3.Các thiết bị nhập/ xuất (I/O devices)
CPU
_ Màn hình (monitor)
_ Bàn phím (keyboard)
Tb Nhập
Tb Xuất
i t )
_ Má
Máy iin ((printer)
Bnhớ chính
_ Con chuột (mouse)
_ Máy quét (scanner)
_ Máy đọc thẻ từ, đọc mã vạch, …
BNHỚ PHỤ
_...
4.Thiết bị lưu trữ (Backing Storages)
Cấu trúc của máy PC
_ Đĩa từ : đĩa cứng, đĩa mềm (hard disk, floppy disk)
_ Đĩa quang: CD ROM, CD-R, DVDs,…
3
CÁC THÀNH PHẦN CƠ BẢN
CỦA MÁY TÍNH PC
Các dòng CPU i386SX,
486DX4, Pentium IV của
Intel
MỘT SỐ THIẾT BỊ NGOẠI VI
Barcode Reader
Scanner
Màn hình màu SVGA
Printer
Bàn phím và
Con chuột chuẩn
Modem
Camera
Hình dáng của RAM
MỘT SỐ THIẾT BỊ LƯU TRỮ
Dung lượng
Đĩa mềm 3 ½ inch: 1.44 MB
Đĩa cứng: 10 - 80GB …
Đĩa CDROM: 200 - 700MB
Đĩa DVD: 2GB – 15GB
Light pen
NIC
Mô hình cấu trúc cơ bản của
máy tính
(Thiết bị ngoại vi)
(Thiết bị nhập/xuất)
(ROM RAM)
(ROM,
(Thiết bị nhớ phụ)
((Thiết bịị ngoại
g ạ vi khác))
(Bus hệ thống)
4
Bộ nhớ đệm (cache)
Computer memory
Bộ nhớ được sử dụng để lưu trữ
chương trình, dữ liệu.
Bao gồm
o Bộ nhớ đệm (cache)
FDD, HDD, FLASH DRIVE
o Bộ nhớ chính (main memory)
ộ nhớ ngoài
g
(
y or external
(auxiliary
o Bộ
RAM
memory)
Bộ nhớ nào càng “gần” CPU thì
tốc độ và giá thành chế tạo càng
cao
Đặt giữa CPU và bộ nhớ chính
Tốc độ rất cao
Dung lượng nhỏ
Mục đích: Tăng tốc độ trao đổi
thông tin giữa CPU và RAM
Được chia thành nhiều mức
o Cache L1 (Level 1)
o Cache L2
o Càng gần CPU thì tốc độ càng cao
Ví dụ: CPU Intel Petium III, 256KB Cache
Bật chế độ truy xuất bộ nhớ
trực tiếp
Kiểm tra bộ nhớ của máy tính
• Peak/128 = M
• M * 128 = Y
• So sánh Total với Y
bằng cách Total – Y
Æ Dung lượng bộ nhớ
còn thiếu (nếu cần)
Tổng dung
lượng bộ
nhớ hiện có
-Chọn Control Panel,
Trình System, chọn
tab Hardware, Device
Manager.
Nhấ ké
h ột ở
-Nhấp
kép chuột
mục IDE ATA/ATAPI
controllers, và chọn
mục Advance
Settings.
-Thiết lập chế độ
DMA if available
Lượng bộ nhớ lớn
nhất đã sử dụng
Bật chế độ DMA (Direct Memory Access) tăng tốc toàn hệ thống
5
Tổng kết bộ nhớ máy tính
Hãy thử tìm hiểu …
Cache
Tốc độ tăng dần
d
ect o c d
s
Electronic
disk
Magnetic Disk
Dung lượng
g tăng dần
Main memory (RAM+ROM)
Optical Disk
Magnetic Tape
CÁC THAO TÁC CƠ BẢN VỚI
CHUỘT
-Click mouse
(Nhấp chuột)
Đưa Mouse pointer
đến vị trí cần thiết
và nhấp 1 lần
-Double click
(Nhấp kép chuột)
Đưa Mouse pointer
đến vị trí cần thiết
và nhấp liên tiếp 2
lần (nhấp kép)
CÁC THÀNH PHẦN CƠ BẢN CỦA MÁY TÍNH PC
Màn hình
(Output)
Chuột (Input)
-Point Mouse
(Trỏ chuột)
CPU
Phần cứng
•CPU
•Bộ nhớ chính
•Thiết bị vào/ra
•Thiết bị lưu trữ
Đĩa cứng
(Backing
storage)
Đưa chỉ điểm
chuột đến vị trí nào
đó
-Drag Mouse
(Rê chuột)
Nhấn và giữ nút
chuột trái, rê
chuột từ vị trí này
sang vị trí khác
Bàn phím
(Input)
HT Tin học
Phần mềm
Đĩa mềm
(Backing
storage)
Các chương trình
PM hệ thống
PM ứng dụng
Ngôn ngữ lập trình
Người sử dụng
Quản lý và điều khiển
Hệ thống thông tin thủ công (manual information systems)
Hệ thống thông tin được máy tính hoá (computerised information systems)
6
Nguyên tắc hoạt động của
máy tính PC
THÔNG TIN VÀ DỮ LIỆU
Đầu vào
Máy tính xử lý
THÔNG TIN
DỮ LIỆU
Dữ liệu gốc
Đầu ra
‘a’
Mã hoá
• Biểu diễn số nguyên
• Biểu diễn số thực
• Biểu diễn văn bản
Mã hoá
Dữ liệu mã hoá
Bảng mã ASCII
0110 0001 (97)
Dữ liệu cần xử lý
MÁY TÍNH
XỬ LÝ
Dãy bit
(Mã nhị phân)
MÁY TÍNH XỬ LÝ
đổi ‘a’ thành ‘A’
Thông tin đã xử lý
Thông tin mã hoá
Bảng mã ASCII
0100 0001 (65)
Giải mã
Thông tin kết quả
Giải mã
NGUYÊN LÝ MÃ HOÁ NHỊ PHÂN
‘A’
Mã hoá thông tin trong máy tính
Sơ đồ hoạt động của máy tính khi thực
hiện một lệnh từ thiết bị nhập
Nguyên lý điều khiển bằng chương trình
Nguyên lý lưu trữ chương trình dưới dạng mã nhị phân
Nguyên lý truy cập theo địa chỉ
NGUYÊN LÝ J. VON NEUMANN
MÔN TIN HỌC GÓP PHẦN PHÁT
TRIỂN TƯ DUY THUẬT TOÁN
NỘI DUNG MÔN TIN HỌC
GÓP PHẦN PHÁT TRIỂN TƯ DUY
THUẬT TOÁN
Vấn đề 1: Vấn đề - bài toán
Vấn đề 2: Giải quyết bài toán trên máy tính
Vấn đề 3: Thuật toán - biểu diễn thuật toán
Thể hiện một phương pháp suy nghĩ, làm việc với các khả năng sau:
-Có thể mô tả chính xác quá trình tiến hành một công việc, một
hoạt động nhằm đạt một mục đích nào đó, nói vắn tắt là biết lập
quy trình tiến hành công việc
-Biết cách phân tích một hoạt động thành những thao tác, sắp xếp
chúng
hú theo
th một
ột trình
t ì h tự
t chặt
hặt chẽ
hẽ để giải
iải quyết
ết mục đí
đích
h đã đặt ra
cho hoạt động đó
-Biết cách thực hiện các thao tác theo trình tự đã nêu
-Có thể khái quát trên cơ sở thực hiện một hoạt động cụ thể thành
ra môt quy trình (một thuật toán) để giải quyết một lớp bài toán
tương tự
Với các phân tích đó, ta thấy tư duy thuật toán không những cần cho các học
sinh đang còn học trong các nhà trường, mà còn là một yếu tố quan trọng
giúp cho họ thành đạt khi ra đời, dù cho họ làm công việc gì, từ sản xuất đến
kinh doanh hay quản lý
7
Bài toán trong tin học ?
Vấn đề và bài toán ?
Ví dụ :
1.Chứng minh hằng đẳng thức : (a+b)2 = a2 + 2ab+ b2.
2.Chứng minh rằng gia tốc của chuyển động tròn đều là gia tốc
hướng tâm.
3.Chỉ ra các bước dựng một tam giác với chiều dài các cạnh là
a, b, c cho trước.
4.Với
4 Với số vốn 1,3
1 3 tỉ đồng,
đồng cần đầu tư vào lãnh vực sản xuất nào
để có tiền lời cao nhất ?
-Việc giải quyết vấn đề – bài toán có thể diễn đạt bằng sơ đồ
chung như sau :
A
B
Trong đó :
A
là giả thiết hoặc điều kiện ban đầu
B
là kết luận hoặc mục tiêu cần đạt
là suy luận, giải pháp cần xác định
Bài toán trong tin học ?
Từ Input
làm thế nào
để tìm ra
Output ?
Là việc nào đó ta muốn máy tính thực hiện để
từ dữ liệu đưa vào (Input) tìm được kết quả
đầu ra – thông tin (Output).
Ví dụ :
• Tìm ước số chung lớn nhất của hai số nguyên dương.
Input : Hai số nguyên dương M và N.
Output : Ước số chung lớn nhất của M và N.
• Bài toán xếp loại học tập của một lớp.
Input : Bảng điểm của học sinh trong lớp.
Output : Bảng xếp loại học lực của học sinh.
Giải bài toán trên máy tính ?
Các bạn cần tìm
ra cách giải
của bài toán.
8
Máy tính và GQVĐ– bài toán
Máy tính
Tốc độ: cực nhanh
Độ bền: Liên tục hàng
tháng – hàng năm
Chịu ảnh hưởng của
yếu tố khách quan: ít
Khả năng suy luận gq
vấn đề: Không
Khả năng phản ứng
trước các tình huống
bất ngờ: Không
Ppháp GQVĐ – bài toán trên
máy tính
Con người
Chậm hay rất chậm
Liên tục trong vài ngày giảm dần theo tgian
Có
Tốt
Tốt
Thuật toán ?
Hình dung sơ lược cách máy tính “giải quyết”
một bài toán đơn giản
Hãy tính tổng S của n số nguyên dương đầu
tiên: S = 1+ 2 + 3 + 4 + … + n
Lời giải trên máy tính
B1. Hỏi giá trị của n
B2. Đặt S = 0. Nhớ S = 0. Nhớ i = 1
B3. Nếu số cộng i còn nhỏ hơn hoặc bằng n
(số phép cộng chưa bằng n-1) thì sang B.3.1
Ngược
g ợ lại
ạ sang
g B4
{
o 3.1. Cộng kết quả S đã nhớ với i và nhớ kết quả
mới
o 3.2. Tăng số i lên 1 đơn vị
o 3.3. Trở về B3
B4. Kết quả tính chính là số S đã nhớ
B5. Kết thúc
9
Thuật toán ?
Từ thuật toán (Algorithm) xuất phát từ tên một nhà toán
học người Trung Á là Muhammad ibn Musa alKhwarizmi, thường gọi là al’Khwarizmi. Ông là tác giả một
cuốn sách về số học, trong đó ông đã dùng phương pháp
mô tả rất rõ ràng, mạch lạc cách giải những bài toán. Sau
này, phương pháp mô tả cách giải toán của ông đã được
xem là một chuẩn mực và được nhiều nhà toán học khác
tuân theo. Từ algorithm ra đời dựa theo cách phiên âm tên
của
ủ ông.
He was the author of al-Kitāb al-mukhtaṣar fī ḥisāb al-jabr wa-lmuqābala, the first book on the systematic solution of linear and
quadratic equations. Consequently he is considered to be the father of
algebra, a title he shares with Diophantus. The word algebra is derived
from al-jabr, one of the two operations used to solve quadratic
equations, as described in his book. Algoritmi de numero Indorum,
the Latin translation of his other major work on the Indian numerals,
introduced the positional number system and the number zero to the
Western world in the 12th century. The words algorism and algorithm
stem from Algoritmi, the Latinization of his name.His name is also the
origin of the Spanish word guarismo, meaning digit.
Muḥammad ibn Mūsā alKhwārizmī (Arabic: محمد بن موسى
)الخوارزميwas a Persian
mathematician, astronomer,
astrologer and geographer. He
was born around 780, in either
Khwarizm or Baghdad, and died
around 850.
Tính xác định
Giả sử khi nhận một lớp học mới, Ban Giám hiệu yêu cầu giáo viên chủ nhiệm chọn
lớp trưởng mới theo các bước sau :
1. Lập danh sách tất các học sinh trong lớp.
2. Sắp thứ tự danh sách học sinh.
3. Chọn học sinh đứng đầu danh sách để làm lớp trưởng.
Khi nhận được thông báo này, giáo viên chắc chắn sẽ rất bối rối vì không hiểu
là trong danh sách học sinh cần có những thông tin gì? Danh sách chỉ cần họ
tên, hay cần
ầ thêm ngày tháng năm sinh? Có cần
ầ thêm điểm
ể trung bình không?
Yêu cầu 2 lại càng gây nhiều thắc mắc. Cần phải sắp xếp danh sách theo chiều
tăng dần hoặc giảm dần ? Sắp theo chỉ tiêu gì ? Theo tên, theo ngày tháng năm
sinh hay theo điểm trung bình chung, ...Giả sử sắp theo điểm trung bình thì nếu
có hai học sinh cùng điểm trung bình thì học sinh nào sẽ sắp trước, học sinh nào
sẽ sắp sau ? ...
Hướng dẫn ở trên vi phạm tính chất "không mập mờ" của thuật toán. Nghĩa là,
có quá nhiều thông tin còn thiếu để làm cho các bước 1,2 được hiểu đúng và
hiểu theo một nghĩa duy nhất
Tính chất cơ bản thuật toán
Xác định: rõ ràng, không mập mờ và các bước
giải khả thi có thể thực thi được
o Mập mờ: thiếu thông tin hoặc có nhiều chọn lựa nhưng
không đủ điều kiện để quyết định
o Thực thi được: xét trong điều kiện hiện tại của bài toán
Hữu hạn: số
ố bước là hữu hạn và có tính chất
ấ
dừng Æ dễ bị vi phạm nhất
o Sau một thời gian thi hành hữu hạn thì phải cho kết quả
mong muốn
Đúng: đúng với mọi trường hợp của bài toán
o Tính chất khó đạt nhất
Thuật toán chọn lớp trưởng !!!
1. Lập danh sách tất các học sinh trong lớp theo hai thông tin: Họ và Tên;
Ðiểm trung bình cuối năm.
2. Sắp hạng học sinh theo điểm trung bình theo thứ tự giảm dần (từ điểm cao
đến điểm thấp). Hai học sinh có cùng điểm trung bình sẽ có cùng hạng.
3. Nếu chỉ có một học sinh có hạng nhất thì chọn học sinh đó làm lớp trưởng.
Trường hợp có nhiều học sinh đồng hạng nhất thì chọn học sinh có điểm môn
Toán cao nhất làm lớp trưởng.
Nếu vẫn còn nhiều hơn một học sinh đồng hạng nhất và có cùng điểm môn
Toán cao nhất thì tiến hành bốc thăm.
Ở đây chúng ta cần phân biệt mập mờ và sự chọn lựa có quyết định. Mập mờ
là thiếu thông tin hoặc có nhiều chọn lựa nhưng không đủ điều kiện để quyết
định. Còn chọn lựa có quyết định là hoàn toàn xác định duy nhất trong điều
kiện cụ thể của vấn đề. Chẳng hạn trong vấn đề chọn lớp trưởng ở trên, bước
3 thể hiện một sự lựa chọn có quyết định. Tất nhiên, khi chưa lập danh sách,
chưa xếp hạng theo điểm trung bình thì giáo viên không thể biết được sẽ chọn
lớp trưởng theo cách nào. Nhưng khi đã sắp xong danh sách thì chỉ có một
phương án chọn duy nhất.
10
Xác định = không mập mờ +
thực thi được
Tính "thực thi được" cũng là một tính chất khá hiển nhiên. Rõ
ràng nếu trong "thuật toán" tồn tại một bước không thể thực thi
được thì làm sao ta có được kết quả đúng như ý muốn?
Æ Chú ý đến tính chất này khi giải quyết bài toán trên máy tính - vấn đề
cần giải quyết máy tính phải thực thi được ≠ cách giải quyết bình thường
của con người
Tuy nhiên,
thực thi được
nhiên cần phải hiểu là "thực
được" xét trong điều kiện
hiện tại của bài toán. Chẳng hạn, khi nói "lấy căn bậc hai của một
số âm" là không thể thực thi được nếu miền xác định của bài
toán là số thực, nhưng trong miền số phức thì thao tác "lấy căn
bậc hai của một số âm" là hoàn toàn thực thi được. Tương tự,
nếu ta chỉ đường cho một người đi xe máy đến một bưu điện
nhưng con đường ta chỉ là đường cụt, đường cấm hoặc đường
ngược chiều thì người đi không thể đi đến bưu điện được.
Tính đúng
Tính "đúng" là một tính chất khá hiển nhiên nhưng là tính chất
khó đạt tới nhất. Thực vậy, khi giải quyết một vấn đề-bài toán,
ta luôn luôn mong muốn lời giải của mình sẽ cho kết quả đúng
nhưng không phải lúc nào cũng đạt được.
Mọi học sinh khi làm bài kiểm tra đều muốn bài làm của mình
có đáp số đúng nhưng trên thực tế, trong lớp học chỉ có một
số
ố học sinh nhất
ấ định là có khả năng đưa ra lời giải đúng!
3 tính chất cơ bản của Thuật Toán
Các tính chất của thuật toán rất chặt chẽ và cứng nhắc. Nhưng điều đó cũng có
nghĩa là khả năng giải quyết vấn đề theo kiểu thuật toán cũng bị giới hạn. Sau này,
người ta đã "làm mềm" đi hai tính chất quan trọng của thuật toán là tính xác định và
tính đúng để giải quyết những vấn đề phức tạp hơn mà với các tính chất chặt chẽ của
thuật toán thì không thể giải quyết được. Ðó là thuật giải.
Tính hữu hạn (tính dừng)
Tính "dừng" là tính chất dễ bị vi phạm nhất, thường là do sai sót khi trình bày thuật
toán. Mọi thuật toán đều nhằm thực hiện một công việc nào đó nên sau một thời gian thi
hành hữu hạn thì thuật toán phải cho chúng ta kết quả mong muốn. Khi không thỏa tính
chất này, ta nói rằng "thuật toán" bị lặp vô tận hoặc bị quẩn. Ðể tính tổng các số
nguyên dương lẻ trong khoảng từ 1 đến n ta có thuật toán sau :
B1. Hỏi giá trị của n.
B2. Đặt S = 0, i = 1
B3. Nếu i = n+1 thì sang bước B7, ngược lại sang bước B4
B4. Cộng thêm i vào S
B5. Cộng thêm 2 vào i
B6. Quay lại bước B3.
B7. Tổng cần tìm chính là S. Kết thúc
Ta chú ý đến bước B3. Ở đây ta muốn kết thúc thuật toán khi giá trị của i vượt quá n.
Thay vì viết là "nếu i lớn hơn n" thì ta thay bằng điều kiện "nếu i bằng n+1" vì theo toán
học "i = n+1" thì suy ra "i lớn hơn n". Nhưng điều kiện "i=n+1" không phải lúc nào cũng
đạt được. Vì ban đầu i = 1 là số lẻ, sau mỗi bước, i được tăng thêm 2 nên i luôn là số lẻ.
Nếu n là số chẵn thì n+1 là một số lẻ nên sau một số bước nhất định, i sẽ bằng n+1.
Tuy nhiên, nếu n là một số lẻ thì n+1 là một số chẵn, do i là số lẻ nên dù có qua bao
nhiêu bước đi chăng nữa, i vẫn khác n+1. Trong trường hợp đó, thuật toán trên sẽ bị
quẩn.
Các đặc trưng khác của
thuật toán
Đầu vào và đầu ra (Input/Output) : mọi
thuật toán đều nhận dữ liệu đầu vào, xử
lý nó và cho ra kết quả cuối cùng.
Tính hiệu quả (Effectiveness) : dựa trên
khối lượng tính toán, không gian và thời
gian khi thuật toán được thi hành. Là yếu
tố quyết định để đánh giá, chọn lựa cách
giải quyết vấn đề – bài toán trên thực tế.
Tính tổng quát (Generalliness): áp dụng
được cho mọi trường hợp của bài toán.
11
KẾT LUẬN
Nhập
dữ liệu
Tính toán
xử lý
Xuất
thông tin
Ví dụ về thuật toán
Giải phương trình bậc nhất ax + b =0
1. Yêu cầu cho biết giá trị của a và b
2. Nếu a = 0 thì
2.1. Nếu b = 0 thì phương trình vô định. Kết
thúc
thú thuật
th ật toán.
t á
2.2. Nếu b ≠ 0 thì phương trình vô nghiệm. Kết
thúc thuật toán.
thao tác 1; thao tác 2; …; thao tác N
Liệt kê - Sơ đồ
Nngữ lập trình
Chương trình
Ví dụ về thuật toán
Thuật toán giải phương trình bậc hai ax2+bx+c=0 (a ≠0)
1. Yêu cầu cho biết giá trị của 3 hệ số a, b, c
2. Nếu a=0 thì
2.1. Yêu cầu đầu vào không đảm bảo.
2.2. Kết thúc thuật toán.
3. Trường hợp a khác 0 thì
3.1. Tính giá trị Δ = b2-4ac
3.2. Nếu Δ > 0 thì
3.2.1. Phương trình có hai nghiệm phân biệt x1 và x2
3.2.2. Giá trị của hai nghiệm được tính theo công thức sau
3.2.3. Kết thúc thuật toán.
3.3. Nếu Δ = 0 thì
3.3.1. Phương trình có nghiệm kép x0
3.3.2. Giá trị của nghiệm kép là x0 = -b/2a
3.3.3. Kết thúc thuật toán
3.4. Nếu Δ < 0 thì
3.4.1. Phương trình vô nghiệm.
3.4.2. Kết thúc thuật toán.
⎧
−b+ Δ
⎪ x1 =
⎪
2a
⎨
⎪x = − b − Δ
2
⎪⎩
2a
3. Nếu a ≠ 0 thì phương trình có một
nghiệm duy nhất là x = - b/a. Kết thúc
thuật toán.
Ví dụ về thuật toán
Thuật toán tìm hộp có trọng lượng nặng nhất
Vấn đề : Có n hộp có khối lượng khác nhau và một cái cân dĩa.
Hãy chỉ ra cách cân để tìm được hộp có trọng lượng nặng nhất.
Vấn đề này là thể hiện của một bài toán tổng quát : Cho một tập
hợp A hữu hạn và một thứ tự toàn phần trên A. Hãy xây dựng
thuật toán tìm phần tử lớn nhất của A.
A
Ý tưởng:
• Nếu có 1 hộp Æ hộp đó là nặng nhất
• Nếu có từ 2 hộp trở lên:
• Chọn 2 hộp bất kỳ đưa lên bàn cân Æ giữ lại hộp nặng
• Thực hiện cứ thế cho đến khi không còn hộp nào
• Hộp cuối cùng còn lại trên bàn cân là hộp nặng nhất
12
Lời giải trên máy tính = thuật
toán
1. Nếu chỉ có 1 hộp (n=1) thì
1.1. Hộp đó chính là hộp nặng nhất.
1.2. Kết thúc thuật toán.
2. Ngược lại nếu có từ hai hộp trở lên (n>1)
2.1. Chọn hai hộp bất kỳ và đặt lên bàn cân.
2.2.
2 2 Giữ lại hộp nặng hơn,
hơn cất hộp nhẹ hơn sang chỗ khác.
khác
3. Nếu còn hộp chưa được cân thực hiện các bước sau, nếu
không còn hộp nào nữa, sang bước 5.
3.1. Chọn một hộp bất kỳ và để lên dĩa cân còn trống.
3.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn sang chỗ khác.
4. Trở lại bước 3.
5. Hộp còn lại trên cân chính là hộp nặng nhất. Kết thúc.
Thuật giải ?
Có nhiều bài toán cho đến nay vẫn chưa tìm ra được một
cách giải theo kiểu thuật toán và cũng không biết có
thuật toán hay không ? (Bài toán tìm số nguyên tố lớn
nhất)
Có nhiều bài toán đã có thuật toán để giải nhưng không
chấp nhận được vì thời gian giải theo thuật toán đó là
quá lớn (Bài toán tháp Hà Nội)
Có những
giải
hữ bài toán
t á được
đ
iải theo
th những
hữ cách
á h giải
iải vii
phạm thuật toán nhưng vẫn chấp nhận được.
Mở rộng hai tiêu chuẩn của thuật toán : tính xác định và tính đú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.
Một trong những thuật giải thường được đề cập đến trong khoa học trí tuệ
nhân tạo là các cách giải theo kiểu Heuristic (Hơ rís tíc).
Thuật giải ?
Ví dụ 2: Bài toán đổ nước
Ví dụ 1 : Thuật giải nấu cơm
{Gạo, củi}
Nấu cơm :
–Vo gạ
gạo
–Chuẩn bị lửa
–Nấu, canh giờ
–Kết thúc
{Nồi cơm chín}
Thuật giải ?
TÍNH ĐÚNG
Có hai bình đựng nước là B5 có dung tích 5lít , B8 có
dung tích 8lít. Hãy chỉ ra cách đong để có được hai lít
nước. Các thao tác có thể thực hiện được là :
o Hứng đầy nước vào bình B5 hoặc B8.
o Đổ hết nước trong một bình.
o Đổ nước từ bình này sang bình khác cho đến lúc bình
kia đầy.
Thuật giải :
Đổ đầy nước vào bình B5 (B5=5) .
Đổ hết nước từ bình B5 sang bình B8 (B5=0, B8=5).
Đổ đầy nước bình B5 (B5=5, B8=5).
Đổ nước từ bình B5 cho đến khi B8 đầy (B5=2, B8=8).
TÍNH XÁC ĐỊNH VÀ TÍNH ĐÚNG
13
THUẬT GIẢI HEURISTIC
Thuật giải Heuristic là một sự mở rộng khái
niệm thuật toán. Nó thể hiện cách giải bài toán
với các đặc tính sau :
o Thường tìm được lời giải tốt (nhưng
không chắc là lời giải tốt nhất)
o Giải bài toán theo thuật giải Heuristic
thường dễ dàng và nhanh chóng đưa ra
kết quả hơn so với giải thuật tối ưu, vì
vậy chi phí thấp hơn.
o Thuật giải Heuristic thường thể hiện khá
tự nhiên, gần gũi với cách suy nghĩ và
hành động của con người.
Ví dụ minh họa
Bài toán tìm đường đi ngắn nhất –
Ứng dụng nguyên lý Greedy
Bài toán : Bài toán người bán hàng.
Một nhân viên phân phối hàng cho một công ty được
giao nhiệm vụ phải giao hàng cho các đại lý của công
ty, sau đó trở về công ty. Vấn đề của người nhân viên
là
à làm
à sao đi giao hàng
à cho tất
ấ cả
ả đại lý
ý mà
à không
ô tiêu
ê
quá số tiền đổ xăng mà công ty cấp cho mỗi ngày Æ
Yêu cầu bài toán là làm sao tìm được hành trình ngắn nhất
có thể được.
Tất nhiên ta có thể giải bài toán này bằng cách liệt kê
tất cả con đường có thể đi, tính chiều dài của mỗi con
đường đó rồi tìm con đường có chiều dài ngắn nhất.
Tuy nhiên, cách giải này lại có độ phức tạp n! (tổng số
hành trình có thể có là n!). Do đó, khi số đại lý tăng thì
số con đường phải xét sẽ tăng lên rất nhanh.
Xây dựng thuật giải Heuristic
Có nhiều phương pháp để xây dựng một thuật giải Heuristic, trong đó
người ta thường dựa vào một số nguyên lý cơ sở như sau:
Nguyên lý vét cạn thông minh :
Trong một bài toán tìm kiếm nào đó, khi không gian tìm kiếm lớn, ta thường tìm
cách giới hạn lại không gian tìm kiếm hoặc thực hiện một kiểu dò tìm đặc biệt
dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu.
Nguyên lý tham lam (Greedy):
Lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của bài toán để làm tiêu chuẩn chọn
lựa hành động cho phạm vi cục bộ của
từng giai đoạn)) trong quá
ủ từng bước (hay
(
trình tìm kiếm lời giải.
Nguyên lý thứ tự :
Thực hiện hành động dựa trên một cấu trúc thứ tự hợp lý của không gian khảo
sát nhằm nhanh chóng đạt được một lời giải tốt.
Hàm Heuristic:
Trong việc xây dựng các thuật giải Heuristic, người ta thường dùng các hàm
Heuristic. Ðó là các hàm đánh giá thô, giá trị của hàm phụ thuộc vào trạng thái
hiện tại của bài toán tại mỗi bước giải. Nhờ giá trị này, ta có thể chọn được cách
hành động tương đối hợp lý trong từng bước của thuật giải.
Ý tưởng của thuật giải
Một cách giải đơn giản và thường cho kết
quả tương đối tốt là dùng một thuật giải
Heuristic ứng dụng nguyên lý Greedy. Tư
tưởng của thuật giải như sau :
1. Từ điểm khởi đầu, ta liệt kê tất cả quãng
đường từ điểm xuất phát cho đến n đại lý rồi
chọn đi theo con đường ngắn nhất.
2. Khi đã đi đến một đại lý, chọn đi đến đại lý kế
tiếp cũng theo nguyên tắc trên. Nghĩa là liệt kê
tất cả con đường từ đại lý ta đang đứng đến
những đại lý chưa đi đến. Chọn con đường
ngắn nhất. Lặp lại quá trình này cho đến lúc
không còn đại lý nào để đi
14
THUẬT TOÁN VÀ THUẬT GIẢI
Mô phỏng ý tưởng
2
1
Thuật toán (Algorithm) là một dãy hữu hạn các thao tác
không mập mờ và khả thi, được sắp xếp theo một trình
tự xác định, sao cho các quá trình thực hiện dãy thao tác
đó phải dừng và cho kết quả như mong muốn
3 đặc trưng cơ bản của thuật toán:
2
3
7
5
o Tính xác định: các thao tác không mập mờ và khả thi
o Tính hữu hạn: số hữu hạn các thao tác và phải dừng
o Tính đúng đắn:
ắ cho kết
ế quả
ả như mong muốn
ố
2
3
4
3 đặc trưng phụ khác:
1
(H): 15
Thuật giải Heuristic thực hiện
o Đầu vào - đầu ra
o Tính hiệu quả
o Tính tổng quát
Thuật giải
Thuật toán
MỞ RỘNG TÍNH ĐÚNG,
TÍNH XÁC ĐỊNH
≠
1Æ2Æ5Æ3Æ4Æ1
Kết quả chính xác mong đợi
Biểu diễn thuật toán
) Cách 1: Dùng ngôn ngữ tự nhiên
) Cách 2: Dùng lưu đồ / Vẽ sơ đồ khối
) Cách 3: Dùng mã giả
Bằng ngôn ngữ tự nhiên
(liệt kê)
Trong cách biểu diễn thuật toán theo ngôn ngữ tự nhiên,
người ta sử dụng ngôn ngữ thường ngày để liệt kê các
bước của thuật toán (Các ví dụ ở phần trước đều sử
dụng ngôn ngữ tự nhiên). Phương pháp biểu diễn này
không yêu cầu người viết thuật toán cũng như người đọc
thuật
tắc. Tuy
biểu diễn
th ật toán
t á phải
hải nắm
ắ các
á quy tắ
T vậy,
ậ cách
á h biể
diễ
này thường dài dòng, không thể hiện rõ cấu trúc của
thuật toán, đôi lúc gây hiểu lầm hoặc khó hiểu cho người
đọc. Gần như không có một quy tắc cố định nào trong
việc thể hiện thuật toán bằng ngôn ngữ tự nhiên.
Tuy vậy, để dễ đọc, ta nên viết các bước con lùi vào bên
phải và đánh số bước theo quy tắc phân cấp như 1, 1.1,
1.1.1, ...
15
Ví dụ về thuật toán
Giải phương trình bậc nhất ax + b =0
1. Yêu cầu cho biết giá trị của a và b
2. Nếu a = 0 thì
2.1. Nếu b = 0 thì phương trình vô định. Kết
thúc thuật toán.
2.2. Nếu b ≠ 0 thì phương trình vô nghiệm. Kết
thúc thuật toán.
3. Nếu a ≠ 0 thì phương trình có một nghiệm
duy nhất là x = - b/a. Kết thúc thuật toán.
Các kí hiệu biểu diễn trong
sơ đồ
Bằng sơ đồ khối/ lưu đồ
Lưu đồ hay sơ đồ khối là một công cụ trực quan để
diễn đạt các thuật toán.
Biểu diễn thuật toán bằng lưu đồ sẽ giúp người đọc
theo dõi được sự phân cấp các trường hợp và quá trình
xử lý của thuật toán.
Phương pháp lưu đồ thường được dùng trong những
ậ toán có tính rắc rối,, khó theo dõi được
ợ q
quá trình
thuật
xử lý .
Để biểu diễn thuật toán theo sơ đồ khối, ta phải phân
biệt hai loại thao tác. Một thao tác là thao tác chọn lựa
dựa theo một điều kiện nào đó. Chẳng hạn : thao tác
"nếu a = b thì thực hiện thao tác B2, ngược lại thực hiện
B4" là thao tác chọn lựa. Các thao tác còn lại không
thuộc loại chọn lựa được xếp vào loại hành động.
Chẳng hạn, "Chọn một hộp bất kỳ và để lên dĩa cân còn
trống." là một thao tác thuộc loại hành động.
Ví dụ minh họa
16
Các bước xây dựng
thuật toán
Bằng mã giả
Vay mượn các cú pháp của một ngôn ngữ lập trình nào đó để
thể hiện thuật toán (thường dùng NNLT Pascal để diễn tả).
Dùng mã giả vừa vận dụng được các khái niệm trong ngôn
ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt được
nội dung thuật toán, tuy nhiên là trong mã giả vẫn dùng một
phần
hầ ngôn
ô ngữ
ữ tự
t nhiên.
hiê
Ví dụ : (các từ in đậm là sử dụng từ khóa của NNLT Pascal)
Nhập a, b
If a = 0 then
If b = 0 then xuất kết quả ‘Pt vô định’. Kết thúc
Else xuất kết quả ‘Pt vô nghiệm’. Kết thúc
Else xuất kết quả x =-b/a. Kết thúc
Xác định bài toán :
- Input
- Output
Hình thành ý tưởng chính để giải quyết
bài toán, lưu ý xác định điểm dừng của
thuật toán.
Xây dựng thuật toán bằng 1 trong 2 cách:
- Liệt kê (ngôn ngữ tự nhiên)
- Vẽ sơ đồ
Mô phỏng để kiểm tra tính đúng đắn.
Ví dụ minh hoạ
Xác định bài toán: Thuật toán tìm số lớn nhất
Input: Số nguyên dương N và dãy N số nguyên
a1, a2, …, aN (ai với i : 1→N).
Output: Số lớn nhất (Max) của dãy số.
Mô phỏng ý tưởng
Quả này
Quả này
mới lớn nhất
Ồ!
Tìm
Quả
ra quả
này
lớn
lớn
nhất
hơnrồi!
lớn nhất
Ý tưởng:
t ở
- Đặt giá trị Max = a1.
- Lần lượt cho i đi từ 2 đến N, so sánh giá trị ai với giá trị
Max, nếu ai > Max thì Max nhận giá trị mới là ai.
- Max là giá trị lớn nhất cần tìm
MAX
17
Biểu diễn thuật toán
B1
Cách 1: Dùng ngôn ngữ tự nhiên
Bước 1: Nhập N và dãy a1,a2…, aN;
Bước 2: Max ← a1; i ← 2;
Bước 3: Nếu i > N thì đưa ra giá trị Max
rồi kết thúc;
Bước 4: Nếu ai > Max thì Max ← ai;
Bước 5: i ← i+1 rồi quay lại B3.
B2
NỘI DUNG MÔN TIN HỌC
B3
RÈN LUYỆN KỸ NĂNG LẬP TRÌNH
MÁY TÍNH VỚI NNLT BẬC CAO
B4
B5
Cách 2: Dùng lưu đồ
MỘT SUY NGHĨ VỀ DẠY HỌC
LẬP TRÌNH
Vấn đề 1: Trình bày khái niệm
o Cần trình bày các khái niệm sao cho thật dễ hiểu, dễ tiếp
thu và dễ ứng dụng nhất đối với hs
Vấn đề 2: Xây dựng ví dụ minh họa
o Cần xây dựng hệ thống các ví dụ
o Cho phép minh họa tốt nhất có thể có các k/niệm
o Giúp hs tiếp thu được các kỹ năng, kinh nghiệm lập trình
của chính gv
Vấn đề 3: Biên soạn bài tập
• Cần biên soạn hệ thống các bài tập giúp hs tự rèn luyện tốt
các kỹ năng được mong đợi của môn học
Vấn đề 4: Trình bày yêu cầu của bài tập lập trình
o Cần trình bày yêu cầu của bài tập lập trình thật rõ ràng dễ
hiểu đối với hs. Hạn chế tối đa việc hs không thực hiện
được bài tập là do không hiểu hay hiểu sai đề
Vấn đề 5: Trình bày cách giải/bài giải của bài tập lập trình
o Cần trình bày bài giải/ cách giải thật rõ ràng, súc tích để hs
dễ tiếp thu nhất có thể có
Vấn đề 1: Mô hình hóa bài toán
Vấn đề 2: Rèn luyện khả năng phân tích bài toán
Vấn đề 3: Kỹ năng lập trình máy tính
DẠY HỌC LẬP TRÌNH VỚI AML
Tác giả: Nguyễn Tiến Huy, ĐHKHTN Tp.HCM
AML bao gồm hệ thống các sơ đồ được sử dụng như
một công cụ hỗ trợ giảng dạy về lập trình
AML hỗ trợ giáo viên:
o Soạn thảo, trình bày các bài tập lập trình một cách rõ ràng, súc
tích và trực quan
o Soạn thảo, trình bày bài giải một cách ngắn gọn, đơn giản và độc
lập với NNLT
AML hỗ trợ học sinh:
o Tiếp nhận và hiểu rõ các yêu cầu của bài tập lập trình của gv
o Tiếp thu dễ dàng các bài giải của gv
o Bước đầu rèn luyện tư duy lập trình theo thiết kế và lập trình theo
yêu cầu với các bài tập lập trình Æ đây chính là các tư duy nền
tảng cho việc phát triển các phần mềm ứng dụng sau này
18
DẠY HỌC LẬP TRÌNH VỚI AML
Hệ thống các sơ đồ
KỸ THUẬT LẬP TRÌNH CƠ BẢN
XEM TÀI LiỆU GT AML
o Nhóm 1:
Sơ đồ phục vụ cho việc mô tả yêu cầu: DFD
(Data Flow Diagram)
o Nhóm
Nhó 2:
2
Sơ đồ mô tả kiến trúc tổ chức các thành phần
của chương trình/phần mềm: MAD (Module
Architecture Diagram)
Sơ đồ mô tả hoạt động phối hợp giữa các
thành phần của chương trình/ phần mềm: FCD
(Function Collaboration Diagram)
BÀI TOÁN
ĐẶC TẢ YÊU CẦU Æ PHÂN TÍCH Æ THIẾT KẾ Æ CÀI ĐẶT
CHƯƠNG TRÌNH
THẾ GIỚI THỰC vs VIỆC THỰC HIỆN TRÊN MÁY TÍNH
THẾ GIỚI THỰC
TIN HỌC HÓA
VIỆC THỰC HIỆN TRÊN
MÁY TÍNH
19