Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Cao đẳng - Đại học Báo cáo thực tập-phương pháp dạy học tin...

Tài liệu Báo cáo thực tập-phương pháp dạy học tin

.PDF
19
180
60

Mô tả:

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
- Xem thêm -

Tài liệu liên quan