Xem mẫu
- SỞ GIÁO DỤC VÀ ĐÀO TẠO QUẢNG BÌNH
TÀI LIỆU
BỒI DƯỠNG THƯỜNG XUYÊN
DÀNH CHO GIÁO VIÊN THPT
MÔN TIN HỌC
(LƯU HÀNH NỘI BỘ)
NHÓM BIÊN SOẠN
Lê Thủy Thạch
Nguyễn Lê Hải
Quảng Bình, năm 2013
- PHẦN 1.
HƯỚNG DẪN SỬ DỤNG PHẦN MỀM ADOBE CONNECT
Adobe Connect là hệ thống cho phép thực hiện:
- Họp qua web (Web Conference),
- Lớp học ảo (Virtual Classroom),
- Chia sẻ bài giảng điện tử eLearning để học trực tuyến, tạo lớp học và
chương trình học.
Hệ thống Adobe Connect do Cục CNTT, Bộ Giáo dục và Đào tạo thiết lập
và quản lý, có địa chỉ website là http://hop.edu.net.vn. Hiện nay, có nhiều phòng
họp ảo khác nhau, tương ứng phần đuôi của địa chỉ khác nhau. Tại một thời điểm,
tổng số người có thể nối vào hiện nay là 80 concurent user licenses. Để tham gia
một phòng họp hay lớp học, người sử dụng cần biết địa chỉ phòng họp. Thí dụ:
http://hop.edu.net.vn/quangbinh là phòng họp đã được giao cho Sở GD&ĐT
Quảng Bình quyền quản lý.
1. Các tính năng chính
- Phát hình video: người giảng bài.
- Phát tiếng (voice, sound).
- Trình chiếu powerpoint.
- Trình chiếu chia sẻ màn hình các ứng dụng khác.
- Trình chiếu chia sẻ màn hình windows.
- Cửa sổ trao đổi qua gõ phím (Chatting room).
- Thăm dò dư luận, bỏ phiếu (Polling, Vote).
- Bảng trắng để vẽ, viết …
- Truyền tệp (file transfer).
- Cộng tác, làm việc chung.
- Diễn đàn trao đổi.
- Kiểm tra kiến thức bằng thi trắc nghiệm.
2. Ứng dụng của web conference
- Họp giao ban giữa Bộ với các Sở; giữa Sở với các Phòng; giữa Phòng với
các trường quận/huyện.
- Tập huấn phần mềm (có thể chia sẻ màn hình phần mềm cần tập huấn).
- Giảng bài từ xa.
- Chia sẻ bài giảng eLearning.
- Bảo vệ luận án.
- Giao lưu giữa các trường trong và ngoài nước.
- Quảng cáo giới thiệu sản phẩm.
1
- 3. Điều kiện sử dụng:
- Có đường kết nối Internet ADSL.
- Có webcam nếu muốn hiển thị hình ảnh video của mình lên
cho mọi người nhìn thấy.
- Có microphone (có thể tích hợp sẵn ở trong webcam như Logitech
Quickcam).
- Loa máy tính.
- Được thông báo địa chỉ web để họp (Cục CNTT cấp).
4. Các quyền sử dụng:
- Host: làm ông chủ, có đầy đủ quyền điều hành. Người làm host có thể:
+ Cho phép các thành viên đều là presenter như sau:
+ Không cho ai vào nữa (block Incoming Attendees)
+ Không cho khách là gust vào (block Guest Attendees), trong khi các
thành viên khác đã đăng ký vẫn được vào.
Cục CNTT cấp quyền cho người làm host.
- Presenter: Người trình bày, báo cáo viên.
- User: Người sử dụng, đại biểu, người học.
5. Đăng nhập với người sử dụng
- Đăng nhập với vai trò là khách (Enter as a Guest): Hãy gõ tên cá nhân
hoặc tên cơ quan một cách ngắn gọn. Người sử dụng không cần tên và mật khẩu.
- Đăng nhập với vai trò là host: (Enter with your login and password) Khi
quý vị đã được Cục CNTT cấp quyền làm chủ phòng họp (host) thì đăng nhập
bằng cách chọn dòng thứ hai:
2
- Adobe Connect cho phép quản lý đăng nhập:
- Hoặc là vào thẳng
- Hoặc phải được ông chủ phòng họp (host) chấp thuận.
Người làm chủ phòng họp có thể đặt chế độ vào thẳng hoặc phải xin phép
mình.
6. Màn hình đầu tiên
Nháy chuột vào đây để kích hoạt webcam.
3 cách bố trí màn hình có sẵn: Sharing, Discussion và Collaboration
3
- Nút chuyển sang chế độ “chuẩn bị bố trí mặt màn hình”.
Nút khóa không cho ai thay đổi bố trí mặt màn hình.
7. Chọn lựa và điều chỉnh âm thanh
Việc điều chỉnh âm thanh rất quan trọng. Cuộc họp thành công hay không
phụ thuộc đầu tiên vào yếu tố âm thanh.
a) Vỉ âm thanh trên máy tính
- Không nên dùng vỉ âm thanh có sẵn trên máy để bàn vì chất lượng kém, dễ
gây tiếng vọng và nhiễu, ồn.
- Nên dùng vỉ âm thanh của máy tính xách tay có chất lượng tốt hơn.
- Tốt nhất nên mua vỉ âm thanh ngoài, có chất lượng rất tốt. Mua hai loại: vỉ
PCI và cắm USB
b) Điều khiển âm thanh trên màn hình Adobe Connect
chứa các nút điều khiển âm thanh.
Nháy và giữ chuột ở nút này để bật mic phát biểu (Hold
and Talk). Khi nhả chuột ra thì mic không bắt tín hiệu nữa. Khi phát biểu, mức độ
to nhỏ của tín hiệu có thể hiện ở vạch mầu xanh phía dưới. Trong khi nháy chuột
vào nút hình khoá bên cạnh là để bật mic liên tục, tay không cần giữ
chuột khi phát biểu.
Nháy chuột vào nút cho ra hình sau:
4
- Voice off: Tắt hết mic và loa của tất cả mọi người.
Voice on – Multiple Speakers: Mọi người đều có thể nói. Khi này rất dễ bị
rú rít và rất ồn nếu nhiều người cùng nói.
Voice on – One Speaker: Chỉ một người nói.
Nháy chuột phải vào màn hình, sau đó nháy chuột trái vào chữ hiện ra là
Setting để nhìn thấy:
Hãy nháy chuột vào nút hình microphone để có hình ảnh sau:
Hãy chọn nguồn tín hiệu âm thanh, ở đây là
Logitech Microphone Pro 4000.
Điều chỉnh Record volume về tối thiểu.
8. Khắc phục hiện tượng rú rít và tiếng vọng
Để khắc phục hiện tượng loa rú rít và có tiếng vọng, ta thực hiện:
- Nháy chuột chọn chế độ Reduce Echo (giảm tiếng vọng). Điều quan trọng
nhất là đẩy nút Record Volume về chế độ thích hợp, thí dụ ở đây: vặn về gần như
bé nhất vì microphone có độ nhạy cao. Nói thử xem vạch xanh nhấp nháy, không
nên để mức tín hiệu lên cao đến mức có mầu đỏ.
- Điều chỉnh độ nhạy mic về tối thiểu, đủ dùng.
- Nếu chủ động được thì chọn chế độ 1 người nói.
- Khi không phát biểu nên tắt mic. Không dùng chế độ hand-free.
- Không bật loa quá to.
- Dùng thiết bị chuyên dụng có khử tiếng vọng.
- Chọn Low Volume.
Nguyên tắc 1: Mỗi phòng họp chỉ cho khoảng 3-5 người được quyền bật
mic phát biểu (Presenter). Còn lại: tắt hết mic khi họ chỉ là đại biểu (Participant).
Nguyên tắc 2: Chỉ bật mic khi phát biểu để tránh tiếng rú rít và tiếng ồn,
tiếng vọng. Việc các đại biểu tự tắt mic là một việc hơi khó do họ chưa có thói
quen sử dụng.
5
- Microphone: Có thể dùng mic của webcam (rất nhạy), hoặc nối mic ngoài
qua vỉ mạch âm thanh. Khi giáo viên giảng bài qua mạng, nên dùng mic qua vỉ
mạch âm thanh vì mic này có độ nhạy thấp, bớt rú rít. Mic ngoài còn có ưu điểm là
có nút tắt bật ngay ở tay nên dễ điều khiển.
Nối mic ngoài vào máy tính qua bộ chuyển đổi âm thanh USB như đã trình
bày ở trên.
9. Đàm thoại
Nếu điều kiện cho phép, hãy chuyển sang dùng đường âm thanh đàm thoại
(họp qua điện thoại). Quay số 04. 62 78 78 50 và quay tiếp số hiệu phòng họp.
Nếu có thuê bao điện thoại của Viettel thì quay số cước nội vùng là 1900
1563 và quay tiếp số hiệu phòng họp.
Thiết bị để đàm thoại: Dùng điện thoại Panasonic 2373
Điện thoại này có ưu điểm:
- Rẻ tiền.
- Có loa ngoài, đủ để 20 người họp nghe được.
- Có mic nhạy.
- Có nút MUTE tắt mic với đèn báo đỏ.
Lưu ý 1: Nhớ lắp pin để tiếng mic và loa tốt.
Lưu ý 2: Cục CNTT đã chế tạo bộ chuyển đổi, kết nối điện thoại với loa
ngoài và mic ngoài. Đã cấp mẫu cho các Sở để dùng.
10. Chọn video
Lần đầu tiên cắm webcam vào hoặc có nhiều nguồn tín hiệu video, hãy nháy
chuột vào hình webcam để chọn thiết bị camera thích hợp.
Nháy chuột vào nút để kích hoạt webcam.
Về nguyên lý, có thể hiện lên rất nhiều, hằng chục hình video. Mỗi hình
video chiếm dung lượng khoảng 150 Kbps do Adobe Connect dùng công nghệ nén
thành video flash. 4 hình thì cần 600 Kbps.
Nếu nhiều hình quá thì nhìn khó kĩ chi tiết và quan trọng là yêu cầu băng
thông đường truyền cao lên. Tuy nhiên kinh nghiệm cho thấy, nên để 2-4 hình hiện
lên là vừa.
11. Chọn webcam
Webcam phù hợp hiện nay là Logitech Quickcam S5500.
6
- Thiết bị kết nối USB:
Để kết nối các loại camera
khác vào máy tính, nên mua thiết
bị chuyển đổi EasyCap của
Kworld.
Có thể dùng AVerDVD
EZMaker USB2.0
Camera Pan/Titl/Zoom
Ở những phòng họp và lớp học rộng, nếu có điều kiện
kinh phí thì mua camera có tính năng điều khiển tự động,
quay ngang, quay dọc như Sony EVI D70.
7
- Một máy tính có thể nối 2 webcam hay 2 camera, miễn sao máy tính nhận
ra là hai thiết bị USB khác nhau.
Thí dụ có thể dùng 1 cái webcam Logitech + 1 cổng camera nối qua USB
EasyCap.
12. Chia sẻ màn hình. Đây là nơi để chọn:
- Tệp powerpoint để trình chiếu, giảng bài: Nháy vào nút Documents. Rồi
chọn tệp powerpoint từ mục From my computer..
- Chia sẻ màn hình đang làm việc nên rất dễ tổ chức tập huấn các phần mềm.
- Chia sẻ màn hình trang web đang sử dụng.
- Chia sẻ bảng trẳng để vẽ (whiteboard).
Chọn chế độ video
Cần chọn chế độ hình video là High Quality.
8
- Hoặc bấm nhanh vào hình của Camera and Voice để có thể lựa chọn
High-Quality Image. Khi này, hình ảnh có thể chậm, giật nhưng đẹp. Lý do: Khi
ngồi họp, ít cử động, di động nên chọn ảnh đẹp là phù hợp nhất.
Lưu ý: cẩn thận khi chọn camera off vì lúc đó không ai bật được camera.
Kinh nghiệm: Lúc thử nghiệm, có thể cho hết camera bật lên. Nhưng lúc họp
thật, nên bật vài camera (3-4) vì càng bật nhiều, băng thông đường truyền càng đòi
hỏi phải cao.
Muốn xem dung lượng đường truyền đang tiêu tốn bao nhiêu, hãy nháy
chuột vào nút xanh lá cây góc trên bên phải:
Latency: Thời gian trễ.
13. Điều chỉnh kích thước window và bố trí mặt bằng làm việc
Việc bố trí các cửa sổ đang nhìn thấy là ngầm định ban đầu. Tuy nhiên, có
thể dùng chuột để di chuyển vị trí, để co kéo kích thước các cửa sổ. Sau đây là một
số thí dụ khi trình bày báo cáo với powerpoint:
9
- Buổi họp giao ban giữa Bộ GD&ĐT với 63 Sở qua web và qua đàm thoại:
14. Điều khiển powerpoint
Panel bên phải
Tắt mở panel bên phải
để điều khiển bằng tay từng trang trình chiếu.
để cho chạy tự động các trang trình chiếu.
10
- cho phép điều khiển: Phần
trình chiếu powerpoint sẽ chiếm hết màn hình, hoặc Stop trình chiếu, stop chia sẻ
màn hình.
15. Báo hiệu xin ý kiến:
Nháy chuột vào biểu tượng để chọn các
hoạt động báo hiệu ý kiến như:
- Giơ tay xin phát biểu.
- Biểu quyết đồng ý.
- Không đồng ý.
- …
- Hoan hô
16. Thiết kế mặt bằng: Thêm bớt các cửa sổ nghiệp vụ
Nháy chuột vào mục Pod trên hàng Menu, hiện ra danh mục các cửa sổ sẽ
hiện ra trên màn hình.
Hiện ra hoặc tắt di:
Cửa sổ Share để nạp powerpoint, chia sẻ màn
hình
Cửa sổ danh sách người tham gia
Cửa sổ Camera and Voice
Cửa sổ Chat
Cửa sổ Note
Cửa sổ thăm dò dư luận, biểu quyết
Cửa sổ up file lên để chia sẻ
Cửa sổ chia sẻ web link.
Cho phép di chuyển và điều chỉnh kích thước các
cửa sổ hay khoá lại.
11
- 17. Ghi hình để phát lại
Ghi hình để phát lại
18. Sử dụng Adobe Connect với Adobe Presenter
Có thể tải các bài giảng e-Learning được soạn từ Adobe Presenter, Adobe
Captivate lên Adobe Connect, biến Adobe Connect thành lớp học ảo.
Hãy sử dụng Adobe Presenter để Upload bài giảng điện tử lên đây.
12
- PHẦN 2.
KẾT HỢP KỸ THUẬT ĐÁNH DẤU PHẦN TỬ VÀ XỬ LÝ BÍT ĐỂ GIẢI
QUYẾT MỘT SỐ BÀI TOÁN TRONG TIN HỌC
Khi lập trình để giải quyết các bài toán trong tin học, có hai tài nguyên rất
quan trọng đó là: bộ nhớ và thời gian thực hiện chương trình. Trong thực tế, hầu
hết các bài toán cần giải quyết đều có dung lượng dữ liệu vào rất lớn và đòi hỏi
thời gian thực hiện phải nhanh. Ví dụ: Sắp xếp danh sách 20.000 học sinh dự thi
tốt nghiệp THPT tăng dần theo vần ABC; Chụp ảnh biến đổi khí hậu từ vệ tinh và
truyền về trung tâm dự báo thời tiết; Điều khiển máy bay không người lái...
Để khắc phục những hạn chế về bộ nhớ và thời gian thực hiện chương trình
khi giải quyết các bài toán lớn người ta có hai giải pháp đó là: nâng cấp phần cứng
và cải tiến phần mềm
Để nâng cấp phần cứng, người ta thường kết nối nhiều máy tính với nhau để
tăng dung lượng bộ nhớ, đồng thời chia nhiệm vụ xử lý cho nhiều máy tính cùng
xử lý song song. Mặc dù đã được nâng cấp rất nhiều nhưng thực tế bộ nhớ máy
tính và tốc độ xử lý của CPU vẫn có giới hạn của nó. Vì thế, người ta thường kết
hợp nâng cấp phần cứng với cải tiến phần mềm.
Để cải tiến phần mềm, người ta tìm các kỹ thuật mã hóa lưu trữ dữ liệu
nhằm giảm dung lượng nhớ đồng thời cải tiến thuật toán nhằm giảm thời gian thực
hiện chương trình.
Đối với một bài toán trong Tin học thường có rất nhiều thuật toán để giải
quyết. Thông thường, thuật toán giải quyết đơn giản nhất, người lập trình dễ thấy
nhất sẽ là thuật toán mà máy tính phải thực hiện nhiều phép toán nhất, dẫn đến thời
gian để máy thực hiện xong chương trình là rất lớn.
Ngoài ra, một thuật toán trong tin học được xem là tối ưu nếu nó giải quyết
được bài toán khi dữ liệu vào có dung lượng và phạm vi dữ liệu rất lớn.
Khi giảng dạy, người giáo viên thông thường chỉ hướng dẫn để học sinh tìm
được một thuật toán để giải quyết bài toán. Hơn nữa, phạm vi và dung lượng dữ
liệu trong đề bài toán mà giáo viên ra cho học sinh thường là rất hẹp. Do đó, đã
hình thành thói quen của học sinh là không quan tâm đến việc xem xét thời gian
thực hiện của máy tính khi giải quyết bài toán theo thuật toán này.
Trong các kỳ thi học sinh giỏi quốc gia và quốc tế, người ta không chỉ quan
tâm đến tính chính xác của kết quả chương trình mà còn đặc biệt quan tâm đến thời
gian để máy tính thực hiện xong chương trình và cho ra kết quả chính xác. Có
những bài toán người ta chỉ yêu cầu máy tính chạy trong một giây nhưng nếu
13
- không có thuật toán tốt thì có thể máy tính phải chạy hàng giờ vẫn chưa thu được
kết quả.
Phần này nhằm giới thiệu kỹ thuật đánh dấu phần tử kết hợp với kỹ thuật xử
lý bít để mở rộng phạm vi lưu trữ dữ liệu và đồng thời tăng tốc thuật toán của một
số bài toán trong tin học.
Phần này không trình bày sâu về kỹ thuật đánh dấu phần tử mà tập trung
trình bày về kỹ thuật xử lý bít và khai thác sự kết hợp hai kỹ thuật này để nâng cao
tốc độ thuật toán và mở rộng phạm vi dữ liệu của một số bài toán.
Nội dung chính bao gồm 2 phần:
1. Một số vấn đề cơ bản về đánh dấu phần tử và xử lý bít.
2. Kết hợp kỹ thuật đánh dấu phần tử với kỹ thuật xử lý bít để mở rộng
phạm vi dữ liệu và tăng tốc thuật toán khi giải một số bài toán:
+ Bài toán sắp xếp dãy số.
+ Bài toán lọc dữ liệu.
+ Bài toán tìm giao của hai tập hợp.
Đối với mỗi loại bài toán, sau khi phát biểu bài toán, xin giới thiệu một thuật
toán giải quyết dễ phát hiện nhất, lập trình theo thuật toán đó; phân tích độ phức
tạp của thuật toán; đề xuất thuật toán cải tiến bằng việc ứng dụng kỹ thuật đánh
dấu phần tử để tăng tốc độ thuật toán; sau đó đề xuất thuật toán ứng dụng kỹ thuật
xử lý bít để mở rộng phạm vi dữ liệu; Cuối cùng, đề tài giới thiệu chương trình
tương ứng với thuật toán cải tiến.
NỘI DUNG
I. Một số vấn đề cơ bản về đánh dấu phần tử và xử lý bít.
1.1. Đánh dấu phần tử
Có thể hiểu nôm na đánh dấu phần tử là việc duyệt qua một phần tử đồng
thời thiết lập một trạng thái mới cho phần tử đó.
Trong tin học, một dãy các phần tử thường được lưu trong một mảng một
chiều A.
Để đánh dấu một phần tử trong dãy A, ta khai báo một mảng A gồm nhiều
phần tử. Thực hiện gán giá trị ban đầu cho các phần tử là 0 với ý nghĩa là chưa có
phần tử nào được chọn. Khi duyệt qua phần tử thứ i, nếu muốn đánh dấu phần tử
thứ i, ta thực hiện lệnh gán A[i] := 1 theo nghĩa i là phần tử đã được đánh dấu.
1.2. Xử lý bít
1.2.1. Khái niệm
14
- Trong cấu trúc lưu trữ của máy tính, mỗi byte bao gồm 8 bít được đánh số từ
phải sang trái, từ 0 đến 7. Mỗi bít có thể nhận một trong hai trạng thái đóng hoặc
mở mạch điện. Tương ứng với trạng thái đóng, ta mã hóa là 1 ngược lại ta mã hóa
là 0.
Trong ngôn ngữ lập trình, thông thường đơn vị lưu trữ thông tin nhỏ nhất là
byte. Việc kết hợp 2 byte (hoặc nhiều hơn) để lưu trữ sẽ cho ta một kiểu mới.
Mọi số nguyên trong máy đều biểu diễn dưới dạng nhị phân, ví dụ số 5 được
biểu diễn như sau:
Chỉ số bít: 7 6 5 4 3 2 1
Giá trị bít: 0 0 0 0 1 0 1
1.2.2. Các phép toán cơ bản trên bít
- Phép đảo bít (Phép toán NOT): Phép toán NOT là phép toán một ngôi. Giải sử
bít i có giá trị là 0 thì NOT i sẽ cho giá trị là 1
- Phép cộng bít (Phép toán OR): Phép toán OR là phép toán hai ngôi. Giả sử i
và j là hai bít có giá trị (0,1) thì phép toán i OR j sẽ cho giá trị tương ứng như bảng
dưới đây:
i j i OR j
0 0 0
1 0 1
0 1 1
1 1 1
Như vậy, i OR j cho kết quả là 0 khi và chỉ khi cả hai bít i và j đều có giá trị 0.
- Phép nhân bít (Phép toán AND): Phép toán AND là phép toán hai ngôi. Giả
sử i và j là hai bít có giá trị (0,1) thì phép toán i AND j sẽ cho giá trị tương ứng
như bảng dưới đây:
i j i AND j
0 0 0
1 0 0
0 1 0
1 1 1
Như vậy, i AND j cho kết quả là 1 khi và chỉ khi cả hai bít i và j đều có giá trị
1.
- Phép cộng loại trừ (Phép toán XOR) Phép toán XOR là phép toán hai ngôi.
Giả sử i và j là hai bít có giá trị (0,1) thì phép toán i XOR j sẽ cho giá trị tương ứng
như bảng dưới đây:
i j i XOR j
0 0 0
15
- 1 0 1
0 1 1
1 1 0
Như vậy, i XOR j cho kết quả là 1 khi cả hai bít i và j có giá trị khác nhau.
- Phép dịch phải (phép toán SHR)
Với hai số nguyên x và i, phép toán x shr i cho giá trị là số nguyên nhận được
sau khi dịch số x sang phải i bít.
Ví dụ: x có giá trị là 5, biểu diễn nhị phân của x là:
0 0 0 0 1 0 1
Khi thực hiện phép toán: x Shr 1, ta nhận được biểu diễn nhị phân là:
0 0 0 0 0 1 0
Đây là biểu diễn nhị phân của số 2 trong hệ thập phân.
Quy tắc:
Muốn chia nguyên một số nguyên cho 2, ta dịch số đó sang phải một bít. Muốn
chia nguyên một số nguyên cho 2i, ta dịch số đó sang phải i bít.
x shr i = x DIV 2i
Muốn tìm dư của phép chia nguyên của một số nguyên cho số 2 i, ta nhân logic
số đó với n - 1
x mod 2i = x AND (2i - 1)
- Phép dịch trái (Phép toán SHL)
Với hai số nguyên x và i, phép toán x shr i cho giá trị là số nguyên nhận được
sau khi dịch số x sang trái i bít.
Ví dụ: x có giá trị là 5, biểu diễn nhị phân của x là:
0 0 0 0 1 0 1
Khi thực hiện phép toán: x Shr 1, ta nhận được biểu diễn nhị phân là:
0 0 0 1 0 1 0
Đây là biểu diễn nhị phân của số 10 trong hệ thập phân.
Quy tắc:
Muốn nhân một số nguyên với 2, ta dịch số đó sang trái một bít. Muốn nhân
một số nguyên với 2i, ta dịch số đó sang trái i bít.
x shl i = x * 2i
Muốn tìm dư của phép chia nguyên của một số nguyên cho số 2 i, ta nhân logic
số đó với n - 1
x mod 2i = x AND (2i - 1)
1.2.3. Một số hàm và thủ tục xây dựng trên các phép toán cơ bản
- Hàm Getbit(x,i: integer) cho giá trị của bít thứ i của số nguyên x (tính từ
phải sang trái)
16
- Function Getbit(x,i:byte):byte;
Begin
getbit:=(x shr i) and 1;
end;
Phương pháp: Dịch bít thứ i về đầu phải rồi nhân locgic với 1 để lấy giá trị của
bít đó.
- Thủ tục Setbit(var x:byte;i:byte) gán giá trị 1 cho bít thứ i của số x
Procedure setbit(var x:byte;i:byte);
Begin
x:= x OR (1 shl i);
End;
Phương pháp: Dich chuyển bít 1 đến vị trí i, sau đó thực hiện phép cộng logic
với x.
- Thủ tục hidebit(var x:byte;i:byte) gán giá trị 0 cho bít thứ i của số x.
Procedure hidebit(var x:byte;i:byte);
Begin
x:= x AND (NOT(1 shl i));
End;
Phương pháp: Dich chuyển bít 1 đến vị trí i tương ứng sau đó đảo byte này
để được byte có giá trị 0 ở bít i và giá trị 1 trong các bit còn lại. Cuối cùng thực
hiện phép nhân logic với byte x.
II. Kết hợp kỹ thuật đánh dấu phần tử với xử lý bít để giải quyết một số bài
toán trong Tin học
2.1. Bài toán sắp xếp
Sắp xếp dữ liệu đóng vai trò rất quan trọng trong xữ lý thông tin. Ý nghĩa
thực tiễn của việc sắp xếp là nhằm dễ dàng tìm kiếm thông tin cần thiết.
2.1.1. Mô tả bài toán: Có N học sinh (1 < N < 32000). Mỗi học sinh có một mã số
là một số nguyên dương đôi một khác nhau (1 < ai < 32000). Hãy sắp các học sinh
trên tăng dần theo mã số của học sinh.
2.1.2. Phân tích:
a. Phương án đơn giản:
+ Thuật toán đơn giản: (T1)
Thuật toán đơn giản nhất và dễ thấy nhất thường được sử dụng để giải quyết
bài toán này như sau::
Bước 1: Lấy phần tử đầu tiên a1 so sánh với lần lượt từng phần tử thứ 2 đến
cuối dãy (aj).
17
- Bước 2: Nếu a1>ạ thì thực hiện đổi chỗ hai phần tử đó cho nhau.
Bước 3: Xem phần tử thứ hai là phần tử đầu tiên, lặp lại thực hiện Bước 1
Bước 4: In kết quả.
+ Chương trình biểu diễn của thuật toán T1:
const fi='sap1.inp';
fo='sap1.out';
type mmc=array[1..32000] of integer;
var f:text;
i,j,n,t:integer;
a:^mmc; ti:longint;
Begin
ti:=meml[0:$46c];
new(a);
assign(f,fi);reset(f);
readln(f,n);
for i:=1 to n do read(f,a^[i]);
close(f);
for i:=1 to n-1 do
for j:=i+1 to n do
if a^[i]>a^[j] then
begin
t:=a^[i]; a^[i]:=a^[j]; a^[j]:=t;
end;
assign(f,fo);rewrite(f);
writeln(f,n);
for i:=1 to n do write(f,a^[i],' ');
close(f);
dispose(a);
writeln('Thoi gian thu hien ',(meml[0:$46c]-ti)/18.21:8:5);
readln;
end.
+ Nhận xét 1 :
- Phân tích thuật toán và chương trình ta thấy có 2 vòng lặp FOR lồng nhau
nên ta ước lượng được độ phức tạp của thuật toán T1 trên là O(N2).
- Khi N bé, thuật toán trên có thể chấp nhận được. Tuy nhiên, trong nhiều
trường hợp N lớn, chẳng hạn N=32000 phần tử, khi đó máy sẽ thực hiện trong rất
18
- nhiều thời gian mới sắp xếp được dãy số. (với N=32000, thời gian thực hiện
khoảng 14 giây)
- Để giải quyết được bài toán này khi N lớn trong một khoảng thời gian rất
nhỏ, ta sử dụng kỹ thuật đánh dấu phần tử.
- Ta cần chú ý đến một giả thiết quan trọng trong bài toán đặt ra là “các phần
tử đôi một khác nhau”, nghĩa là trong dãy không có phần tử nào trùng nhau. Đối
với bài toán sắp xếp có phần tử trùng nhau ta không sử dụng được kỹ thuật này.
b. Phương pháp cải tiến: P2-Phương pháp đánh dấu trên byte.
+ Dữ liệu: Sử dụng một mảng A gồm 32000 phần tử, các phần tử có kiểu byte.
ý nghĩa: A[i] = 1 có nghĩa i là phần tử có trong dãy, A[i] = 0 có nghĩa i là phần tử
không có trong dãy.
+ Thuật toán cải tiến: (T2)
+ Khởi động mọi giá trị của A[] là 0 {Giống như giả sử ban đầu mọi phần tử
đều không thuộc dãy số}
+ Đọc từng phần tử của dãy số, giả sử số thứ j của dãy là X, ta đánh dấu
phần tử A[X] = 1 {Xác nhận số X thuộc dãy số}. Thực hiện đánh dấu cho đến khi
đọc hết dãy số. Khi đó ta thu được một mảng A[] trong đó A[i] = 1 tại các chỉ số i
có giá trị bằng giá trị các phần tử trong dãy số.
+ Duyệt từ đầu mảng đến cuối mảng, nếu vị trí vào có giá trị 1 thì ta xuất chỉ
số đó ra. Kết quả ta được một dãy số được sắp xếp tăng dần
+ Chương trình biểu diễn thuật toán T2:
const fi='sap2.inp';
fo='sap2.out';
type mmcb=array[1..32000] of byte;
var f:text;
n:word;
a:mmcb;
ti:longint;
procedure doc;
var i,x:word;
begin
fillchar(a,sizeof(a),0);
assign(f,fi);
reset(f);
readln(f,n);
for i:=1 to n do
begin
19
nguon tai.lieu . vn
