DẠY CHƯƠNG 1 TIN HỌC 10
BÁO CÁO
Biên soạn: NCT, Bộ môn Tin học
Chương trình bồi dưỡng sách giáo khoa tin học 10
Các trường THPT Hà Nội.


Nội dung báo cáo
Phần 1. Tổng quan về chương IMục đích: Tìm hiểu tổng thể nội dung từng bài, từng mục.Chốt lại những nội dung chính của từng bài, dự đoán dụng ý tác giả (tức SGK) là gì?
Phần 2. Đề xuất ba phương án để chọn lựa cách giảng
Phương án một: Dạy theo đúng trình tự các section (§) trong SGK và thời lượng trong SGV.
Phương án hai: Dạy theo định hướng chú trọng nội dung khó.
Phương án ba: Dạy cho đối tượng chuyên và cận chuyên
Phần 3. Vài kinh nghiệm giảng dạy phần thuật toán
Phần 4. Thảo luận trao đổi ý kiến
Chương 1: MỘT SỐ KHÁI NIỆM CƠ BẢN VỀ TIN HỌC

Mục đích của việc giới thiệu tổng quan
Tìm hiểu tổng thể nội dung từng bài, từng mục
Chốt lại những nội dung chính của từng bài, dự đoán dụng ý tác giả.
PHẦN I: TỔNG QUAN VỀ CHƯƠNG 1
§1. Tin học là một ngành khoa học
Cấu trúc nội dung của § 1
1. Sự hình thành và phát triển của tin học
2. Đặc tính và vai trò của máy tính
Bài đọc thêm liên quan, Các § liên quan
Bài đọc thêm "Tin học có phải là ngành KH", tr 45, SGV)
§ 8 (trang 53 - Những ứng dụng của tin học);
§ 9 (trang 58 - Tin học và xã hội)
Bài đọc thêm số hai: Lịch sử phát triển của các kỹ thuật tính toán. (Trang 33: các mốc lịch sử chính)
Câu hỏi và bài tập: 5 câu hỏi lý thuyết (trang 6)
Chốt lại nội dung § 1
Nhập môn tin học sao cho ấn tượng thông qua hai việc:
Khẳng định Tin học là một ngành khoa học
Máy tính cực kỳ quan trọng và cần thiết vì các ưu điểm của nó.(Tham khảo thêm tr.33)
§ 2. Thông tin và dữ liệu
Cấu trúc nội dung của § 2
1. Khái niệm thông tin và dữ liệu
2. Đơn vị đo thông tin
3. Các dạng thông tin
4. Mã hóa thông tin
5. Biểu diễn thông tin trong máy tính
Nguyên lý mã hóa nhị phân trong khung tr.13
Bài đọc thêm 1: Biểu diễn hình ảnh và âm thanh
Bài thực hành 1: Làm quen với thông tin và mã hóa thông tin
Câu hỏi và bài tập: 5 câu hỏi lý thuyết tr.17
Bài đọc thêm 2: Biểu diễn số trong các hệ đếm khác nhau 
Chốt lại nội dung § 2
Biểu diễn thông tin trong máy tính: Mã hóa, Hệ nhị phân (có nguyên lý mã hóa nhị phân trong khung),
Các hệ đếm khác, các dạng thông tin (số, phi số).
§ 3. Giới thiệu về máy tính
Cấu trúc của § 3
1. Khái niệm hệ thống tin học
2. Sơ đồ cấu trúc của một máy tính
3. Bộ xử lý trung tâm
4. Bộ nhớ trong
5. Bộ nhớ ngoài
6. Thiết bị vào
7. Thiết bị ra
8. Hoạt động của máy tính
Nguyên lý điều khiển bằng chương trình
Nguyên lý lưu trữ chương trình
Nguyên lý truy cập theo địa chỉ
Nguyên lý Phôn nôi-nam (là 3 nguyên lý trên).
Bài thực hành 2: Làm quen với máy tính
Câu hỏi và bài tập: 6 câu hỏi lý thuyết (trang 28)
Bài đọc thêm 3: Lịch sử phát triển các kỹ thuật tính toán
Các nhà khoa học gắn liền với lịch sử phát triển các kỹ thuật tính toán
Các mốc lịch sử chính trang 31
Chốt lại nội dung § 3

Giới thiệu cấu tạo chung của máy tính và các thành phần của nó được định nghĩa trong các khung. Máy tính gồm 5 thành phần độc lập: Bộ xử lý trung tâm, bộ nhớ trong, bộ nhớ ngoài, thiết bị vào, thiết bị ra.
Ghi nhớ nguyên lý Phôi nôi-man gồm 3 nguyên lý thành phần: điều khiển bởi chương trình, lưu trữ chương trình, truy cập theo địa chỉ (dữ liệu và lệnh).
§ 4. Bài toán và thuật toán
4.1. Khái niệm bài toán
Khái niệm dẫn dắt, nhấn mạnh việc xác định rõ input và output của bài toán, chưa cần quan tâm đến cách giải quyết bài toán. Đó là "bước xác định bài toán" - bước đầu tiên trong các bước giải một bài toán trên máy tính.
Bốn ví dụ để tìm input và output cho 4 bài toán sau đây:
Ví dụ 1: Tìm UCLN của hai số nguyên dương
Ví dụ 2: Tìm nghiệm PTB2
Ví dụ 3: Kiểm tra tính nguyên tố của một số nguyên dương
Ví dụ 4: Xếp loại học lực của học sinh một lớp
§ 4. Bài toán và thuật toán (trang 2)
4.2. Khái niệm thuật toánKhái niệm thuật toán chốt lại trong khung một cách nôm na là: Thuật toán là việc con người hướng dẫn cho máy tính cách để nó có thể tìm ra output mong muốn từ input đã cho. Trả lời câu hỏi "làm như thế nào?“Phải đảm bảo: hữu hạn thao tác, theo một trình tự, nguyên tắc nhất định.
Ví dụ : Thuật toán tìm giá trị lớn nhất của một dãy số nguyên
Theo SGK, gồm 4 công việc chính
Xác định bài toán
Ý tưởng thuật toán
Thuật toán: Liệt kê từng bước và Sơ đồ khối.
Ví dụ mô phỏng
Rút ra các tính chất: tính dừng, tính xác định, tính đúng đắn
§ 4. Bài toán và thuật toán (trang 3)
4.3. Một số ví dụ về thuật toán
Ví dụ 1: Kiểm tra tính nguyên tố của một số nguyên dương
Ví dụ 2: Thuật toán sắp xếp bằng tráo đổi
Ví dụ 3: Thuật toán tìm kiếm tuần tự
Ví dụ 4: Thuật toán tìm kiếm nhị phân
Tất cả các ví dụ trên, từng ví dụ đều có 4 công việc chính như trên.
Câu hỏi và bài tập (trang 44): 1,2,3 : Lý thuyết
Tiếp theo có 4 bài tập (chương I chỉ duy nhất bài 4 là có bài tập)
4. Xây dựng thuật toán tìm giá trị nhỏ nhất của một dãy số
5. Xây dựng thuật toán tìm nghiệm của PTB2 tổng quát
6. Xây dựng thuật toán sắp xếp giảm dần một dãy n số nguyên
7. Xây dựng thuật toán đếm xem có bao nhiêu số hạng có giá trị 0 trong một dãy n số
4. Chốt lại nội dung § 4
Quá trình xây dựng thuật toán giải một bài toán gồm ba công việc chính:
Việc 1: Xác định bài toán (xác định input, output)
Việc 2: Ý tưởng thuật toán (là sự lập luận tự nhiên hoặc trình bầy một cơ sở có lý về cách giả quyết bài toán. Cơ sở toán học thì càng tốt)
Việc 3: Xây dựng thuật toán.
Việc diễn tả thuật toán thể hiện theo một trong hai cách "từng bước" hoặc "sơ đồ khối" là phần trọng tâm. Sau ba bước trên cần có ví dụ mô phỏng.
Bài học này đề cập đến 4 bài toán cơ bản và 3 thuật toán kinh điển.
Tìm giá trị MAX, MIN của một dãy số
Tìm để đếm một giá trị cụ thể trong một dãy số
Kiểm tra tính chất nguyên tố của một số nguyên dương
Giải PTB2 tổng quát
Thuật toán tìm kiếm tuần tự
Thuật toán tìm kiếm nhị phân
Thuật toán sắp xếp tăng (giảm) bằng tráo đổi (kiểu nổi bọt từ trên xuống)
§ 5. Ngôn ngữ lập trình
Cấu trúc nội dung của § 5
ĐVĐ: Ngôn ngữ để diễn tả thuật toán trong máy tính là ngôn ngữ lập trình. Kết quả của một diễn tả như vậy là một chương trình.
5.1. Ngôn ngữ máy
Ngôn ngữ máy
chương trình dịch.
Ngôn ngữ lập trình khác
5.2. Hợp ngữ
5.3. Ngôn ngữ bậc cao
Ngôn ngữ lập trình càng xa ngôn ngữ máy thì càng gần (thân thiện) với người lập trình vì nó viết bằng ngôn ngữ tự nhiên của con người.
Những ngôn ngữ lập trình thân thiện với người lập trình gọi là ngôn ngữ lập trình bậc cao. Ngôn ngữ lập trình bậc cao cũng cần tới chương trình dịch.
Câu hỏi và bài tập (trang 46) Gồm 3 câu hỏi lý thuyết đơn giản.

Chốt lại nội dung của § 5
Cung cấp liên tiếp các khái niệm "ngôn ngữ lập trình, chương trình, hợp ngữ, chương trình dịch, ngôn ngữ lập trình bậc cao" .
SKG viết ngắn gọn, nên theo đúng như SGK.
§ 6. Giải một bài toán trên máy tính
ĐVĐ: Giải một bài toán trên máy tính gồm 5 bước, trong đó bước 2 chính là nội dung của quá trình xây dựng thuật toán (ở bài 4).
6.1. Xác định bài toán: Tìm hiểu bài toán để phân biệt input, output, yêu cầu bài toán, lựa chọn thuật toán,
6.2. Thiết kế thuật toán
a) Lựa chọn thuật toán
b) Diễn tả thuật toán
Việc 1: Xác định input/output;
Việc 2: Ý tưởng thuật toán;
Việc 3: Diễn tả thuật toán bằng liệt kê từng bước hoặc sơ đồ khối
Và tiếp theo cần có ví dụ mô phỏng cho thuật toán
Ví dụ: Xây dựng thuật toán tìm UCLN của hai số nguyên dương M và N
6. Giải một bài toán trên máy tính (trang 2)
6.3. Viết chương trìnhĐề cập đến những vấn đề sau (mà chưa cần cụ thể trên một ngôn ngữ lập trình nào)
Lựa chọn việc tổ chức dữ liệu
Lựa chọn ngôn ngữ lập trình (tuân theo đúng cú pháp, sửa lỗi nhờ chương trình dịch)
6.4. Hiệu chỉnh: Kiểm nghiệm tính đúng đắn của chương trình bằng một bộ dữ liệu kiểm thử đầy đủ. Từ đó điều chỉnh cho chương trình đúng đắn
6.5. Viết tài liệu: Ghi chép lại tất cả các bước thực hiện từ 1 đến 4 để tích lũy thành một tài liệu có thể sử dụng cho sau này.
Các bước 6.1 đến 6.5 là một quá trình tuyến tính nhưng có thể có bước quay lại.
Câu hỏi và bài tập (trang 51)
1, 2 : Lý thuyết
3. Xây dựng thuật toán giải phương trình ax + b = 0
Chốt lại nội dung của § 6
§ 6 là một cơ hội để tiếp tục nội dung của bài 4 (ba công việc chính của quá trình xây dựng thuật toán giải một bài toán).
§ 6, bổ sung thêm ví dụ tìm UCLN của hai số nguyên dương và bài tập giải PTB1
Tổng quan về 5 bước bước giải một thuật toán trên máy tính, tuy nhiên trọng tâm vẫn là bước 2, tức là quay về nội dung của § 4.
§ 7. Phần mềm máy tính
Cấu trúc nội dung của § 7
7.1. Phần mềm hệ thống Là chương trình tạo ra môi trường làm việc cho các phần mềm khác
7.2. Phần mềm ứng dụng Là các phần mềm MT phục vụ c/v có tính nghiệp vụ hoặc để giải trí
Trong phần mềm ứng dụng, tuy không rõ rệt trong phân loại, có những phần mềm được gọi là phần mềm công cụ (hỗ trợ các phần mềm khác), phần mềm tiện ích (hỗ trợ thao tác truy cập, bảo vệ thông tin)
Câu hỏi bài tập (trang 52): gồm 2 câu hỏi lý thuyết
Chốt lại nội dung § 7
Cung cấp một cách liên tiếp và ngắn gọn các khái niệm: phần mềm hệ thống; phần mềm ứng dụng
Khi giảng cũng nên theo đúng như SGK.
§ 8. Những ứng dụng của tin học
Cấu trúc nội dung của § 8
8.1. Giải các bài toán KHKT
8.2. Hỗ trợ quản lý
8.3. Tự động hóa và điều khiển
8.4. Truyền thông
8.5. Soạn thảo, in ấn, lưu trữ, văn phòng
8.6. Trí tuệ nhân tạo
8.7. Giáo dục
8.8. Giải trí
Câu hỏi và bài tập (trang 57)
Gồm 4 câu hỏi lý thuyết
Chốt lại nội dung của § 8Kể tên và đánh giá những lĩnh vực ứng dụng to lớn của ngành tin học nhờ có máy tính với chương trình và các phần mềm hữu ích được cài đặt bên trong chúng.
§ 9. Tin học và xã hội
Cấu trúc nội dung của §9
9.1. Ảnh hưởng của Tin học đối với sự phát triển của xã hộiTin học tác động vào các lĩnh vực của đời sống xã hội, tạo ra các phương thức hoạt động mới. Cần phải chú ý: không chỉ chú trọng việc khai thác những phần mềm ứng dụng.
9.2. Xã hội tin học hóa (Kể tên các hoạt động của đời sống xã hội có sự tham gia tích cực của tin học)
9.3. Văn hóa và pháp luật trong xã hội tin học hóa (Giáo dục việc sử dụng thông tin dữ liệu theo hướng tích cực đúng quy định luật pháp để bảo vệ lợi ích cá nhân và cộng đồng)
Câu hỏi và bài tập (trang 60): Ba câu hỏi lý thuyết
Chốt lại nội dung § 9Những nhận xét về sự ảnh hưởng của tin học trong đời sống xã hội trên những lĩnh vực, hoạt động cụ thể. Giáo dục về phẩm chất con người lao động mới trong xã hội văn minh trí tuệ (văn minh thông tin)
Phương án một: Dạy theo đúng trình tự các section (§) trong SGK và trung thành với thời lượng của chúng trong SGV.
Phương án hai: Dạy theo định hướng chú trọng nội dung khó
Phương án ba: Dạy cho đối tượng chuyên và cận chuyên.
PHẦN 2: ĐỀ XUẤT 3 PHƯƠNG ÁN CHỌN LỰA CÁCH GIẢNG DẠY
Phương án một: Dạy theo đúng trình tự các section trong SGK và thời lượng trong SGV
Ưu điểm của phương án một:
Tuân thủ đúng SGK và SGV để dễ dàng thực hiện đúng cơ sở pháp lý về chuẩn kiến thức.
Tận dụng trình tự logic của các section trong SGK
Phân chia thời lượng (SGV trang 25)
Đánh giá sự logic của trình tự các § trong SGK
Nhược điểm của phương án một:
Phụ thuộc nhiều vào SGK, không nhìn thấy tính chủ động, linh hoạt trong việc tổ chức lựa chọn các mạch kiến thức.
Ít có điều kiện tập trung vào những vấn đề khó dạy mà lại có dung quan trọng.
Phân bổ thời lượng chương 1 trong SGV
Logic trong trình tự kiến thức SGK
Phương án hai: Dạy theo định hướng chú trọng nội dung khó.
Những căn cứ để lựa chọn phương án hai:
Căn cứ thứ nhất: Thực hiện đúng tinh thần hướng dẫn của SGV.Trang 16, SGV viết "Không nên đồng nhất tuyệt đối hoàn toàn SGK và bài giảng của GV. Để tăng cường trong việc giảng dạy, GV cần chủ động biên soạn giáo án, sắp xếp bài giảng sao cho hợp lý tùy thuộc vào học lực của từng lớp, miễn là truyền tải đủ nội dung đã viết trong SGK, đảm bảo đúng chuẩn kiến thức đã quy định trong chương trình".
Căn cứ thứ hai: Có phương án phân chia lại các mạch nột dung kiến thức thành 3 phần đảm bảo logic trong trình tự kiến thức và đảm bảo chuẩn kiến thức
Căn cứ thứ ba: Có phương án phân bổ lại thời lượng hợp lý cho ba phần kiến thức đã được phân chia
Phân chia chương 1 thành ba phần nội dung
Phần Một: Nhập môn tin học, đề cập đến các vấn đề sau đây:
Tin học là một ngành khoa học (bài 1)
Những ứng dụng của tin học (bài 8)
Tin học và xã hội (bài 9)
Giới thiệu về máy tính (bài 3)
Phần Hai: Biểu diễn thông tin trong máy tính, tập trung vào (bài 2) và hai bài đọc thêm (1 và 2), đề cập đến những vấn đề sau đây:
Khái niệm thông tin và dữ liệu.
Đơn vị đo thông tin và các bội của thông tin.
Các dạng thông tin.
Mã hóa và vấn đề biểu diễn thông tin trong máy tính.
Phần Ba: Thuật toán , đề cập tới những vấn đề sau đây
Bài toán và thuật toán: khái niệm bài toán, khái niệm thuật toán, quá trình xây dựng thuật toán giải một bài toán (bài 4)
Năm bước giải một bài toán trên máy tính, mà trọng tâm vẫn là bước 2 (bài 6)
Các nội dung trên liên quan đến các vấn đề sau:
Ngôn ngữ lập trình (bài 5)
Phần mềm máy tính (bài 7)
=> Nặng nhất là phần hai và phần ba (bài 2, bài 4 và bài 5)
Phân chia thời lượng cho ba phần nội dung
Ưu và nhược điểm của phương án hai
Ưu điểm của phương án hai:
Chủ động, sáng tạo trong soạn giáo án và bài giảng.
Tập trung vào được phần khó dạy, là trọng tâm của chương.
Tiết kiệm thời gian cũng như tận dụng quỹ thời gian vào những mạch kiến thức quan trọng.
Nhược điểm của phương án hai:
Đòi hỏi GV phải sáng tạo và linh hoạt trong soạn bài giảng và cân đối thời lượng.
Đòi hỏi có cách đặt vấn đề hợp lý trong việc ghép nối các section lại với nhau.
Nói ngắn gọn, cái khó thứ nhì là dạy về phần biểu diễn dữ liệu. Cái khó nhất vẫn là dạy một số ví dụ về thuật toán cho học sinh hiểu, trong đó phải kể tới việc giảng về sơ đồ khối.
PHẦN 3: VÀI KINH NGHIỆM GIẢNG DẠY PHẦN THUẬT TOÁN
1. Trước khi bắt đầu, cho HS thống nhất về cách hiểu đối với một số thuật ngữ, ký hiệu, mà GV sẽ diễn đạt.
Ví dụ:
Phân biệt i và a[i];
Thuật ngữ đổi chỗ hay tráo đổi hai biến;
Thay vì nói biến i nhận các giá trị là 1,2,3,..., 10, ta sẽ nói biến i nhận giá trị từ 1 đến 10. Để thật ngắn gọn ta rất hay dùng cách nói "i chạy từ 1 đến 10“;
Các thuật ngữ khác nếu HS có thể hiểu nhầm cũng cần thống nhất cách hiểu từ đầu.
2. Lựa chọn một tiến trình tiếp cận thuật toán sao cho tự nhiên
3. Phương pháp Tiếp cận thô khi vẽ sơ đồ khối cho thuật toán
Sơ đồ khối có một vài vòng lặp và đặc biệt là sơ đồ khối có hai vòng lặp lồng nhau thường gây ra sự lúng túng khi giảng giải và đây là vấn đề mà HS khó hiểu nhất.
Thuật ngữ "thô" là để chỉ một bài toán con đã được "đóng gói", nghĩa là tạm thời chưa quan tâm đến việc giải quyết nó như thế nào.
Phương pháp tiếp cận từ thô là vẽ sơ đồ khối của thuật toán theo từng giai đoạn:
Ở giai đoạn đầu, sơ đồ khối có những bài toán con đóng gói, HS sẽ tiếp cận dễ dàng hơn so với việc tiếp cận ngay tới một sơ đồ đầy đủ.
Sơ đồ khối sẽ được chi tiết dần (do đó giảm tính thô sơ)
Ở giai đoạn cuối cùng ta thu được sơ đồ khối đầy đủ của thuật toán.
Hai cách Tiếp cận thô để vẽ sơ đồ khối cho thuật toán
Làm thô từ ngoài vào: Giai đoạn một ta vẽ sơ đồ ở mức tổng thể, thô sơ mà không cần chi tiết.
Làm thô từ trong ra: Giai đoạn một, ta chỉ vẽ sơ đồ khối của các vòng lặp trong cùng, các biến bên ngoài vòng lặp được xem như có một số giá trị cố định nào đó.
Khi làm thô cần tới sơ đồ phụ. Sơ đồ phụ là sơ đồ chi tiết thuật toán của một bài toán con.
Thường thì các bài toán trong trong SGK chỉ đòi hỏi giải quyết với hai giai đoạn: làm thô và chi tiết
Ví dụ về phương pháp làm thô từ ngoài vào: Xây dựng thuật toán kiểm tra tính chất nguyên tố của một số nguyên dương.
Việc 1: Ví dụ mô phỏng
0 & 1 : không là số nguyên tố;
Chỉ có một số nguyên tố duy nhất là số chẵn, đó là số 2. Các số nguyên tố đếu là số lẻ.
2, 3 : là số nguyên tố ;
6: không là số nguyên tố vì nó có hai ước thực sự là 2 và 3
7: là số nguyên tố vì nó không có ước thực sự nào
Nhận xét :Ước thực sự lớn nhất của một số nguyên dương cùng lắm là bằng một nửa của nó. Nếu chính xác tuyệt đối (như SGK) thì ước thực sự lớn nhất của một số là phần nguyên của căn bậc hai của số đó. Tức là nếu k là ước thực sự lớn nhất của a thì k <= [sqrt(a)].
Xây dựng thuật toán kiểm tra tính chất nguyên tố của một số nguyên dương (trang 2)
Việc 2: Ý tưởng (SGK):
Nếu N = 1 thì N không là số nguyên tố
Nếu 1Nếu N>= 4 và N không có ước số trong phạm vi từ 2 đến k (k là ước thực sự lớn nhất của N) thì N là số nguyên tố.
Việc 3: Thuật toán
a) Liệt kê từng bước (như SGK)
b) Sơ đồ khối
Xây dựng thuật toán kiểm tra tính chất nguyên tố của một số nguyên dương (trang 3)
Ta gọi P là bài toán con “Kiểm tra N có phải là số nguyên tố hay không khi N>=4"
Ý tưởng thuật toán giải P: Ta dùng biến i để thử tất cả những giá trị có thể là ước thực sự của N. Suy ra i có giá trị bé nhất là 2 và lớn nhất cùng lắm là [sqrt(N)]. Nói cách khác, trong quá trình i "chạy" từ 2 đến [sqrt(N)], nếu có một giá trị nào đó của i là ước thực sự của N thì chứng tỏ N không là số nguyên tố và ta kết thúc thuật toán.
Lưu ý thay vì kiểm tra "A có đúng không" ta kiểm tra "A có sai không". Nếu A không sai tức là A đúng. Từ đó nếu trong quá trình i chạy nói trên mà thuật toán không dừng để thông báo N không là số nguyên tố thì chứng tỏ khi i chạy xong, N phải là số nguyên tố.
Xây dựng thuật toán kiểm tra tính chất nguyên tố của một số nguyên dương (trang 4), làm thô từ ngoài vào
Ví dụ về phương pháp làm thô từ trong ra: Xây dựng thuật toán sắp xếp bằng tráo đổi dãy N số a1, ..., aN
Xét dãy cần sắp xếp dãy ban đầu a1, a2, ..., aN
Bài toán con P: Xét dãy con từ phần tử thứ nhất đến phần tử thứ M nào đó (M<=N), tức là dãy:  a1, a2, ..., aM (M<=N), Yêu cầu làm đúng một nhiệm vụ, đó là chuyển phần tử có giá trị lớn nhất về cuối dãy.
Thuật toán sắp xếp bằng tráo đổi dãy N số a1, ..., aN (trang 2)
Ý tưởng thuật toán giải P: Giảng bằng lời
là ý tưởng nổi bọt. Giả sử dãy trên dựng đứng, mỗi một phần tử xem như một bọt nước. Trọng lượng của một bọt nước thứ i là giá trị của phần tử a[i].
Ta cho i chạy từ đầu dãy đến M, nếu tại một vị trí i nào đó mà a[i] > a[i+1], tức là nếu phần tử bên trên nặng hơn phần tử bên dưới thì chứng tỏ nó phải chìm xuống và phần tử bên dưới nó phải nổi lên trên, nói cách khác phải có lệnh đổi chỗ a[i] và a[i+1].
Bây giờ nếu tăng i lên thì đương nhiên i "nhìn vào" phần tử nặng hơn vừa chìm xuống.
Việc so sánh a[i] với phần tử bên dưới nữa là a[i+1] lại được lặp lại và công việc đổi chỗ có thể xảy ra nếu a[i] nặng hơn a[i+1]. Rồi i lại tiếp tục "đi xuống".
Điều này chứng tỏ trong quá trình i đi dần xuống , quá trình so sánh và đổi chỗ sẽ luôn luôn đảm bảo i nhìn vào các phần tử nặng hơn. Khi i dừng lại ở M thì chắc chắn phần tử nặng nhất của dãy đã được chuyển về cuối dãy, vậy yêu của bài toán P được giải quyết.
Thuật toán sắp xếp bằng tráo đổi, (trang 3)
Ý tưởng thuật toán giải P: Giảng song song với việc vẽ hình

Thuật toán sắp xếp bằng tráo đổi dãy N số a1, ..., aN (trang 4)
Lưu ý: khi i chạm vào M thì a[i+1] sẽ vô nghĩa (vượt chỉ số), hơn nữa lúc mà i = M-1 thì việc so sánh sẽ vẫn đảm bảo đổi chỗ phần tử gần cuối cùng này (nếu nó nặng hơn) với phần tử cuối cùng. Vậy cho nên i chỉ cần chạy tới M-1 là đủ.
Từ đó điều kiện để dừng lặp là i > M-1.
Ngoài ra, để biểu thị quá trình i chạy từ 1, thì i phải được khởi tạo từ 0.
Thuật toán sắp xếp bằng tráo đổi dãy N số (trang 5)
Cơ sở lý luận của Tiếp cận thô để vẽ sơ đồ khối cho thuật toán
Làm thô từ ngoài vào: tiếp cận bài toán từ trên xuống (top-dowm) tức là nhìn tổng thể bài toán cần giải và phân rã bài toán cần giải thành các bài toán con thô (đóng gói). Tiếp theo ta sẽ xem xét thuật toán cho các bài toán con.
Làm thô từ trong ra: không quan tâm ngay đến việc giải quyết bài toán đã cho mà tìm thuật toán giải những bài toán con trước, do đó đây là phương pháp tiếp cận từ dưới lên (bottom-up). Sau đó đóng gói các bài toán con này trong sơ đồ tổng thể giải quyết bài toán đã cho.
Làm thô từ trong ra thường thực hiện với mục đích xây dựng sẵn các bài toán con đóng gói để dùng cho các bài toán sau này có thể cần tới
HẾT CHƯƠNG 1
Xin cảm ơn