(SKKN HAY NHẤT) sử DỤNG GIẢI THUẬT sắp xếp GIÚP học SINH GIẢI các bài TOÁN TRONG lập TRÌNH THEO ĐỊNH

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ

TRƯỜNG THPT BA ĐÌNH NGA SƠN

SÁNG KIẾN KINH NGHIỆM

SỬ DỤNG GIẢI THUẬT SẮP XẾP

GIÚP HỌC SINH GIẢI CÁC BÀI TOÁN

TRONG LẬP TRÌNH

THEO ĐỊNH HƯỚNG PHÁT TRIỂN NĂNG LỰC

Họ và tên: Vũ Thị Huệ

Chức vụ: Giáo Viên

SKKN thuộc môn: Tin Học

THANH HOÁ, NĂM 2021

UAN VAN CHAT LUONG download : add [email protected]

Mục lục

1. Mở đầu................................................................................................................................................1

1.1 Lý do chọn đề tài...................................................................................................................1

1.2 Mục đích nghiên cứu...........................................................................................................1

1.3 Đối tượng nghiên cứu.........................................................................................................1

1.4 Phương pháp nghiên cứu...................................................................................................1

1.5 Những điểm mới của sáng kiến.....................................................................................2

2. Nội dung sáng kiến kinh nghiệm........................................................................................2

2.1 Cơ sở lý luận của vấn đề...................................................................................................2

2.2 Thực trạng của vấn đề trước khi áp dụng sáng kiến kinh nghiệm................3

2.3 Giải pháp và tổ chức thực hiện.......................................................................................3

2.4 Hiệu quả của đề tài nghiên cứu.....................................................................................19

3 . Kết luận và đề xuất……………………………………..…………………20

3.1 Kết luận…………………….…………..………………..……………...20

3.2 Đề Xuất …………………………………………………….…………..20

Tài liệu tham khảo

Danh mục các đề tài SKKN

Phụ Lục

UAN VAN CHAT LUONG download : add [email protected]

1. Mở đầu

1.1. Lý do chọn đề tài.

Sắp xếp( Sort) hiểu tổng quát là quá trình tuyển lựa, bố trí sắp đặt lại vị trí

các đối tượng dữ liệu theo một trật tự nhất định. Sắp xếp đóng vai trò rất quan

trọng trong cuộc sống nói chung và trong Tin Học nói riêng. Ý nghĩa và công

dụng của sắp xếp là giúp đơn giản hóa việc tìm kiếm các phần tử trong khối dữ

liệu đã được sắp xếp. Thử hình dung xem, một cuốn từ điển, nếu các từ không

được sắp xếp theo một trật tự, sẽ khó khăn như thế nào trong việc tra cứu các từ.

Theo nhà khoa học D.Knuth thì có tới 40% thời gian tính toán của máy tính là

dành cho việc sắp xếp. Như vậy sắp xếp là công việc thường hay sử dụng trong

lập trình, nó cũng là thao tác cơ bản và quan trọng trong xử lý dữ liệu [5] .

Trong quá trình giảng dạy trên lớp cũng như bồi dưỡng cho học sinh mũi

nhọn, tôi luôn phải sử dụng nhiều tới các kỹ thuật sắp xếp để giải các bài toán có

ứng dụng của thuật toán sắp xếp.

Tuy nhiên trên thực tế qua các tài liệu nghiên cứu các tác giả đều chưa tập

hợp tổng hợp các thuật toán cũng như các kỹ thuật cho thuật toán sắp xếp nói

chung đầy đủ nhất, chủ yếu đề cập đến các thuật toán sắp xếp tiêu biểu như nổi

bọt hay sắp xếp nhanh.

Trong đề tài sáng kiến kinh nghiệm lần này tôi mạnh dạn trình bầy về các

thuật toán đến chương trình đề sắp xếp dữ liệu đã được đưa vào bộ nhớ chính.

Tôi đã áp dụng để truyền đạt cho các học sinh của mình, thu được các tiết học

thực sự lý thú và có hiệu quả.

1.2. Mục đích nghiên cứu.

- Mục đích nghiên cứu của sáng kiến này tôi muốn trình bầy làm rõ về các thuật

toán sắp xếp để ứng dụng vào giải các bài toán ở mức độ THPT.

- Nắm vững về cấu trúc cú pháp và hoạt động của các giải thuật sắp xếp .

- Luyện cho học sinh kỹ năng viết, lựa chọn sử dụng các kỹ thuật sắp xếp linh

hoạt khi lập trình

- Học sinh biết vận dụng kiến thức về giải thuật sắp xếp giải quyết các vấn đề

thực tiễn, phát huy những suy nghĩ tích cực, tư duy sáng tạo. Huy động tiềm

năng của học sinh, góp phần hình thành năng lực giải quyết vấn đề cho học sinh.

1.3. Đối tượng nghiên cứu.

- Sử dụng linh hoạt các kỹ thuật của giải thuật sắp xếp dữ liệu khi giải bài toán

trên máy tính trong chương trình phổ thông một cách khoa học và hiệu quả nhất.

1.4. Phương pháp nghiên cứu.

Khi nghiên cứu và áp dụng đề tài này tôi đã sử dụng các phương pháp

nghiên cứu:

- Phương pháp nghiên cứu xây dựng cơ sở lý thuyết, qua các văn bản chủ trương

của Đảng, chính sách pháp luật của nhà nước về giáo dục và đào tạo trong

chương trình phổ thông.

- Phương pháp điều tra khảo sát thực tế, thu thập thông tin và xử lý số liệu. Đảm

bảo tính chính xác của thực trạng, hiệu quả của vấn đề nghiên cứu và rút ra

những kết luận quan trọng.

1

UAN VAN CHAT LUONG download : add [email protected]

- Phương pháp thống kê xử lý dữ liệu phân tích tổng hợp, thu thập thông tin từ

nhiều nguồn tài liệu.

1.5. Những điểm mới của sáng kiến.

- Sáng kiến này đề cập đến những khía cạnh khác nhau của các kỹ thuật sắp xếp

dữ liệu. Từ đó đánh giá thời gian thực thi cũng như dung lượng bộ nhớ cấp phát

của mỗi kỹ thuật sắp xếp. Người lập trình có thể chọn và áp dụng thuật toán sắp

xếp phù hợp với mỗi yêu cầu bài toán và dữ liệu đặt ra.

- So với sáng kiến kinh nghiệm hoàn thành trong năm học 2019- 2020, năm nay

trong sáng kiến này tôi đã nghiên cứu, phân tích, minh họa và trình bầy thêm về

kỹ thuật sắp xếp theo giải thuật chèn và giải thuật sắp xếp bằng đếm phân phối.

Thu được kết quả cao khi áp dụng giải các bài toán phổ thông và trong bồi

dưỡng mũi nhọn.

2. Nội dung sáng kiến kinh nghiệm

2.1. Cơ sở lý luận của sáng kiến kinh nghiệm.

Theo nhà khoa học D.Knuth đã nghiên cứu và chứng minh thì 40% thời

gian tính toán của máy tính là dành cho sắp xếp. Không phải ngẫu nhiên thuật

toán sắp xếp nhanh( Quick Sort) được bình chọn là một trong 10 thuật toán tiêu

biểu của thế kỷ XX [5]. Trong các chương trình giảng dạy Tin Học ở các cấp

học nói chung việc sắp xếp dữ liệu luôn được đề cập, trong Tin Học lớp 10 và

lớp 11 các em học sinh được học từ thuật toán đến chương trình để sắp xếp các

phần tử của mảng theo thứ tự tăng dần hoặc giảm dần là một ví dụ rất bổ ích cho

việc nắm vững các phép xử lý mảng [2]. Tuy nhiên thuật toán sắp xếp chủ đạo

trong sách giáo khoa Tin Học lớp 10 và lớp 11 đưa ra là thuật toán sắp xếp bằng

tráo đổi ( Exchange Sort) hay còn có tên gọi khác là sắp xếp nổi bọt( Bubble

Sort) thích hợp với các bài toán cơ sở có dữ liệu nhỏ [1]. Khi giải các bài toán

với dữ liệu lớn hơn, yêu cầu độ phúc tạp nhỏ, cần thời gian chạy ít hơn, tôi đã

tìm hiểu đến các thuật toán sắp xếp khác nhau để phù hợp cho mỗi bài toán đặt

ra và tôi sẽ trình bầy trong sáng kiến kinh nghiệm này.

Bên cạnh đó, cá nhân tôi nhận thức về tầm quan trọng của việc tăng

cường đổi mới dạy học Bộ giáo dục và đào tạo đã tập trung chỉ đạo thông qua

nghị quyết Hội nghị trung ương 8 khóa XI về việc đổi mới căn bản, toàn diện

giáo dục và đào tạo nêu rõ: ” Tiếp tục đổi mới mạnh mẽ phương pháp dạy học

và học theo phương pháp hiện đại, phát huy tính tích cực, chủ động sáng tạo và

vận dụng kiến thức, kỹ năng của người học, khắc phục lối truyền thụ áp đặt một

chiều, ghi nhớ máy móc. Tập trung dạy cách học, cách nghĩ, khuyến khích tự

học, tạo cơ sở để người học tự cập nhật và đổi mới trí thức, kỹ năng phát triển

năng lực. Chuyển từ học trên lớp sang tổ chức hình thức học tập đa dạng, chú ý

các hoạt động đa dạng, ngoại khóa, nghiên cứu khoa học. Đẩy mạnh ứng dụng

công nghệ thông tin và truyền thông trong dạy học...”

Hiện nay trong các tài liệu về các ngôn ngữ lập trình rất phong phú và đa

dạng. Việc đưa ra hệ thống các bài tập có tính phân bậc để luyện kỹ năng cho

các em hoc sinh giúp các em dễ dàng nắm bắt nội dung của bài học mà còn định

hướng và phát triển tư duy cho các em về khả năng ngôn ngữ lập trình, linh hoạt

2

UAN VAN CHAT LUONG download : add [email protected]