›
›

Hệ quản trị cơ sở dữ liệu - Chương 5: Cơ sở dữ liệu

pdf 61 trang vanle 5010
Download
Bạn đang xem 20 trang mẫu của tài liệu "Hệ quản trị cơ sở dữ liệu - Chương 5: Cơ sở dữ liệu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfhe_quan_tri_co_so_du_lieu_chuong_5_co_so_du_lieu.pdf

Nội dung text: Hệ quản trị cơ sở dữ liệu - Chương 5: Cơ sở dữ liệu

  1. Chương 5 CƠ SỞ DỮ LIỆU Chương này giới thiệu những kiến thức cơ bản liên quan đến cơ sở dữ liệu, hệ quản trị cơ sở dữ liệu, ngôn ngữ truy vấn dữ liệu SQL. Từ đó, giúp sinh viên hiểu được: cơ sở dữ liệu là gì, sự cần thiết của việc tổ chức dữ liệu dưới dạng cơ sở dữ liệu, phần mềm dùng để tạo lập và quản trị cơ cở dữ liệu, ngôn ngữ truy vấn dữ liệu SQL. 5.1. CƠ SỞ DỮ LIỆU 5.1.1. Khái niệm cơ sở dữ liệu Cơ sở dữ liệu (CSDL, thuật ngữ tiếng Anh là database) là một tập hợp các dữ liệu có liên quan với nhau chứa thông tin về một tổ chức nào đó (như một trường đại học, một ngân hàng, một bệnh viện, một công ty ) được lưu trữ trên các thiết bị nhớ thứ cấp (như băng từ, đĩa từ ) để đáp ứng nhu cầu khai thác thông tin của nhiều người sử dụng với nhiều mục đích khác nhau. Ví dụ 5.1: Bài toán Quản lý sinh viên đơn giản, ta có thể dùng một cơ sở dữ liệu lưu trữ thông tin về sinh viên và kết quả học tập của họ bao gồm 5 bảng (ví dụ được tạo bởi phần mềm Microsoft Access) như sau: Bảng KHOA: Bảng LOP: 80
  2. Bảng SINHVIEN: Bảng MONHOC: Bảng KETQUA: 5.1.2. Các mức thể hiện của cơ sở dữ liệu Vì mỗi nhóm người dùng có vai trò, nhu cầu hiểu và khai thác thông tin khác nhau nên để quản lý thông tin một cách hiệu quả, các hệ CSDL phải có các mức thể hiện khác nhau. Có 3 mức thể hiện CSDL là mức vật lý, mức khái niệm, mức khung nhìn. a. Mức vật lý Những chuyên gia tin học cần hiểu chi tiết về cách lưu trữ dữ liệu trong bộ nhớ, chẳng hạn: các tệp dữ liệu được lưu trữ trong vùng nhớ nào? mỗi bản ghi chiếm bao nhiêu byte? Mức hiểu biết chi tiết về một CSDL như vậy gọi là mức vật lý của hệ CSDL đó. 81
  3. b. Mức khái niệm Nhóm phát triển các ứng dụng không cần hiểu chi tiết ở mức vật lý, nhưng họ cần phải biết những dữ liệu nào được lưu giữ trong CSDL, giữa các dữ liệu có mối quan hệ như thế nào. Mức hiểu CSDL như vậy được gọi là mức khái niệm. SinhVien MaSV Hodem Lop ten MaLop Ngaysinh TenLop Gioitinh MaKhoa Tinh MaLop Khoa Ketqua Monhoc MaKhoa MaSV MaMH TenKhoa MaMH TenMH SDT Diem DVHT DieuKien Hình 5.1. Ví dụ về mức khái niệm của CSDL c. Mức khung nhìn Mỗi nhóm người dùng chỉ cần biết phần thông tin nào đó của CSDL phù hợp với nghiệp vụ hay mục đích sử dụng của mình. Ví dụ, sinh viên thông qua khung nhìn biết được những thông tin liên quan đến bản thân họ. Người quản trị CSDL cần biết được toàn bộ thông tin về CSDL Vì vậy, mức khung nhìn là mức hiểu CSDL của người dùng thông qua khung nhìn. Ba mức hiểu về CSDL như trên chính là ba mức mô tả và làm việc với CSDL, phù hợp với nhu cầu khác nhau của những người liên quan đến CSDL. USER 1 K. nhìn 1 USER 2 K. nhìn 2 CSDL mức CSDL mức khái niệm vật lý (logic) USER n K. nhìn n Hình 5.2. Ba mức thể hiện của CSDL 82
  4. 5.1.3. Mô hình dữ liệu quan hệ Mô hình dữ liệu (data model) là một tập các khái niệm và kí pháp dùng để mô tả dữ liệu, các mối quan hệ của dữ liệu, các ràng buộc trên dữ liệu của một tổ chức. Hiện nay, có khá nhiều mô hình dữ liệu như: - Mô hình dữ liệu quan hệ (Relational Data Model). - Mô hình dữ liệu phân cấp (Hierarchical Data Model). - Mô hình dữ liệu mạng (Network Data Model). - Mô hình dữ liệu thực thể - liên kết (Entity-Relationship Data Model). - Mô hình dữ liệu hướng đối tượng (Object Data Model). Trong các mô hình trên thì mô hình dữ liệu quan hệ được sử dụng khá phổ biến. Mô hình này được đề xuất bởi E. F. Codd vào những năm 1970 - 1972. Nó cung cấp một cấu trúc dữ liệu đơn giản đó là quan hệ (bảng). Cơ sở dữ liệu được xây dựng trên mô hình dữ liệu quan hệ được gọi là CSDL quan hệ. Một CSDL quan hệ thông thường chứa nhiều bảng. Mỗi bảng chứa dữ liệu của một tập thực thể, bao gồm các hàng và các cột. Mỗi hàng là một bản ghi (Record), mỗi cột là một trường (Field). a. Một số khái niệm cơ bản trong mô hình dữ liệu quan hệ Quan hệ: Dữ liệu lưu trữ trong CSDL được tổ chức thành bảng 2 chiều. Mỗi bảng 2 chiều được gọi là một quan hệ. Dưới đây là ví dụ của một quan hệ: Tên bảng ~ Tên các thuộc tính ~ Trường (Field) Tên quan hệ SINHVIEN MaSV HoDem Ten NgaySinh GioiTinh Tinh 521234 Lê Thị Lan 02/04/90 Nữ Hà Nội 521235 Nguyễn Văn Nam 23/06/90 Nam Thanh Hóa 521235 Lê Văn Hùng 03/05/91 Nam Hà Nội Hàng ~ Bộ ~ Bản ghi Hình 5.3. Ví dụ về quan hệ SINHVIEN Lược đồ (schema) Tên của một quan hệ và tập các thuộc tính của nó được gọi là một lược đồ đối với quan hệ đó. Ta biểu diễn lược đồ cho một quan hệ bởi Tên của quan hệ và theo sau là danh sách các thuộc tính của nó. Vậy lược đồ của quan hệ SINHVIEN trong hình 5.3 là: SINHVIEN(MaSV, HoDem, Ten, NgaySinh, GioiTinh, Tinh) 83
  5. Lược đồ cơ sở dữ liệu quan hệ (relational database schema) là tập các lược đồ quan hệ của bài toán. Ví dụ 5.2: Bài toán quản lý sinh viên trong ví dụ 5.1 có lược đồ CSDL bao gồm 5 lược đồ quan hệ sau: KHOA(MaKhoa, TenKhoa, SoDT) LOP(MaLop, TenLop, MaKhoa) SINHVIEN(MaSV, HoDem, Ten, NgaySinh, GioiTinh, Tinh, MaLop) MONHOC(MaMH, TenMH, DVHT, Dieukien) KETQUA(MaSV, MaMH, Diem) Bộ (tuble) Bộ là dòng của một quan hệ, trừ dòng tiêu đề (tên của các thuộc tính). Bộ còn có cách gọi khác là bản ghi (record). Trong một quan hệ các bộ không được trùng nhau. Miền (domain) Miền là tập các giá trị mà thuộc tính có thể nhận. Ví dụ, miền của thuộc tính Gioitinh (giới tính) trong ví dụ 5.2 gồm hai giá trị {Nam, Nữ}. Khóa (key, còn gọi là khóa chính) Khóa của một quan hệ là một hoặc nhiều thuộc tính tối thiểu để xác định tính duy nhất của mỗi bộ trong quan hệ đó Ví dụ 5.3: Trong quan hệ SINHVIEN ở trên, dễ hiểu là MaSV của mỗi sinh viên là duy nhất, không thể có 2 mã sinh viên trùng nhau. Vậy MaSV được thiết lập là khóa. Ví dụ 5.4: Trong quan hệ KETQUA(MaSV, MaMH, Diem) ở trên, vì một sinh viên có thể học nhiều môn học nên để ghi điểm các môn của sinh viên đó vào bảng thì các bộ có cùng MaSV, khác nhau MaMH. Tương tự, một môn học có thể được học bởi nhiều sinh viên, nên các bộ có thể trùng MaMH, khác nhau MaSV (xem bảng KETQUA ở trên). Nhưng cặp MaSV, MaMH không thể trùng nhau để xác định duy nhất một điểm môn học của sinh viên. Chú ý: Một quan hệ có thể có nhiều khóa, khi đó mỗi một khóa được gọi là một khóa dự tuyển. Thông thường có một khóa dự tuyển được chỉ định làm khóa chính. Việc lựa chọn một khóa dự tuyển làm khóa chính là tùy ý, nhưng nên chọn khóa dự tuyển đặc trưng cho bộ và chỉ gồm một thuộc tính hoặc có ít thuộc tính nhất làm khóa chính. Ví dụ 5.5: Lược đồ quan hệ KHOA(MaKhoa, TenKhoa, SoDT) có hai khoá ứng cử là: K1= {MaKhoa}, K2 ={TenKhoa}, tuy nhiên ta chọn MaKhoa làm khoá chính vì nó đặc trưng cho Khoa hơn và các giá trị của thuộc tính này ngắn, không có dấu và không có khoảng trống. Khóa ngoại (foreign key) Khóa ngoại (khóa ngoài) của một lược đồ quan hệ là một tập gồm một hay nhiều thuộc tính không phải là khóa chính của lược đồ quan hệ này nhưng lại là khóa chính của một lược đồ quan hệ khác. 84
  6. Khoá ngoại dùng để biểu thị liên kết giữa quan hệ này và quan hệ khác trong mô hình quan hệ. Ví dụ 5.6: Xét lược đồ CSDL trong ví dụ 5.2. Ta thấy, trong lược đồ quan hệ LOP có MaKhoa là khoá ngoại (vì nó là khoá chính trong lược đồ quan hệ KHOA nhưng không phải là khoá chính của lược đồ quan hệ LOP). Khi đã tạo mối quan hệ (Relationship) hợp lý giữa trường MaKhoa trong bảng KHOA với trường MaKhoa trong bảng LOP thì ta có thể truy vấn các thông tin liên quan giữa 2 quan hệ này như lớp này thuộc khoa nào, có tên khoa là gì. Những nội dung như này sẽ được minh họa rõ ràng hơn ở phần sau và khi thực hành trên máy tính. Một ví dụ tương tự trong lược đồ quan hệ SINHVIEN có MaLop là khoá ngoại (vì nó là khoá chính trong lược đồ quan hệ LOP nhưng không phải là khoá chính của lược đồ quan hệ SINHVIEN). Lưu ý là khóa ngoại không xác định tính duy nhất của bộ dữ liệu như khóa chính. Với ví dụ này: - Trong quan hệ LOP, thuộc tính MaKhoa của các bộ có thể trùng nhau (tương đương một khoa có nhiều lớp); nhưng trong quan hệ KHOA thì thuộc tính MaKhoa của mỗi bộ phải là duy nhất. - Trong quan hệ SINHVIEN, thuộc tính MaLop của các bộ có thể trùng nhau (tương đương một lớp có nhiều sinh viên); nhưng trong quan hệ LOP thì thuộc tính MaLop của mỗi bộ phải là duy nhất. 5.1.4. Hệ cơ sở dữ liệu Hệ CSDL (Database system) là một hệ thống gồm 4 thành phần: - Cơ sở dữ liệu. - Người sử dụng cơ sở dữ liệu: Là bất cứ một người nào đó có thể truy nhập (hợp pháp) vào CSDL, có nghĩa là bao gồm tất cả những người sử dụng cuối, những người viết chương trình ứng dụng và những người điều khiển toàn bộ hệ thống (còn gọi là người quản trị CSDL). - Hệ quản trị CSDL (Phần 5.2). - Phần cứng: Bao gồm các thiết bị nhớ thứ cấp được sử dụng để lưu trữ CSDL. 5.1.5. Lợi ích của hệ cơ sở dữ liệu Trước khi các hệ CSDL ra đời (khoảng đầu những năm 60) là giai đoạn tiền xử lý cơ sở dữ liệu: Dữ liệu được tổ chức và xử lý bởi các tệp ghi trên các băng từ. Các ngôn ngữ lập trình như COBOL, BASIC được sử dụng để lập trình xử lý dữ liệu. Mỗi chương trình ứng dụng đều có một tệp dữ liệu tương ứng và mỗi khi chương trình ứng dụng cần được sửa đổi hoặc mở rộng thì tệp dữ liệu tương ứng cũng phải thay đổi theo. Cách tổ chức lưu trữ như vậy sẽ bị dư thừa dữ liệu, dữ liệu không nhất quán, khó khăn trong việc truy cập và chia sẻ dữ liệu, dữ liệu không được bảo mật cao Việc sử dụng hệ CSDL để lưu trữ dữ liệu theo lý thuyết cơ sở dữ liệu sẽ khắc phục được những hạn chế của cách lưu trữ trên, cụ thể có những ưu điểm sau: - Giảm bớt dư thừa dữ liệu trong lưu trữ: Trong các ứng dụng lập trình truyền thống, phương pháp tổ chức lưu trữ dữ liệu vừa tốn kém, dư thừa thông tin và lãng phí bộ nhớ. 85
  7. Nhiều chương trình ứng dụng khác nhau cùng xử lý trên các dữ liệu như nhau nhưng lại không dùng chung dữ liệu, dẫn đến sự dư thừa đáng kể về dữ liệu. - Tránh được sự không nhất quán trong lưu trữ dữ liệu và bảo đảm được tính toàn vẹn của dữ liệu: Nếu một thuộc tính được mô tả trong nhiều tệp dữ liệu khác nhau và các bản ghi bị lặp lại nhiều lần thì khi thực hiện việc cập nhật, sửa đổi, bổ sung sẽ không sửa hết nội dung các mục đó. Nếu dữ liệu càng nhiều thì sự sai sót khi cập nhật, bổ sung càng lớn. Khả năng xuất hiện mâu thuẫn, không nhất quán thông tin càng nhiều, dẫn đến không nhất quán dữ liệu trong lưu trữ. Tất yếu kéo theo sự dị thường thông tin, thừa, thiếu và mâu thuẫn thông tin. Nếu một thuộc tính của một đối tượng chỉ được lưu trữ một lần trong một CSDL thì sẽ đảm bảo được tính toàn vẹn và nhất quán của dữ liệu. - Có thể triển khai đồng thời nhiều ứng dụng trên cùng một CSDL: Điều này có nghĩa là trên cùng một CSDL có thể triển khai đồng thời nhiều ứng dụng khác nhau tại các thiết bị đầu cuối khác nhau. - Thống nhất các tiêu chuẩn, thủ tục và các biện pháp bảo vệ, an toàn dữ liệu: Các CSDL sẽ được quản lý tập trung bởi một người hay một nhóm người quản trị CSDL. Người quản trị CSDL có thể áp dụng thống nhất các tiêu chuẩn, quy định, thủ tục chung như quy định thống nhất về mẫu biểu báo cáo, thời gian bổ sung, cập nhật dữ liệu. Nhờ đó công việc bảo trì dữ liệu trở nên dễ dàng. Người quản trị CSDL có thể bảo đảm việc truy nhập tới CSDL, có thể kiểm tra, kiểm soát các quyền truy nhập của người sử dụng, có thể cho phép nhiều người truy nhập đồng thời mà vẫn đảm bảo tính đúng đắn của dữ liệu. Người quản trị CSDL có thể cho phép mỗi người dùng của hệ CSDL chỉ được phép truy cập một phần CSDL, điều đó cũng là một biện pháp giữ cho dữ liệu trong CSDL được an toàn. Ví dụ, trong hệ thống quản lý học tập theo tín chỉ trên mạng, các sinh viên của trường chỉ nhìn thấy một phần CSDL chứa thông tin về sinh viên đó thông qua tài khoản họ được cấp chứ không nhìn thấy các thông tin của sinh viên khác. Như vậy, việc tổ chức lưu trữ dữ liệu trong CSDL giúp người dùng quản lý dữ liệu tốt hơn và thông qua các hệ quản trị CSDL ta có thể thực hiện các nhiệm vụ quan trọng như: tổng hợp, sắp xếp, tìm kiếm, thêm, xóa, sửa và khai thác dữ liệu. 5.2. HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 5.2.1. Khái niệm Hệ quản trị cơ sở dữ liệu (HQTCSDL, thuật ngữ tiếng Anh là Database Management System - DBMS) là phần mềm được thiết kế để thuận lợi việc tạo lập, lưu trữ và khai thác thông tin của CSDL. Như vậy, HQTCSDL cung cấp một môi trường thuận lợi, đơn giản và hiệu quả để người sử dụng có thể tạo lập, lưu trữ và thao tác trên CSDL mà không cần quan tâm nhiều đến thuật toán chi tiết và cách biểu diễn dữ liệu trong bộ nhớ. Dưới đây là giao diện của việc dùng HQTCSDL Microsoft Access để tạo lập cơ sở dữ liệu: 86
  8. Hình 5.4. Giao diện thiết kế các bảng trong HQTCSDL Microsoft Access 5.2.2. Phân loại hệ quản trị cơ sở dữ liệu a. Phân loại Các hệ quản trị cơ sở dữ liệu được phân thành 3 loại: XML DBMS, ODBMS và RDBMS.  XML DBMS: Phù hợp cho dữ liệu đã được định dạng XML (eXtensible Markup Language).  ODBMS (object database management system): Phù hợp cho mô hình CSDL hướng đối tượng.  RDBMS (relational database management system): Phù hợp cho mô hình cơ sở dữ liệu quan hệ. Ngày nay, các HQTCSDL này đều có tính năng thao tác trên dữ liệu XML và các lớp đối tượng. Thông thường, mỗi một HQTCSDL được xây dựng để phục vụ cho một mô hình dữ liệu nhất định, nhưng cũng có một số HQTCSDL có thể phục vụ cho nhiều mô hình dữ liệu khác nhau. b. Một số hệ quản trị cơ sở dữ liệu phổ biến Ngày nay, có một số HQTCSDL phổ biến như: Microsoft Access, Microsoft SQL Server, MySQL, SQLite, Oracle. 87
  9. - DB2 là sản phẩm của IBM thuộc dòng HQTCSDL quan hệ, phiên bản đầu tiên ra đời năm 1982. Đây là HQTCSDL được dùng cho tất cả các máy tính, từ máy tính cá nhân đến những dòng máy tính lớn. - Microsoft SQL Server và Microsoft Access là sản phẩm của Microsoft, thuộc loại HQTCSDL quan hệ. - MySQL là HQTCSDL nguồn mở đa luồng, đa người dùng, được hãng MySQL sản xuất. MySQL rất phổ biến với những ứng dụng web và có thể làm việc với các CSDL trên nền Linux/Mac/Windows. - SQLite là một hệ quản trị cơ sở dữ liệu có đặc điểm của gọn, nhẹ, đơn giản. Chương trình gồm 1 file duy nhất có dung lượng chưa đến 500kB, không cần cài đặt mà có thể sử dụng ngay. CSDL được lưu ở một file duy nhất, chạy tốt trên platform Mac OS-X, Android, iOS. 5.2.3. Chức năng cơ bản của hệ quản trị cơ sở dữ liệu Một hệ quản trị cơ sở dữ liệu có các chức năng cơ bản sau đây: Cung cấp môi trường tạo lập CSDL Cung cấp môi trường cập nhật và khai thác dữ liệu - Cập nhật: Thêm, xóa, sửa dữ liệu. - Khai thác: Sắp xếp, tìm kiếm, kết xuất báo cáo Cung cấp công cụ kiểm soát, điểu khiển CSDL - Phát hiện và ngăn chặn sự truy cập không được phép. - Duy trì tính nhất quán của dữ liệu. - Tổ chức và điều khiển các truy nhập đồng thời. - Khôi phục CSDL khi có sự cố ở phần cứng hay phần mềm. - Quản lý các mô tả dữ liệu. Nói chung các HQTCSDL đều có các chức năng trên, nhưng các HQTCSDL khác nhau có chất lượng và khả năng khác nhau khi đáp ứng các nhu cầu thực tế. Các HQTCSDL luôn phát triển theo hướng đáp ứng đòi hỏi ngày càng cao của người dùng, bởi vậy các chức năng của chúng ngày càng được mở rộng. 5.3. NGÔN NGỮ TRUY VẤN SQL SQL (Structured Query Language – ngôn ngữ truy vấn có cấu trúc) là ngôn ngữ truy vấn dựa trên đại số quan hệ được xác nhận là rất mạnh, phổ dụng và dễ sử dụng. SQL được sử dụng hầu hết trong các thao tác: truy vấn, thêm, xóa, sửa trên các hệ quản trị CSDL quan hệ. SQL được thiết lập như một ngôn ngữ chuẩn đối với cơ sở dữ liệu. Ngôn ngữ SQL gồm các thành phần: - Ngôn ngữ định nghĩa dữ liệu (Data Definition Language - DDL): Cung cấp các câu lệnh cho phép định nghĩa các lược đồ quan hệ, các ràng buộc toàn vẹn mà dữ liệu được lưu trữ trong CSDL phải thỏa mãn, cho phép xóa, sửa cấu trúc các quan hệ. 88
  10. - Ngôn ngữ thao tác dữ liệu (Data Manipulation Language - DML): Đây là nhóm câu lệnh cho phép thao tác trên các dữ liệu của quan hệ. Nó dùng để tìm kiếm, trích rút, tổng hợp dữ liệu từ các quan hệ, đồng thời cho phép thêm, xóa, sửa dữ liệu trong các quan hệ - Nhóm ngôn ngữ kiểm soát dữ liệu (Data Control Language - DCL): Bao gồm các câu lệnh đảm bảo tính an toàn và toàn vẹn dữ liệu, cấp phát quyền truy cập vào dữ liệu. Trong nội dung giáo trình Tin học đại cương này chủ yếu giới thiệu nhóm ngôn ngữ thao tác dữ liệu cơ bản. Nhóm ngôn ngữ SQL thao tác dữ liệu bao gồm các câu lệnh cho phép thao tác trên dữ liệu của CSDL. Nó dùng để thực hiện các truy vấn như: tìm kiếm, thêm, xóa, sửa các bản ghi. - SELECT – trích dữ liệu từ một cơ sở dữ liệu - INSERT – chèn dữ liệu mới vào trong một cơ sở dữ liệu - DELETE – xóa dữ liệu từ một cơ sở dữ liệu - UPDATE – cập nhật dữ liệu trong một cơ sở dữ liệu 5.3.1. Câu lệnh truy vấn dữ liệu Loại câu lệnh này cho phép ta tìm kiếm, trích rút dữ liệu từ cơ sở dữ liệu. Kết quả của câu lệnh được hiển thị dưới dạng bảng 2 chiều. Cú pháp: SELECT [DISTINCT] | *| FROM [,bảng 2 ] [WHERE ] [GROUP BY [HAVING ]] [ORDER BY [ASC|DESC]] Giải thích: - DISTINCT là từ khoá để được một danh sách không có các bản ghi trùng nhau. - Các thành phần mà người dùng phải điền cụ thể vào khi viết lệnh được viết trong cặp . - Các thành phần tùy chọn (những thành phần có thể có hoặc không) được viết trong cặp [ ]. - Danh sách các cột là tên các cột cần truy vấn trong các bảng (chú ý nếu tên cột xuất hiện trên nhiều bảng thì phải chỉ rõ cột đó được tham chiếu qua bảng nào bằng cú pháp: Tenbang.Tencot) - SELECT *: dùng để hiển thị tất cả các cột trong bảng. - Bảng 1, bảng 2 là tên các bảng hoặc tên các khung nhìn dùng để truy vấn dữ liệu. 89
  11. - Mệnh đề WHERE dùng để chỉ định một tiêu chuẩn chọn các bản ghi. - là một biểu thức logic có kết quả trả về là TRUE hoặc FALSE. - GROUP BY dùng để nhóm kết quả hiển thị theo từng loại giá trị của cột. - Having là tiêu chuẩn chọn trên từng nhóm, được đặt sau GROUP BY. - ORDER BY dùng để sắp xếp kết quả vừa chọn ở trên theo cột nào (ASC là tăng, DESC là giảm). Biểu thức có các toán tử sau có thể được dùng: Bảng 5.1. Các toán tử trong SQL Phép toán Giải thích = Bằng Lớn hơn = Lớn hơn hoặc bằng AND Chọn tất cả các trị trong khoảng giới hạn giữa hai giá trị. Các trị này có thể là các số, chuỗi kí tự, hay ngày tháng. [NOT] IN (danh sách|câu truy vấn]) Kiểm tra giá trị của biểu thức có trong tập danh sách các giá trị không [NOT] EXISTS ( ) Kết quả trả về TRUE nếu câu truy vấn khác rỗng. SOME|ALL|ANY Kết quả trả TRUE nếu phép so sánh thỏa mãn. Ví dụ 5.7: Sử dụng CSDL trong ví dụ 5.1 để thực hiện các yêu cầu sau: Câu lệnh SQL hiển thị thông tin về tất cả sinh viên, thông tin hiển thị cần: mã sinh viên, họ tên, ngày sinh, giới tính: SELECT MaSV, HoDem, Ten, NgaySinh, GioiTinh FROM Sinhvien; 90
  12. Để chạy thử câu lệnh SQL, ta mở CSDL của bài toán trên đã được cài đặt trong một HQTCSDL, sau đó gõ câu lệnh SQL và chạy thử, màn hình sẽ hiển trị kết quả truy vấn. Hình 5.5. Giao diện soạn thảo câu lệnh SQL trong HQTCSDL Microsoft Access Hình 5.6. Kết quả thực hiện câu lệnh SQL hình 5.5 trong HQTCSDL Microsoft Access 91
  13. Câu lệnh SQL hiển thị thông tin về các sinh viên nữ, thông tin hiển thị cần: mã sinh viên, họ tên, ngày sinh, giới tính. SELECT MaSV, HoDem, Ten, NgaySinh, GioiTinh FROM Sinhvien WHERE Gioitinh=“Nữ”; Chạy thử câu lệnh SQL trong HQTCSDL Microsoft Access: Hình 5.7. Giao diện soạn thảo câu lệnh SQL trong HQTCSDL Microsoft Access Hình 5.8. Kết quả thực hiện câu lệnh SQL hình 5.7 trong HQTCSDL Microsoft Access 92
  14. Câu lệnh SQL hiển thị thông tin về các sinh viên khoa CNTT (có MaKhoa=“CNTT”). Thông tin hiển thị cần: mã sinh viên, họ tên, ngày sinh, giới tính: SELECT MaSV, HoDem, Ten, NgaySinh, GioiTinh FROM Sinhvien, Lop WHERE Lop.MaKhoa="CNTT" AND (Sinhvien.MaLop=Lop.MaLop); Hình 5.9. Giao diện soạn thảo câu lệnh SQL trong HQTCSDL Microsoft Access Hình 5.10. Kết quả thực hiện câu lệnh SQL hình 5.9 trong HQTCSDL Microsoft Access 93
  15. Câu lệnh SQL hiển thị thông tin về các sinh viên với các kết quả học tập của họ. Thông tin hiển thị cần: mã sinh viên, họ tên, ngày sinh, giới tính, tên môn học, điểm. SELECT Sinhvien.MaSV, HoDem, Ten, NgaySinh, GioiTinh, TenMH, Diem FROM Sinhvien, Ketqua, Monhoc WHERE Sinhvien.MaSV = Ketqua.MaSV AND Ketqua.MaMH=Monhoc.MaMH; Chạy câu lệnh SQL trong HQTCSDL Microsoft Access: Hình 5.11. Giao diện soạn thảo câu lệnh SQL trong HQTCSDL Microsoft Access Hình 5.12. Kết quả thực hiện câu lệnh SQL hình 5.11 trong HQTCSDL Microsoft Access 94
  16. Câu lệnh SQL hiển thị thông tin về các sinh viên đạt điểm A học phần Tin học đại cương (MaMH=“TH01009”). Thông tin hiển thị cần (mã sinh viên, họ tên, ngày sinh, tên môn học, điểm) và được sắp xếp theo vần alphabet của tên và họ (nếu trùng tên thì sắp xếp theo họ đệm): SELECT Sinhvien.MaSV, HoDem, Ten, NgaySinh, TenMH, Diem FROM Sinhvien, Ketqua, Monhoc WHERE Sinhvien.MaSV=Ketqua.MaSV AND Ketqua.MaMH="TH1009" AND Ketqua.MaMH=Monhoc.MaMH AND Diem>=8.5 ORDER BY Ten, Hodem; Toán tử GROUP BY Có thể phân hoạch các bộ của một quan hệ thành các nhóm tách biệt nhau và áp dụng các phép toán gộp cho các nhóm. Trong câu lệnh SELECT – FROM – WHERE, mệnh đề GROUP BY nhóm lại bởi một danh sách các thuộc tính của quan hệ cần nhóm. Ví dụ 5.8: In ra danh sách các lớp và số sinh viên trong mỗi lớp: SELECT Sinhvien.MaLop, Lop.TenLop, COUNT(Sinhvien.MaSV) AS [So sinh vien] FROM Sinhvien, Lop WHERE Sinhvien.MaLop = Lop.MaLop GROUP BY Sinhvien.MaLop, Lop.TenLop Chạy câu lệnh SQL trong HQTCSDL Microsoft Access: Hình 5.13. Giao diện soạn thảo câu lệnh SQL trong HQTCSDL Microsoft Access 95
  17. Hình 5.14. Kết quả thực hiện câu lệnh SQL hình 5.13 trong HQTCSDL Microsoft Access Toán tử GROUP BY HAVING Phân hoạch các bộ của một quan hệ thành các nhóm tách biệt nhau và áp dụng các phép toán gộp cho các nhóm. Trong câu lệnh SELECT – FROM – WHERE, mệnh đề GROUP BY nhóm lại bởi một danh sách các thuộc tính của quan hệ cần nhóm và thoả mãn một điều kiện nhóm HAVING: GROUP BY A , A , , A l 2 k HAVING E Phân hoạch quan hệ thành các nhóm sao cho hai bộ cùng trong một nhóm khi và chỉ khi chúng giống nhau ở mọi thuộc tính A , A , A . Để cho kết quả của câu vấn tin có nghĩa, các l 2 k thuộc tính A , A , A cũng phải xuất hiện trong mệnh đề SELECT mặc dù chúng có thể có l 2 k những bí danh để in ra nếu cần. Ví dụ 5.9: In ra danh sách các lớp có số sinh viên ≥ 2. Thông tin hiển thị cần: Mã lớp, Tên lớp, Số sinh viên. SELECT Sinhvien.MaLop, Lop.TenLop, COUNT(Sinhvien.MaSV) AS ‘So sinh vien’ FROM Sinhvien, Lop WHERE Sinhvien.MaLop = Lop.MaLop GROUP BY Sinhvien.MaLop, Lop.TenLop HAVING COUNT(Sinhvien.MaSV)>=2; 96
  18. Toán tử LIKE: dùng chỉ định việc tìm gần đúng một xâu kí tự trong một cột. Cú pháp: SELECT FROM WHERE LIKE ; Một dấu "%" có thể dùng như ký tự đại diện cho một số kí tự Ví dụ 5.10: Hiển thị thông tin về những sinh viên có tên bắt đầu bằng chữ “N”. SELECT * FROM Sinhvien WHERE Ten LIKE “N%”; Toán tử BETWEEN AND : chọn tất cả các trị trong khoảng giới hạn giữa hai giá trị. Các giá trị này có thể là các số, chuỗi kí tự, hay ngày tháng. Ví dụ 5.11: Hiển thị thông tin về những sinh viên có ngày sinh trong khoảng 01/01/93 đến 31/12/94. Lưu ý là cần chuyển chuỗi ngày tháng trong câu lệnh thành dạng tháng trước ngày sau. SELECT * FROM Sinhvien WHERE Ngaysinh BETWEEN #01/01/93# AND #12/31/94#; Từ khóa DISTINCT dùng để trả về chỉ các giá trị khác biệt (distinct). Ví dụ 5.12: Hiển thị tên các tỉnh của sinh viên. SELECT DISTINCT Tinh FROM Sinhvien;  Truy vấn trên nhiều bảng dùng kết nối Join Kết nối bằng trên các thuộc tính cùng tên Cú pháp: SELECT FROM Bảng1 INNER JOIN Bảng2 ON [WHERE ]; Ví dụ 5.13: Hiển thị thông tin về các sinh viên cùng với tên lớp của họ. SELECT Sinhvien.*, Lop.TenLop FROM Sinhvien INNER JOIN Lop ON Sinhvien. MaLop=Lop.MaLop; Kết nối ngoài trên các thuộc tính cùng tên Cú pháp: SELECT FROM Bảng1 LEFT|RIGHT JOIN Bảng2 ON [WHERE ]; 97
  19. - LEFT JOIN trả về tất cả các hàng từ bảng thứ nhất, cho dù nó không được so trùng trong bảng thứ hai. Nếu các hàng trong bảng R1 không so trùng trong bảng R2, những hàng này cũng được liệt kê. - RIGHT JOIN trả về tất cả các hàng từ bảng thứ hai, cho dù nó không được so trùng trong bảng thứ nhất. Nếu có bất kỳ hàng nào trong bảng R1 không được so trùng trong bảng R2, các hàng này cũng được liệt kê. Ví dụ 5.14: Hiển thị thông tin về các lớp của các khoa, kể cả những khoa chưa có lớp trong bảng lớp. Thông tin cần hiển thị gồm: mã khoa, tên khoa, tên lớp. SELECT Khoa.MaKhoa, TenKhoa, TenLop FROM Khoa LEFT JOIN Lop ON Khoa.MaKhoa=Lop.MaK;  Câu lệnh truy vấn lồng Cú pháp: SELECT FROM Câu truy vấn cha WHERE ( SELECT FROM Câu truy vấn con WHERE ); Trong đó, phép so sánh tập hợp thường đi cùng với một số toán tử: IN, NOT IN, ALL, ANY, SOME, EXISTS, NOT EXISTS. Ví dụ 5.15: Hiển thị thông tin về những SV đã có kết quả điểm ít nhất một học phần: SELECT * FROM Sinhvien WHERE MaSV IN ( SELECT MaSV FROM Ketqua); Ví dụ 5.16: Hiển thị thông tin về những sinh viên đã đăng kí học và không phải học lại học phần nào. SELECT * FROM Sinhvien, Ketqua WHERE (Sinhvien.MaSV=Ketqua.MaSV) AND Sinhvien.MaSV NOT IN (SELECT MaSV FROM Ketqua WHERE Diem<4); 98
  20. 5.3.2. Câu lệnh cập nhật dữ liệu Dùng để thay đổi giá trị của thuộc tính cho các dòng của bảng. Cú pháp: UPDATE SET = [, = ] [WHERE ]; Ví dụ 5.17: Sửa tỉnh của sinh viên có mã sinh viên là 531236 từ Nam Định về Hà Nội. UPDATE Sinhvien SET Tinh=“Hà Nội” WHERE MaSV=“531236”; Lưu ý: - Những dòng thỏa mãn điều kiện tại mệnh đề WHERE sẽ được cập nhật giá trị mới. - Nếu không chỉ định điều kiện ở mệnh đề WHERE, tất cả các dòng trong bảng sẽ được cập nhật. - Lệnh UPDATE có thể gây ra vi phạm ràng buộc tham chiếu như sau:  Không cho sửa.  Sửa luôn những dòng có giá trị đang tham chiếu đến (ví dụ với HQTCSDL Microsoft Access, trong Relationship nếu ta chọn Cascade Update Related Fields). 5.3.3. Thêm dữ liệu Khi muốn thêm các dòng mới vào một bảng ta sử dụng cú pháp sau: Cú pháp 1: Thêm 1 dòng mới vào bảng với các giá trị cụ thể: INSERT INTO [ ] VALUES (danh sách các giá trị); Ví dụ 5.18: Thêm sinh viên có MaSV=“536780”, Hodem=“Lê Thị”, Ten=“Hà”, Ngaysinh=#25/5/90#, Gioitinh=“Nữ”, Tinh=“Hà Nội”, MaLop=“K52THA” vào bảng Sinhvien. INSERT INTO Sinhvien VALUES (“536780”, “Lê Thị”,“Hà”, #25/5/90#, “Nữ”, “Hà Nội”, “K52THA”); Chú ý: - Thứ tự các giá trị chèn vào phải trùng với thứ tự các cột trong bảng cần chèn. - Có thể chèn giá trị NULL ở những thuộc tính không là khóa chính. 99
  21. - Câu lệnh INSERT sẽ gặp lỗi nếu vi phạm các ràng buộc toàn vẹn sau:  Khóa chính  Tham chiếu  NOT NULL - các thuộc tính có ràng buộc NOT NULL bắt buộc phải có giá trị Cú pháp 2: Thêm nhiều dòng vào bảng INSERT INTO [ ] ; Ví dụ 5.19: Sao lưu những sinh viên có quê ở Hà Nội sang bảng Sinhvien_HN. INSERT INTO Sinhvien_HN SELECT * FROM Sinhvien WHERE Tinh=“Hà Nội”; 5.3.4. Xóa dữ liệu Dùng để xóa các dòng của một bảng. Cú pháp: DELETE FROM [WHERE ]; Ví dụ 5.20: Xóa sinh viên có mã sinh viên là 536780 ra khỏi bảng Sinhvien. DELETE FROM Sinhvien WHERE Masv=“536780”; Chú ý: - Số lượng dòng bị xóa phụ thuộc vào điều kiện ở mệnh đề WHERE - Nếu không chỉ định điều kiện ở mệnh đề WHERE, tất cả các dòng trong bảng sẽ bị xóa. - Lệnh DELETE có thể gây ra vi phạm ràng buộc tham chiếu.  Không cho xóa.  Xóa luôn những dòng có giá trị đang tham chiếu đến (ví dụ trong Microsoft Access, nếu trong Relationship ta chọn Cascade Delete Related Records). 5.3.5. Các hàm của SQL SQL xây dựng sẵn một số hàm để tính toán. a. Hàm AVG Hàm AVG cho trị trung bình cộng của dữ liệu trong một cột dạng dữ liệu số. Các trị NULL sẽ không được tính toán. 100
  22. Ví dụ 5.21: Hãy trả về điểm trung bình lần 1 của những sinh viên trong bảng "Ketqua". SELECT AVG(DiemL1) AS [Điểm trung bình] FROM Ketqua; Ví dụ 5.22: Hãy tính điểm trung bình lần 1 của các sinh viên theo từng lớp. SELECT MaLop, AVG(DiemL1) AS [Điểm trung bình] FROM Sinhvien INNERJOIN Ketqua ON Sinhvien.Masv=Ketqua.Masv GROUPBY MaLop; b. Hàm SUM Hàm SUM tính tổng của dữ liệu trong một cột có kiểu dữ liệu số. Các trị NULL sẽ không được tính toán. Ví dụ 5.23: Hãy trả về tổng điểm lần 1 của những sinh viên trong bảng "Ketqua". SELECT SUM(DiemL1) AS [Tổng điểm] FROM Ketqua; c. Hàm MAX Hàm MAX trả về giá trị lớn nhất trong một cột. Các trị NULL sẽ không được tính toán. Ví dụ 5.24: Hãy trả về giá trị điểm lớn nhất lần 1 của những sinh viên trong bảng "Ketqua". SELECT MAX(DiemL1) AS [Điểm lớn nhất] FROM Ketqua; Ví dụ 5.25: Hãy trả về giá trị điểm lớn nhất lần 1 của các sinh viên theo môn học: SELECT Ketqua.MaMH, TenMH, MAX(DiemL1) AS [Điểm lớn nhất] FROM Ketqua INNER JOIN Monhoc ON Ketqua.MaMH=Monhoc.MaMH GROUP BY Ketqua.MaMH, TenMH; d. Hàm MIN Hàm MIN trả về giá trị lớn nhất trong một cột, các trị NULL sẽ không được tính toán. Ví dụ 5.26: Hãy trả về giá trị điểm lần 1 nhỏ nhất của các sinh viên trong bảng "Ketqua". SELECT MIN(DiemL1) AS [Điểm nhỏ nhất] FROM Ketqua; CÂU HỎI VÀ BÀI TẬP 1. Nêu khái niệm cơ sở dữ liệu. 2. Phần mềm tốt nhất để tạo lập và quản lý CSDL là gì? 3. Trình bày ưu điểm của việc sử dụng CSDL. 101
  23. 4. Nêu các thành phần của hệ CSDL. 5. Hãy phân biệt HQTCSDL và CSDL. 6. Chức năng cơ bản của HQTCSDL là gì? 7. Nhóm ngôn ngữ thao tác dữ liệu SQL bao gồm các lệnh cho phép làm gì trên CSDL? 8. Hãy phân biệt các thuật ngữ sau: Quan hệ, lược đồ quan hệ, lược đồ CSDL quan hệ. 9. Bộ của quan hệ (bản ghi) là gì? Trong một quan hệ có cho phép tồn tại hai bộ giống nhau không? 10. Tại sao cần phải có Khóa trong quan hệ? 11. Hãy phân biệt khái niệm Khóa và Khoá ngoại trong CSDL. 102
  24. Chương 6 THUẬT TOÁN VÀ NGÔN NGỮ LẬP TRÌNH Chương này đề cập đến phương pháp giải quyết vấn đề bằng máy tính, sau đó đi sâu vào hai nội dung chính: 1) Thuật toán (khái niệm thuật toán, các tính chất, các cách diễn đạt thuật toán, phương pháp thiết kế thuật toán và vấn đề đánh giá thuật toán dựa trên độ phức tạp tính toán ); 2) Ngôn ngữ lập trình (khái niệm, lịch sử phát triển của ngôn ngữ lập trình, trình biên dịch, trình thông dịch và các bước cơ bản khi lập trình). 6.1. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ BẰNG MÁY TÍNH Như ta đã biết, một trong những chức năng cơ bản nhất của máy tính là xử lý thông tin. Tất cả các quá trình xử lý thông tin bằng máy tính đều được thực hiện theo trình tự: VÀO XỬ LÝ RA Đầu tiên máy tính tiếp nhận dữ liệu đầu vào, sau đó thực hiện các thao tác xử lý dữ liệu, rồi trả về kết quả sau xử lý dưới dạng thông tin/dữ liệu ra. Câu hỏi đặt ra là máy tính thực hiện quá trình xử lý thông tin như thế nào? Theo nguyên lý Von Neumann, máy tính hoạt động theo các chương trình (phần mềm) được lập sẵn, việc xử lý thông tin trong máy tính luôn tuân theo nguyên lý này. Với mỗi vấn đề/bài toán đặt ra, để có thể giải quyết được bằng máy tính thì cần phải xây dựng một chương trình máy tính tương ứng. Mỗi chương trình là thể hiện của thuật toán dưới dạng một ngôn ngữ lập trình xác định, thuật toán là thể hiện của phương pháp giải quyết, hướng dẫn các thao tác cụ thể cho máy tính thực hiện để giải quyết vấn đề/bài toán đó. Nhìn chung, phương pháp chung để giải quyết vấn đề/bài toán bằng máy tính được thể hiện theo sơ đồ sau: BÀI TOÁN THUẬT TOÁN CHƯƠNG TRÌNH NGÔN NGỮ MÁY MÁY THỰC HIỆN Từ bài toán đặt ra, cần xác định được những dữ liệu nào cần nhập vào máy tính, những dữ liệu/thông tin nào cần phải đưa ra khi kết thúc quá trình xử lý. Sau đó, cần xây dựng thuật toán hay chính là phương pháp xử lý dữ liệu đầu vào để có được dữ liệu /thông tin ra. Khi đã có thuật toán, cần sử dụng một ngôn ngữ lập trình để xây dựng chương trình máy tính tương ứng. Vì máy tính chỉ có thể hiểu được một ngôn ngữ duy nhất là ngôn ngữ máy nên chương trình muốn thực thi được thì cần phải được dịch sang ngôn ngữ máy. Cuối cùng, máy tính sẽ thực hiện các thao tác xử lý theo chương trình lập sẵn và đưa ra các dữ liệu/thông tin ra theo yêu cầu của bài toán. 6.2. THUẬT TOÁN 6.2.1. Khái niệm thuật toán Thuật toán (thuật giải, algorithm) là một khái niệm quan trọng trong lĩnh vực toán học và tin học. Thuật ngữ algorithm được đưa ra từ khá sớm vào khoảng năm 825, xuất phát từ chữ algoritmi – phiên âm La tinh tên của nhà toán học người Trung Á Al-Khwarizmi (780-850) (ông là tác giả của 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). 103
  25. Đối với việc giải quyết một bài toán, thuật toán có thể hiểu đơn giản là một dãy hữu hạn các thao tác thích hợp để có thể giải quyết bài toán đó. Trong lĩnh vực tin học, thuật toán được xem là một dãy hữu hạn các thao tác, các phép toán có thể thực hiện được theo một trình tự xác định trên một số đối tượng dữ liệu nào đó để đạt được kết quả mong muốn. Lưu ý rằng trong phương pháp giải quyết vấn đề/bài toán bằng máy tính thì đối tượng thực hiện thuật toán là máy tính. Bởi vậy, thuật toán được xây dựng phải bao Hình 6.1. Al-Khwarizmi gồm các thao tác được xác định rõ ràng, đơn giản và thực hiện Con tem phát hành vào ngày được hay nói một cách khác là phải “giao cho máy làm được”. 06/09/1983 tại Liên Xô, nhân dịp kỷ niệm 1200 năm ngày sinh của ông. Với mỗi một bài toán có thể có nhiều cách giải quyết khác nhau. Một thuật toán đơn giản, có độ chính xác cao, được đảm bảo về mặt toán học, lại dễ triển khai thực hiện trên máy tính với thời gian thực hiện nhanh được coi là một thuật toán hiệu quả. Khi xây dựng một thuật toán cần xác định rõ thuật toán đó tác động lên dữ liệu nào, bởi xét cho cùng, thuật toán chỉ phản ánh các phép xử lý, còn đối tượng được xử lý chính là dữ liệu. Căn cứ vào các yêu cầu của bài toán đặt ra cần xác định rõ dữ liệu vào, dữ liệu ra và cả dữ liệu trung gian trong quá trình thực hiện các thao tác xử lý. Việc lựa chọn cấu trúc dữ liệu phù hợp cùng với việc xây dựng được các thuật toán đúng đắn và hiệu quả là những vấn đề mấu chốt khi xây dựng phần mềm. Niklaus Wirth - người sáng lập ra ngôn ngữ lập trình PASCAL đã tổng kết: Thuật toán + Cấu trúc dữ liệu = Chương trình. Ví dụ: Xét bài toán tìm ước số chung lớn nhất của 2 số nguyên dương a và b: Input: 2 số nguyên dương a, b Output: ước số chung lớn nhất của a và b (ký hiệu là (a,b)) Một thuật toán điển hình để giải bài toán này là thuật toán Euclid nguyên bản - thuật toán nổi tiếng được biết đến từ thời Hy Lạp cổ đại (khoảng năm 300 trước công nguyên, trong cuốn Euclid’s Elements). Thuật toán được xây dựng dựa trên tính chất: Nếu a=b thì (a,b) = b; ngược lại nếu a>b thì (a,b) = (a-b,b), nếu a b thì thay thế a bởi a-b, nếu a<b thì Bước 2 8 12 thay thế b bởi b-a. Quay lại Bước 1 8 12 Sai thực hiện bước 1. Bước 2 8 4 Bước 1 8 4 Sai Bước 2 4 4 Bước 1 4 4 Đúng Kết quả: (20,32) = 4 104
  26. 6.2.2. Các tính chất của thuật toán Trong cuốn “Những thuật toán cơ bản” (tập 1 của bộ sách Nghệ thuật lập trình máy tính – The Art of Computer Programming), tác giả Donald Ervin Knuth đã chỉ ra rằng, các thuật toán có 5 đặc trưng cơ bản: Đầu vào, Đầu ra, Tính hữu hạn, Tính xác định, Tính hiệu quả. a. Đầu vào (Input) Một thuật toán có thể không có hoặc có nhiều Hình 6.2. Donald Ervin Knuth dữ liệu đầu vào. Các dữ liệu đầu vào sẽ được xác định Sinh ngày 10/01/1938, Donald Ervin Knuth là một ngay tại thời điểm ban đầu trước khi thuật toán được nhà khoa học máy tính nổi tiếng hiện đang là giáo sư bắt đầu/thực thi. Các dữ liệu này được lấy từ các tập danh dự tại đại học Stanford; ông là tác giả của bộ hợp/đối tượng quy ước. sách “Nghệ thuật lập trình máy tính” (The Art of Computer Programming) - một trong những bộ sách Trong thuật toán Euclid nguyên bản, đầu vào tham khảo được coi trọng nhất trong ngành khoa học là 2 số a, b được lấy từ tập hợp các số nguyên dương. máy tính; ông cũng chính là người đã tạo ra ngành phân tích thuật toán và đã đem lại nhiều cống b. Đầu ra (Output) hiến nền tảng cho ngành khoa học máy tính lý thuyết. Mỗi thuật toán có thể có một hoặc nhiều dữ liệu đầu ra, các dữ liệu đầu ra này có mối liên hệ ràng buộc với dữ liệu đầu vào và chính là kết quả cần đạt được theo yêu cầu của bài toán. Trong thuật toán Euclid nguyên bản, có duy nhất một đầu ra là giá trị b tại thời điểm kết thúc thuật toán, đó chính là ước chung lớn nhất của 2 số a, b ở dữ liệu đầu vào. c. Tính hữu hạn (hay còn gọi là Tính kết thúc/Tính dừng - Finiteness) Thuật toán phải kết thúc sau một số hữu hạn bước thực hiện. Trong thuật toán Euclid nguyên bản, tổng a+b giảm thực sự qua mỗi lần thực hiện bước 2 và bởi vì ước chung nhỏ nhất của 2 số nguyên dương luôn là 1 nên không bao giờ tổng a+b nhỏ hơn 2. Chính vì vậy, thuật toán bắt buộc phải kết thúc sau một số hữu hạn bước thực hiện. d. Tính xác định (Definiteness) Mỗi bước của thuật toán phải được xác định một cách chính xác; các thao tác đưa ra phải được quy định chặt chẽ, rõ ràng cho từng trường hợp. Tính chất này sẽ đảm bảo cho thuật toán luôn trả về kết quả đúng theo yêu cầu mà bài toán đặt ra. Kết quả thực hiện thuật toán chỉ phụ thuộc vào dữ liệu đầu vào, tức là với cùng một dữ liệu đầu vào thì dù là những người hay những máy tính khác nhau thực hiện thì cũng chỉ cho một kết quả đúng duy nhất. Trong thuật toán Euclid nguyên bản, các bước thực hiện 1 và 2 được xác định một cách chặt chẽ, rõ ràng dựa theo tính chất đã có để tìm ước chung lớn nhất của 2 số. Chính vì vậy, kết quả trả về của thuật toán là đúng đắn. e. Tính hiệu quả (Effectiveness) Một thuật toán luôn được mong đợi là có hiệu quả, trong đó các thao tác phải đủ cơ bản mà ngay cả bản thân con người cũng có thể thực hiện chúng một cách chính xác trong một khoảng thời gian hữu hạn. Rõ ràng một thuật toán đơn giản với các thao tác cơ bản và không phải sử dụng quá nhiều dữ liệu trung gian sẽ dễ dàng cho việc cài đặt chương trình, đồng thời đảm bảo cho máy tính có 105
  27. thể thực thi một cách chính xác mà không phải tốn quá nhiều bộ nhớ dùng để lưu trữ và giúp giảm thiểu thời gian thực hiện. Với thuật toán Euclid, thao tác thực hiện chỉ bao gồm các phép so sánh, phép trừ và phép gán giá trị; đây là những thao tác cơ bản mà dù là con người hay máy tính cũng đều có thể dễ dàng thực hiện trong một khoảng thời gian ngắn. Ngoài các đặc trưng trên, trong một số tài liệu còn đề cập đến Tính tổng quát (Generality) của thuật toán, tức là thuật toán có thể áp dụng cho cả một lớp các bài toán đồng dạng chứ không phải chỉ áp dụng cho một trường hợp riêng lẻ với dữ liệu đầu vào cụ thể. Ví dụ, thuật toán Euclid áp dụng được với mọi cặp số a, b nguyên dương chứ không phải chỉ áp dụng cho trường hợp a = 20, b = 32 trong ví dụ minh họa. Tuy nhiên, không phải thuật toán nào cũng có tính tổng quát bởi vì trong thực tế, có nhiều bài toán được đặt ra với các dữ liệu đầu vào hoàn toàn xác định mà không tồn tại một lớp bài toán tương tự. 6.2.3. Cách diễn đạt thuật toán Về cơ bản, có thể diễn đạt thuật toán theo một trong 3 cách sau: a. Liệt kê từng bước bằng ngôn ngữ tự nhiên Đây là phương pháp diễn đạt sử dụng ngôn ngữ tự nhiên liệt kê từng bước thực hiện của thuật toán với các quy tắc, các thao tác cụ thể. Ví dụ: Xem lại thuật toán Euclid tìm ước số chung lớn nhất của 2 số nguyên dương đã đề cập đến ở mục 6.2.1. Khái niệm thuật toán. b. Dùng lưu đồ (sơ đồ khối) Sử dụng các hình khối cơ bản (Bắt đầu, Kết thúc, Khối Input, Khối Output, Khối điều kiện, Khối thao tác) và các cung để thể hiện các thao tác và trình tự thực hiện các thao tác của thuật toán: Bắt đầu + - Khối điều kiện Kết thúc Khối Input Khối thao tác Khối Output Thứ tự xử lý Hình 6.3. Các hình khối và cung để biểu diễn thuật toán 106
  28. Ví dụ: Lưu đồ thuật toán Euclid tìm ước số chung lớn nhất của 2 số nguyên dương được xác định như sau: a, b + a = b - a > b 0 b b:=b-a a:=a -b Hình 6.4. Lưu đồ thuật toán Euclid tìm ước chung lớn nhất của 2 số nguyên dương a, b c. Sử dụng giả mã (pseudo code) Giả mã (hay giả ngôn ngữ lập trình) là một bản mô tả thuật toán ngắn gọn, trong đó sử dụng các cấu trúc điều khiển của một ngôn ngữ lập trình kết hợp linh hoạt với ngôn ngữ tự nhiên và các ký hiệu toán học đơn giản, nhằm diễn tả thuật toán theo cách dễ hiểu nhất đối với người đọc nhưng cũng gần gũi với các ngôn ngữ lập trình để có thể dễ dàng chuyển sang ngôn ngữ lập trình khi cài đặt chương trình. Nhìn chung, không có bất cứ tiêu chuẩn nào cho cú pháp của giả mã, vì một chương trình viết bằng giả mã không phải là một chương trình có thể thực thi được. Thông thường, khi xây dựng giả mã dựa theo cấu trúc của một ngôn ngữ lập trình, ta có thể bỏ đi những chi tiết không cần thiết như các khai báo, các chương trình con và thay thế những đoạn mã đặc biệt bằng ngôn ngữ tự nhiên để thuật toán trở nên dễ hiểu hơn. Ví dụ: Giả mã cho thuật toán Euclid tìm ước số chung lớn nhất của 2 số nguyên dương a, b được viết tựa theo cấu trúc của ngôn ngữ lập trình PASCAL: Nhập a,b While a b do If a>b then thay a bởi a-b else thay b bởi b-a Thông báo ước chung lớn nhất là b Đoạn mã tương ứng được viết bằng ngôn ngữ PASCAL là: Writeln('Nhap 2 so nguyen duong a, b:'); Write('a = '); Readln(a); Write('b = '); Readln(b); While a b then a:=a-b 107
  29. else b:=b-a; Writeln('Uoc chung lon nhat la ',b); 6.2.4. Thiết kế thuật toán a. Mô-đun hoá và việc giải quyết bài toán Các bài toán trong thực tế thường khá phức tạp, yêu cầu phải thực hiện nhiều công việc khác nhau mới có thể đạt được mục tiêu đề ra. Để giải quyết một bài toán như vậy, người ta thường sử dụng chiến thuật “chia để trị” (divide and conquer), tức là chia nhỏ bài toán thành các bài toán nhỏ hơn, dễ giải quyết hơn rồi đi giải quyết từng bài toán nhỏ đó. Nếu coi bài toán ban đầu là mô-đun chính, ta chia nó thành các mô-đun con nhỏ hơn, mỗi mô-đun con này lại có thể được tiếp tục chia thành các mô-đun con nhỏ hơn nữa. Quá trình chia nhỏ bài toán như vậy được gọi là quá trình mô-đun hóa bài toán, theo đó bài toán sẽ được thể hiện theo một mô hình phân cấp dạng như mô hình của bài toán A dưới đây: A a1 a2 a3 a11 a12 a13 a31 a32 Hình 6.5. Mô hình phân cấp của bài toán A Việc giải quyết bài toán tuân theo phương pháp thiết kế top-down (top-down design hay phương pháp thiết kế từ đỉnh xuống). Trước tiên cần phân tích tổng quát bài toán: xuất phát từ các dữ liệu đầu vào và đầu ra, xác định các công việc chính cần thực hiện, sau đó đi sâu phân tích từng công việc và giải quyết từng bước một cách cụ thể, chi tiết hơn. Các thuật toán được thiết kế theo phương pháp top-down cho phép giải quyết các bài toán theo định hướng rõ ràng và là nền tảng cho phương pháp lập trình có cấu trúc. b. Tinh chỉnh từng bước thuật toán Tinh chỉnh từng bước là phương pháp thiết kế thuật toán gắn liền với lập trình. Nó cũng thể hiện quá trình mô-đun hóa và phương pháp thiết kế top-down. Bước đầu thuật toán được minh họa bằng ngôn ngữ tự nhiên thể hiện các công việc chính cần thực hiện, càng ở các bước sau, việc minh họa càng trở nên chi tiết hơn với các thao tác xử lý, các phép toán cần thực hiện được chỉ ra một cách cụ thể, đồng thời ngôn ngữ tự nhiên dùng để minh họa được thay thế dần bởi giả ngôn ngữ và ngày càng tiến gần đến ngôn ngữ lập trình. Trong quá trình thiết kế thuật toán từ ngôn ngữ tự nhiên rồi phát triển thành chương trình máy tính, ngôn ngữ thể hiện dần được chuyển đổi theo sơ đồ: Ngôn ngữ tự nhiên Giả ngôn ngữ Ngôn ngữ lập trình. Xét bài toán sắp xếp phần tử - một bài toán cơ bản trong xử lý thông tin: Cho một dãy gồm n phần tử thuộc kiểu có thứ tự: a1, a2 , an. Hãy đổi chỗ các phần tử trong dãy sao cho dãy sau khi đổi chỗ là có thứ tự (tăng hoặc giảm dần). Với bài toán này, hiện đã có nhiều thuật toán được đưa ra. Ở đây ta xét một thuật toán tương đối đơn giản: thuật toán sắp xếp theo kiểu lựa chọn và xét trong trường hợp sắp xếp tăng. 108
  30. Ý tưởng ban đầu của thuật toán như sau: - Chọn phần tử nhỏ nhất trong dãy nguồn rồi xếp vào vị trí đầu tiên trong dãy đích; - Chọn phần tử nhỏ nhất trong dãy nguồn còn lại (tức phần tử nhỏ thứ hai trong dãy nguồn ban đầu) rồi xếp vào vị trí thứ hai trong dãy đích; - - Lặp lại quá trình này cho đến khi hết dãy nguồn. Một cách tổng quát, với thuật toán này thì tại bước thứ i, ta chọn ra phần tử nhỏ nhất trong dãy nguồn còn lại (tức phần tử nhỏ thứ i trong dãy nguồn ban đầu) rồi xếp vào vị trí thứ i trong dãy đích. Lưu ý rằng, ở đây ta sẽ sử dụng cấu trúc mảng một chiều để lưu trữ dữ liệu, theo đó các phần tử của dãy sẽ được lưu trữ tại các từ máy kế tiếp trong bộ nhớ. Để tiết kiệm bộ nhớ, ta chỉ sử dụng chung một mảng để lưu trữ cả dãy nguồn và dãy đích, tức là thao tác “chọn ra phần tử nhỏ nhất trong dãy nguồn còn lại rồi xếp vào vị trí thứ i trong dãy đích” thực chất là thao tác “chọn ra phần tử nhỏ nhất trong dãy nguồn còn lại rồi đổi chỗ cho phần tử a[i]”. Giả sử định hướng chương trình sau này sẽ được viết bằng ngôn ngữ lập trình PASCAL, khi đó thuật toán trên sẽ được viết bằng giả mã như sau: For i:=1 to n do Begin - Chọn phần tử nhỏ nhất aj trong số các phần tử ai , an - Đổi chỗ aj và ai cho nhau End; Các công việc trong khối Begin End sẽ được làm rõ hơn như sau: - Việc “chọn phần tử nhỏ nhất aj trong số các phần tử ai , an” có thể thực hiện bằng cách: Đầu tiên, coi ai là phần tử nhỏ nhất (j:=i), sau đó lần lượt so sánh phần tử nhỏ nhất với các phần tử ai+1 , an; nếu thấy phần tử nào nhỏ hơn thì coi phần tử đó là phần tử nhỏ nhất mới (j:=chỉ số của phần tử nhỏ nhất mới): j:=i; For k:=i+1 to n do If ak<aj then j:=k; - Việc “đổi chỗ aj và ai cho nhau” muốn thực hiện được cần sử dụng thêm một phần tử trung gian min: min:=aj; aj:= ai; ai:=min; Khi chuyển hoàn toàn thuật toán sang ngôn ngữ lập trình PASCAL, ta có đoạn mã tương ứng như sau: For i:=1 to n-1 do Begin j:=i; 109
  31. For k:=i+1 to n do If a[k] i then Begin min:=a[j]; a[j]:=a[i]; a[i]:=min; End; End; Ví dụ: Cho dãy số ban đầu: 3 6 -2 7 5 Dãy mới được sắp sau từng bước thực hiện thuật toán sắp xếp lựa chọn (i = 1 4): i=1: -2 6 3 7 5 i=2: -2 3 6 7 5 i=3: -2 3 5 7 6 i=4: -2 3 5 6 7 6.2.5. Độ phức tạp của thuật toán và vấn đề đánh giá thuật toán a. Sơ lược về đánh giá thuật toán Trong thực tế, khi một bài toán được đưa ra, vấn đề không phải chỉ là xây dựng được một thuật toán để giải quyết bài toán đó. Thông thường, với cùng một bài toán, có thể có nhiều thuật toán khác nhau, khi đó vấn đề đặt ra là cần phải xác định được đâu là thuật toán tốt nhất dựa theo một số tiêu chí nào đó. Điều đó đưa chúng ta tiếp cận với một bài toán hết sức quan trọng và thú vị của phân tích thuật toán: xác định các đặc trưng hiệu suất thực thi của thuật toán. Một trong những tiêu chí để đánh giá một thuật toán có phải là tốt hay không, đó là thời gian thực hiện thuật toán được thể hiện qua số lần thực hiện các thao tác. Các tiêu chí khác như khả năng thích ứng của thuật toán với các loại máy tính khác nhau, tính đúng đắn, mức độ đơn giản, hình thức của thuật toán, dung lượng bộ nhớ sử dụng để lưu trữ dữ liệu. Tùy theo từng trường hợp, cần áp dụng các tiêu chí đánh giá khác nhau. Xét yêu cầu phân tích tính đúng đắn của thuật toán, một thuật toán hiển nhiên chỉ được chấp nhận khi đưa ra được kết quả đúng với yêu cầu của bài toán. Thông thường, người ta có thể cài đặt chương trình thể hiện thuật toán, sau đó chạy chương trình thử nghiệm với một số bộ dữ liệu đầu vào và so sánh các kết quả thử nghiệm với các kết quả đã biết. Tuy nhiên, phương pháp thử nghiệm này chỉ cho phép khẳng định tính sai chứ chưa đủ để đảm bảo được tính đúng đắn của thuật toán. Một phương pháp khác là sử dụng các công cụ toán học để chứng minh tính đúng đắn của thuật toán nhưng phương pháp này không phải lúc nào cũng dễ dàng. Với yêu cầu phân tích mức độ đơn giản của thuật toán, thông thường chúng ta vẫn mong muốn xây dựng được một thuật toán đơn giản, dễ hiểu, dễ lập trình và chỉnh sửa; nhưng nhiều khi những thuật toán đơn giản lại gây ra sự lãng phí về thời gian và bộ nhớ. Đối với các bài toán cụ thể có số lượng dữ liệu đầu vào nhỏ hoặc thuật toán chỉ được sử dụng một vài lần thì tính đơn giản của thuật toán sẽ được chú trọng. 110
  32. Tuy nhiên với các bài toán phức tạp, có số lượng dữ liệu đầu vào lớn hoặc các bài toán phổ biến, thuật toán được sử dụng nhiều lần thì cần quan tâm chủ yếu đến hai vấn đề: thời gian thực hiện thuật toán và dung lượng bộ nhớ dùng để lưu trữ dữ liệu. Trong đó, tiêu chí về thời gian thực hiện thuật toán được coi là một tiêu chí quan trọng hàng đầu thường được sử dụng khi phân tích, đánh giá thuật toán. Mặc dù tốc độ xử lý dữ liệu của máy tính hiện nay là rất lớn, có thể lên đến hàng tỷ phép tính trên 1 giây (ví dụ: siêu máy tính Blue Gene/L dạng nhỏ của IBM, ra đời năm 2005, có tốc độ xử lý dữ liệu đạt 100 teraflop – tương đương với 100 nghìn tỷ phép tính trên giây; hay siêu máy tính K của tập đoàn Fujitsu – Nhật Bản, ra đời năm 2012, có tốc độ xử lý dữ liệu đạt 10 petaflop – tương đương với 10 triệu tỷ phép tính trên giây) nhưng với cùng một bài toán, ngay cả khi mức độ chênh lệch về số phép toán thực hiện giữa hai thuật toán được đưa ra là ít thì khi thực hiện chúng lặp đi lặp lại hàng triệu lần, mức độ chênh lệch về thời gian thực hiện cũng không phải là nhỏ. Có thể thấy, khi cài đặt thành chương trình máy tính thì thời gian thực hiện của một thuật toán phụ thuộc vào rất nhiều yếu tố: - Số lượng các phép toán sơ cấp: các phép tính số học, các phép tính logic, các phép gán giá trị, chuyển chỗ. Số lượng các phép toán sơ cấp này hiển nhiên sẽ phụ thuộc vào kích thước dữ liệu đầu vào của bài toán (ví dụ, khi dùng cùng 1 thuật toán tính giai thừa, việc tính 4! sẽ cần ít phép toán hơn việc tính 10!). Chính vì vậy, có thể coi thời gian thực hiện của một thuật toán là phụ thuộc vào kích thước dữ liệu đầu vào. - Ngôn ngữ lập trình, chương trình dịch, hệ điều hành, tốc độ xử lý của máy tính. Tuy nhiên, những yếu tố này không đồng đều với mỗi loại máy tính, vì vậy không thể dùng chúng làm căn cứ để đánh giá thời gian thực hiện của thuật toán và thời gian thực hiện của thuật toán không thể biểu diễn bằng các đơn vị thời gian thông thường như giờ, phút, giây. Để đánh giá thời gian thực hiện của một thuật toán, người ta sử dụng “Độ phức tạp tính toán của thuật toán” (gọi tắt là độ phức tạp của thuật toán), đây chính là phương pháp đánh giá chỉ phụ thuộc vào kích thước của dữ liệu đầu vào mà không phụ thuộc vào máy tính và các yếu tố liên quan. b. Độ phức tạp tính toán của thuật toán Thuật toán T sử dụng để giải một bài toán có kích thước dữ liệu đầu vào n sẽ cần thực hiện T(n) các phép toán sơ cấp. T(n) là một hàm của tham số n, chính là đặc trưng cho độ phức tạp tính toán của thuật toán. Độ phức tạp được ký hiệu bởi chữ “O” lớn. Xét định nghĩa tổng quát: Giả sử f(n), g(n) là hai hàm số không âm, đồng biến theo n. Hàm f(n) được xác định là có độ phức tạp tính toán cấp g(n), kí hiệu là O(g(n)), f(n) = O(g(n)), khi và chỉ khi tồn tại các hằng số c và n0 sao cho f(n) ≤ cg(n) khi n ≥ n0. Khi đó, ta nói f(n) có cấp g(n) (thực chất là cấp lớn không vượt quá g(n)). Ví dụ: với f(n) = n2 + 2n + 3, rõ ràng f(n) ≤ n2 + 2n2 + 3n2 = 6n2 với n≥1. Do đó, ta có f(n) = O(n2). Khi viết T(n) = O(g(n)) nghĩa là tốc độ tăng của T(n) khi n không vượt quá tốc độ tăng của g(n). Khi n lớn, g(n) cho ta hình dung độ lớn của T(n) hay nói cách khác, g(n) chính là thước đo độ lớn của T(n). Người ta thường cố gắng ước lượng g(n) sao cho sát với T(n) nhất và có dạng đơn giản nhất. Độ phức tạp tính toán của thuật toán có thể thuộc các dạng dưới đây (được sắp xếp theo mức độ tăng dần): 111
  33. - T(n) = O(1): độ phức tạp cấp hằng số (độ phức tạp bằng với một hằng số xác định, không phụ thuộc vào kích thước dữ liệu đầu vào; ví dụ: các thao tác đơn giản như gán, đọc, viết, so sánh giá trị có độ phức tạp cấp O(1)); - T(n) = O(log2n): độ phức tạp cấp hàm logarit; - T(n) = O(n): độ phức tạp cấp hàm tuyến tính; - T(n) = O(nlog2n): độ phức tạp cấp hàm nlog2n; - T(n) = O(n2), O(n3) , O(nk): độ phức tạp cấp hàm đa thức; - T(n) = O(2n), O(n!), O(nn): độ phức tạp cấp hàm mũ. Một thuật toán có độ phức tạp tính toán cấp hàm mũ (O(2n), O(n!), O(nn)) thì tốc độ thực hiện rất chậm. Một thuật toán có độ phức tạp tính toán từ cấp hàm đa thức trở xuống (O(1), O(log2n), 2 3 k O(n), O(nlog2n), O(n ), O(n ) , O(n )) thì thường chấp nhận được. Những bài toán chưa tìm được thuật toán với độ phức tạp tính toán từ cấp đa thức trở xuống sẽ được xếp vào dạng bài toán khó. c. Xác định độ phức tạp tính toán của thuật toán Đối với các thuật toán phức tạp, việc xác định độ phức tạp tính toán không phải lúc nào cũng dễ dàng. Tuy nhiên, với các thuật toán đơn giản, ta hoàn toàn có thể xác định độ phức tạp của chúng thông qua một số quy tắc sau: Quy tắc cộng: Nếu T1(n) = O(f(n)), T2(n) = O(g(n)), thì T1(n) + T2(n) = O(max{f(n),g(n)}). Ví dụ: Trong một thuật toán có 3 bước, mỗi bước có độ phức tạp tính toán lần lượt là 3 T1(n) = O(n ), T2(n) = O(n), T3(n) = O(nlog2n) thì thời gian thực hiện 3 bước là: 3 3 T1(n) + T2(n) + T3(n) = O(max{n ,n,nlog2n}) = O(n ) Quy tắc nhân: Nếu T1(n) = O(f(n)), T2(n) = O(g(n)) thì: T1(n) . T2(n) = O(f(n).g(n)). Ví dụ: Xét 2 câu lệnh viết bằng ngôn ngữ PASCAL sau: - Câu lệnh 1: For j:=1 to n do x:=x+1; Đây là một câu lệnh lặp với số lần lặp là n, tại mỗi bước lặp, chỉ thực hiện thao tác gán giá trị của biểu thức x+1 cho x, do đó thời gian thực hiện là: T(n) = O(n.1) = O(n) - Câu lệnh 2: For i:=1 to n do For j:=1 to n do x:=x+1; Câu lệnh này gồm 2 vòng lặp lồng nhau, thời gian thực hiện được đánh giá là: T(n) = O(n.n) = O(n2) 112
  34. Quy tắc bỏ hằng số: O(c.f(n)) = O(f(n)) trong đó c là một hằng số. Ví dụ: O(n2/2) = O(n2) Căn cứ vào các quy tắc trên, khi đánh giá độ phức tạp tính toán của thuật toán ta có cũng có thể đánh giá theo một cách đơn giản là chỉ cần quan tâm đến số lần thực hiện phép toán tích cực (active operation - phép toán mà số lần thực hiện nó không ít hơn số lần thực hiện của bất kỳ phép toán nào khác trong thuật toán). Xét thuật toán sắp xếp theo kiểu lựa chọn cho dãy n phần tử a1, a2 , an đã được trình bày ở mục 6.2.4, phần b. Phép toán tích cực là phép toán so sánh a[k] < a[j]. Số lần thực hiện phép so sánh này là: = . Do đó, độ phức tạp của thuật toán này là O(n2). Trong thực tế, nhiều khi không chỉ kích thước dữ liệu đầu vào mà ngay cả tình trạng dữ liệu cũng là một yếu tố gây ảnh hưởng đến thời gian thực hiện thuật toán. Ví dụ, với bài toán sắp xếp dãy số, rõ ràng nếu dãy số đầu vào đã có sẵn thứ tự giống hoặc gần giống với thứ tự mong muốn thì thời gian thực hiện thuật toán sẽ nhỏ hơn thời gian thực hiện thông thường. Nhìn chung, tùy theo tình trạng dữ liệu đầu vào mà ta sẽ có các độ phức tạp khác nhau ứng với từng trường hợp: - Tmax: ứng với trường hợp tình trạng dữ liệu bất lợi nhất cho thuật toán. - Tmin: ứng với trường hợp tình trạng dữ liệu thuận lợi nhất cho thuật toán. - Tavg: ứng với trường hợp tình trạng dữ liệu ở mức độ trung bình. Thông thường, Tavg được dùng để so sánh, đánh giá các thuật toán. Tuy nhiên, trong trường hợp việc xác định thời gian thực hiện trung bình quá khó khăn, có thể đánh giá căn cứ vào trường hợp xấu nhất tức là dùng Tmax. Đặc biệt, với các bài toán thời gian thực, đòi hỏi thời gian trả lời không được vượt quá một giới hạn cho trước thì chỉ có thể dùng ước lượng trong trường hợp xấu nhất Tmax. 6.3. NGÔN NGỮ LẬP TRÌNH 6.3.1. Khái niệm về ngôn ngữ lập trình Ngôn ngữ lập trình (Programming language) hiểu một cách đơn giản là ngôn ngữ dùng để viết các chương trình máy tính. Mỗi ngôn ngữ lập trình bao gồm một hệ thống các ký hiệu, các từ khóa, các từ dành riêng (hay từ vựng) và các quy tắc để viết chương trình (hay cú pháp). Người lập trình sử dụng ngôn ngữ lập trình để viết chương trình thể hiện thuật toán bao gồm một tập hợp các lệnh được viết theo đúng cú pháp, trong đó, mỗi lệnh mang một ý nghĩa nhất định (còn gọi là ngữ nghĩa), chỉ dẫn cho máy tính thực hiện một công việc cụ thể. 6.3.2. Lịch sử phát triển của ngôn ngữ lập trình Trong lịch sử phát triển, ngôn ngữ lập trình có thể chia ra làm 3 loại chính: a. Ngôn ngữ máy (Mã máy - Machine language hay Machine code) Cùng với sự ra đời của máy tính điện tử, ngôn ngữ máy được xem như là ngôn ngữ nền tảng của bộ vi xử lý. Đây là ngôn ngữ duy nhất mà bộ vi xử lý có thể nhận biết và thực hiện một cách trực tiếp, tất cả các chương trình máy tính được viết bằng các ngôn ngữ khác đều phải được dịch sang ngôn ngữ máy trước khi thực thi. Các lệnh của ngôn ngữ máy được viết ở dạng nhị phân hoặc biến thể của chúng trong hệ 16. Ưu điểm của ngôn ngữ máy là cho phép người lập 113
  35. trình viết các chương trình điểu khiển trực tiếp máy tính thông qua các lệnh máy và các chương trình được thực hiện nhanh chóng do không phải thực hiện bước dịch chương trình. Tuy nhiên, nhược điểm của nó là các lệnh máy dài và khó nhớ, chương trình được viết thường cồng kềnh, vừa mất thời gian khi viết vừa khó khăn cho việc đọc, phát hiện lỗi và hiệu chỉnh chương trình. Ngoài ra, vì tập lệnh của ngôn ngữ máy phụ thuộc vào loại bộ vi xử lý nên một chương trình chỉ chạy được trên những máy tính có cùng loại bộ vi xử lý mà thôi. Trong số các ngôn ngữ lập trình, ngôn ngữ máy được xem là một ngôn ngữ lập trình bậc thấp (thế hệ thứ nhất). b. Hợp ngữ (Assembly) Ra đời từ đầu những năm 1950, hợp ngữ được đưa ra nhằm khắc phục các nhược điểm của ngôn ngữ máy. Về cơ bản, hợp ngữ có các cấu trúc lệnh rất giống với ngôn ngữ máy nhưng điểm khác biệt lớn nhất là việc cho phép viết lệnh dưới dạng mã chữ thay vì mã nhị phân. Các mã lệnh ở dạng chữ thường là những từ tiếng Anh viết tắt có ý nghĩa rõ ràng, dễ nhớ. Ngoài ra, hợp ngữ cũng cho phép định địa chỉ hình thức, nghĩa là một vị trí bộ nhớ trong máy tính có thể được tham chiếu tới thông qua một cái tên hoặc ký hiệu, thay vì phải sử dụng địa chỉ thực sự của nó dưới dạng mã nhị phân như trong ngôn ngữ máy. Ví dụ, lệnh ADD AX, BX cho phép cộng (addition) số liệu trong các thanh ghi AX, BX với nhau, kết quả để trong thanh ghi AX. Các chương trình hợp ngữ được chuyển sang mã máy thông qua một chương trình đặc biệt gọi là trình hợp dịch (assembler). Mặc dù tương đối dễ dùng hơn mã máy nhưng hợp ngữ vẫn được xem là một ngôn ngữ lập trình bậc thấp (thế hệ thứ hai) bởi vì nó vẫn còn rất gần với tầng thiết kế máy tính, các chương trình được viết bằng ngôn ngữ này luôn có sự liên quan chặt chẽ đến kiến trúc máy tính. Hiện nay, ngôn ngữ này có phạm vi sử dụng khá hẹp, chủ yếu chỉ dùng khi cần lập trình thao tác trực tiếp với phần cứng máy tính hoặc làm các công việc không thường xuyên, thường là trong các trình điều khiển (driver), các hệ nhúng bậc thấp (low-level embedded system) và các hệ thống thời gian thực (real-time system). c. Ngôn ngữ lập trình bậc cao (Ngôn ngữ thuật toán – High level programming language) Năm 1957, sự ra đời của ngôn ngữ lập trình bậc cao FORTRAN đã đánh dấu sự khởi đầu cho cuộc cách mạng của ngôn ngữ máy tính, kể từ đó cho đến nay đã có hàng trăm ngôn ngữ lập trình bậc cao ra đời, à ngôn ngữ rất gần gũi với ngôn ngữ tự nhiên và ngôn ngữ toán học, các ngôn ngữ lập trình bậc cao thường sử dụng hệ thống ký hiệu phong phú với các ký hiệu số, các ký hiệu chữ, các ký hiệu toán học và nhiều ký hiệu thông dụng khác, cùng với các từ khóa tiếng Anh đơn giản, các cấu trúc lệnh chặt chẽ, rõ ràng và mang ý nghĩa thực tế. Chính vì vậy, các ngôn ngữ lập trình bậc cao thường dễ học, dễ đọc, dễ viết và hiệu chỉnh chương trình, vừa cho phép thể hiện chính xác các thuật toán lại vừa có tính độc lập cao, ít phụ thuộc vào phần cứng máy tính. Người ta còn gọi ngôn ngữ lập trình bậc cao là ngôn ngữ thuật toán. Cũng giống như hợp ngữ, các chương trình viết bằng các ngôn ngữ lập trình bậc cao muốn máy tính thực thi được thì cần phải được dịch sang ngôn ngữ máy nhờ các chương trình dịch. Ví dụ về một số ngôn ngữ lập trình bậc cao như: FORTRAN, PASCAL, C, C++, JAVA, PHP Hiện nay, với hàng loạt các ngôn ngữ lập trình được đưa ra, việc phân loại ngôn ngữ lập trình chỉ mang tính tương đối. Tùy theo từng mục đích mà chúng ta có thể phân loại ngôn ngữ lập trình theo những cách khác nhau. Ví dụ: phân loại theo mức trừu tượng, chúng ta có nhóm ngôn ngữ lập trình bậc thấp và nhóm ngôn ngữ lập trình bậc cao; phân loại theo hình thức lập trình, có nhóm ngôn ngữ khai báo (LIST, PROLOG ) và nhóm ngôn ngữ mệnh lệnh (PASCAL, C ); phân loại theo các họ, có họ ngôn ngữ máy và hợp ngữ, họ ngôn ngữ cổ điển (ALGOL, PASCAL, C ), họ ngôn ngữ hàm (LISP ), họ ngôn ngữ logic (PROLOG ), họ ngôn ngữ hướng đối tượng (C++, JAVA ), họ ngôn ngữ truy vấn (SQL ). Dưới đây là một số ngôn ngữ điển hình trong lịch sử phát triển của ngôn ngữ lập trình: 114
  36. - Giai đoạn từ năm 1957 đến những năm đầu 1960: + Ngôn ngữ FORTRAN (FORmula TRANslator): được công bố vào năm 1957 bởi công ty IBM, FORTRAN được thiết kế như là một ngôn ngữ lập trình dành cho các nhà khoa học, các kỹ sư và các nhà toán học; ngôn ngữ này được xem như là ngôn ngữ lập trình cấp cao đầu tiên và được chú ý bởi khả năng diễn đạt và tính toán các phương trình toán học một cách dễ dàng. + Ngôn ngữ ALGOL (ALGOrithmetic Language): được công bố bởi một ủy ban quốc tế vào những năm cuối 1950 trong một báo cáo có tựa đề ALGOL 58, sau đó được phát triển tiếp thành ALGOL 60, ALGOL 68; với cấu trúc điều khiển hiện đại, ALGOL được sử dụng phổ biến trong các ứng dụng khoa học và toán học. + Ngôn ngữ LISP (LISt Processing): được John McCarthy đề xuất vào năm 1958 tại viện công nghệ Massachusetts (MIT) - Mỹ; LISP là ngôn ngữ lập trình hàm đầu tiên, được xem như một ngôn ngữ xử lý danh sách. + Ngôn ngữ COBOL (COmmon Business Oriented Language): được phát triển bởi một hội đồng bao gồm các đại diện từ các tổ chức chính phủ, quốc phòng và doanh nghiệp nước Mỹ, trong đó Grace Hopper - làm việc trong Hải quân Mỹ - được mệnh danh là “mẹ đẻ của COBOL”; với khả năng xử lý các tệp tin lớn và thực hiện những phép tính thương mại tương đối đơn giản, COBOL đã từng là một trong những ngôn ngữ được sử dụng rộng rãi nhất cho các ứng dụng thương mại. - Năm 1963, ngôn ngữ BASIC, viết tắt của cụm từ Beginner's All-purpose Symbolic Instruction Code, được phát triển bởi John Kermeny và Thomas Kurtz tại trường đại học Dartmouth; ban đầu, BASIC được thiết kế là một ngôn ngữ lập trình đơn giản, có tính tương tác để các sinh viên học tập và sử dụng, sau đó ngôn ngữ này đã nhanh chóng trở thành một trong những ngôn ngữ lập trình thông dụng. - Năm 1970, ngôn ngữ PASCAL (lấy theo tên của nhà toán học/vật lý học người Pháp Blaise Pascal), được phát triển bởi Niklaus Wirth, một nhà khoa học máy tính tại Zurich, Thụy Sĩ; ban đầu, PASCAL được phát triển cho mục đích giảng dạy về lập trình cấu trúc, sau đó phiên bản thương mại của nó đã được phát triển rộng rãi trong những năm 80. - Năm 1972, ngôn ngữ C, được phát triển bởi Dennis Ritchie tại phòng thí nghiệm Bell, Mỹ; ban đầu, C được thiết kế như là một ngôn ngữ dùng để viết các phần mềm hệ thống phục vụ cho hệ thống Unix, nhưng sau đó, nhu cầu dùng C để phát triển nhiều loại phần mềm, kể cả các ứng dụng thương mại đã tăng lên nhanh chóng; nhiều ngôn ngữ lập trình hiện nay được phát triển từ C như: JAVA, JAVASCRIPT, PERL, PHP, PYTHON. - Năm 1983, ngôn ngữ C++, được phát triển bởi Bjarne Stroustrup tại phòng thí nghiệm Bell, Mỹ; C++ được nâng cao từ ngôn ngữ C, với sự cải tiến về các lớp, hàm ảo và template; ngôn ngữ C++ được sử dụng trong nhiều ứng dụng thương mại, phần mềm nhúng, phần mềm client/server Cũng trong năm 1983, ngôn ngữ OBJECTIVE C (lập trình hướng đối tượng mở rộng từ C), được phát triển bởi Bradcox và Tomlove tại công ty Stepstone; đây là ngôn ngữ mở rộng từ C, bổ sung thêm chức năng message-passing cho phép truyền dữ liệu từ tiến trình này sang tiến trình khác trên máy tính thông qua ngôn ngữ SMALLTALK, ngôn ngữ này thường được dùng để lập trình trong hệ điều hành iOS và OS X của Apple. - Năm 1987, ngôn ngữ PERL (Practical Extraction and Report Language), được phát triển bởi Larry wall, tại công ty Unisys. PERL được tạo ra để xử lý các báo cáo trong hệ thống Unix; hiện nay, ngôn ngữ này được biết đến như là một ngôn ngữ lập trình mạnh mẽ và có tính 115
  37. linh hoạt cao, được sử dụng trong nhiều ứng dụng cơ sở dữ liệu, quản lý hệ thống, lập trình mạng, lập trình đồ họa - Năm 1991, ngôn ngữ PYTHON (đặt tên theo đoàn hài kịch Anh MONTY PYTHON), được phát triển bởi Guido Van Rossum, làm việc tại công ty CWI; PYTHON được tạo ra để hỗ trợ các dạng ngôn ngữ khác và khá thú vị khi sử dụng, thường được dùng trong lập trình ứng dụng web, phát triển phần mềm, bảo mật thông tin. - Năm 1993, ngôn ngữ RUBBY, được phát triển bởi Yukihiro Matsumoto; đây là ngôn ngữ được đưa ra với mục đích dùng trong giảng dạy, chịu ảnh hưởng của nhiều ngôn ngữ khác như PERL, ADA, LISP, SMALLTALK; hiện nay, ngôn ngữ này thường được sử dụng trong phát triển ứng dụng web. - Năm 1995, ngôn ngữ JAVA, được phát triển bởi Jame Gosling, làm việc tại công ty Sun Microsystems; JAVA được tạo ra cho một dự án truyền hình tương tác và hiện đã trở thành ngôn ngữ lập trình được sử dụng phổ biến nhất trên thế giới, thường dùng trong lập trình mạng, phát triển ứng dụng web, phát triển phần mềm, phát triển giao diện đồ họa người dùng. Cũng trong năm 1995, ngôn ngữ PHP (trước đây có nghĩa là Personal HomePage – trang chủ cá nhân, hiện nay được hiểu theo nghĩa là Hypertext PreProcessor – Bộ tiền xử lý siêu văn bản), được phát triển bởi Rasmus Lerdorf; PHP là ngôn ngữ nguồn mở hiện được sử dụng rất rộng rãi để xây dựng, bảo trì các trang web động, phát triển các server Cũng trong năm 1995, ngôn ngữ JAVASCRIPT, được phát triển bởi Brendan Eich, làm việc tại công ty NetScape; là ngôn ngữ được tạo ra để mở rộng các chức năng của trang web, ứng dụng trong phát triển web động, xử lý tài liệu dạng pdf, công cụ màn hình Ngoài ra còn có nhiều ngôn ngữ lập trình khác như: - APL (AProgramming Language), một ngôn ngữ khá mạnh, dễ dùng, rất tốt trong việc xử lý dữ liệu được lưu dưới dạng bảng (ma trận). - FORTH, tương tự như ngôn ngữ C, cho phép tạo mã chương trình nhanh và hiệu quả, ban đầu được phát triển để điều khiển kính viễn vọng không gian. - LOGO, chủ yếu được biết đến như là một công cụ trong giảng dạy khả năng giải quyết vấn đề. - MODULA-3, tương tự như PASCAL, sử dụng chủ yếu để phát triển các phần mềm hệ thống. - PILOT (Programmed Inquiry Learning Or Teaching), được sử dụng bởi những người công tác trong lĩnh vực giảng dạy để viết các chương trình hướng dẫn CAD. - PL/I (Programming Language/One), ngôn ngữ thương mại và khoa học phối hợp nhiều chức năng của FORTRAN và COBOL. - PROLOG (PROgramming LOGic), được sử dụng trong trí tuệ nhân tạo. - RPG (Report Program Generator), cho phép sử dụng các mẫu đặc biệt để giúp người dùng xác định dữ liệu vào, dữ liệu ra và các yêu cầu tính toán của một chương trình. - ADA (lấy theo tên của Augusta Ada Bryon, người được xem là đã viết chương trình đầu tiên), được thiết kế để phục vụ cho việc viết, bảo trì các chương trình lớn trong một khoảng thời gian dài. 116
  38. 6.3.3. Trình biên dịch và trình thông dịch Máy tính chỉ hiểu được một ngôn ngữ duy nhất là ngôn ngữ máy. Bởi vậy, trước khi được thực thi, các chương trình viết bằng các ngôn ngữ lập trình không phải là ngôn ngữ máy (chương trình nguồn) phải được dịch sang ngôn ngữ máy nhờ các chương trình dịch. Các chương trình dịch có thể chia làm hai loại: trình thông dịch và trình biên dịch. Trình thông dịch (Interpreter): Sử dụng kỹ thuật thông dịch, dịch từng câu lệnh trong chương trình nguồn được viết bằng ngôn ngữ lập trình bậc cao sang ngôn ngữ máy để máy tính “hiểu” và thực thi ngay câu lệnh đó mà không lưu lại đoạn mã máy tương ứng, sau đó chuyển sang dịch câu lệnh tiếp theo. Với kỹ thuật thông dịch, không có bất kỳ tệp mã đối tượng (tệp mã máy tương ứng với chương trình nguồn) nào được tạo ra. Mỗi lần thực hiện chương trình là một lần chương trình nguồn được thông dịch lại sang ngôn ngữ máy. Thậm chí, nếu một câu lệnh trong chương trình được thực hiện lặp đi lặp lại nhiều lần thì mỗi lần thực hiện lệnh là một lần phải dịch lại câu lệnh đó. Lợi thế của trình thông dịch là cho phép dịch và thực hiện ngay câu lệnh mà không cần phải đợi dịch xong toàn bộ chương trình, ngoài ra trình thông dịch cũng giúp cho việc dò tìm lỗi dễ dàng hơn vì nó chỉ ra chính xác câu lệnh nào chứa lỗi. Nhìn chung, với việc dịch và thực hiện từng câu lệnh, trình thông dịch là thích hợp trong môi trường cần có sự đối thoại giữa con người và hệ thống. Một số ngôn ngữ lập trình có sử dụng trình thông dịch như: BASIC, VISUAL BASIC, PERL, PYTHON Trình biên dịch (Compiler): Sử dụng kỹ thuật biên dịch, dịch toàn bộ chương trình nguồn được viết bằng ngôn ngữ lập trình bậc cao sang ngôn ngữ máy và tạo ra tệp mã đối tượng tương ứng, sau đó bộ liên kết sẽ liên kết các đối tượng thành phần với nhau và tạo ra tệp thực thi, cả tệp đối tượng và tệp thực thi đều được nạp vào máy tính để sử dụng khi cần. Trong quá trình biên dịch, trình biên dịch sẽ phân tích từ vựng và cú pháp của các câu lệnh, nếu trong chương trình nguồn có lỗi về mặt cú pháp thì trình biên dịch sẽ thông báo danh sách tất cả các lỗi để lập trình viên chỉnh sửa, tệp mã đối tượng chỉ được tạo ra khi chương trình nguồn không còn bất kỳ lỗi cú pháp nào. Mỗi lần thực hiện chương trình chỉ cần sử dụng chương trình thực thi đã được tạo trước đó mà không cần phải tiến hành biên dịch lại chương trình nguồn. Vì vậy, việc sử dụng trình biên dịch là thích hợp với các chương trình có tính ổn định và được thực hiện nhiều lần. Thông thường, mỗi ngôn ngữ lập trình bậc cao đều có một trình biên dịch tương ứng, ví dụ: PASCAL, C, C++ 6.3.4. Các công việc của người lập trình Về cơ bản, để tạo ra một chương trình bằng ngôn ngữ lập trình bậc cao, người lập trình cần thực hiện các công việc theo trình tự sau: Bước 1: Soạn thảo chương trình Dựa vào thuật toán và ngôn ngữ lập trình để viết chương trình, sau đó sử dụng một trình soạn thảo chuyên dụng để nhập nội dung chương trình, lưu tệp chương trình với phần mở rộng tên tệp phù hợp với ngôn ngữ lập trình sử dụng, ví dụ: phần mở rộng tên tệp là .pas cho tệp chương trình viết bằng ngôn ngữ PASCAL, .c cho tệp chương trình viết bằng ngôn ngữ C hay .cpp cho tệp chương trình viết bằng ngôn ngữ C++ Tệp chương trình này được gọi là tệp mã nguồn (source code). Bước 2: Biên dịch chương trình Sử dụng trình biên dịch (compiler) thích hợp để biên dịch tệp chương trình nguồn sang tệp mã máy tương ứng (tệp đối tượng hay object code). Nếu chương trình nguồn có một số lỗi nào đó về mặt cú pháp thì trình biên dịch sẽ thông báo danh sách tất cả các lỗi, khi đó cần quay lại bước 1, sử dụng trình soạn thảo để chỉnh sửa chương trình nguồn. Khi tệp đối tượng đã được 117
  39. tạo, bộ liên kết (linker) sẽ thực hiện việc liên kết các đối tượng thành phần với nhau và tạo ra tệp thực thi (executable code) cho chương trình. Bước 3: Chạy thử chương trình Chạy chương trình (kích hoạt tệp thực thi), nhập các dữ liệu đầu vào (các dữ liệu mẫu dùng để kiểm tra) và kiểm tra các kết quả được đưa ra. Nếu kết quả thu được không đúng hoặc có lỗi khi thực thi chương trình thì cần kiểm tra, chỉnh sửa lại thuật toán, rồi quay lại bước 1 để chỉnh sửa lại chương trình. Thông thường, trong các môi trường phát triển tích hợp (IDE - Integrated Development Environment) có tích hợp sẵn trình soạn thảo, trình biên dịch, bộ liên kết, trình gỡ rối và cho phép chạy thử chương trình. Tuy nhiên, người lập trình cũng có thể sử dụng một trình soạn thảo chuyên dụng, độc lập để soạn thảo chương trình nguồn; sau đó sử dụng một trình biên dịch thích hợp để biên dịch rồi chạy chương trình bằng cách kích hoạt tệp thực thi đã được tạo. Một trình soạn thảo được sử dụng khá phổ biến hiện nay là Notepad++, đây là một phần mềm miễn phí cho phép soạn thảo với nhiều ngôn ngữ lập trình khác nhau, phù hợp với các cá nhân thường xuyên phải làm việc cùng lúc với nhiều ngôn ngữ lập trình. Ví dụ 1: Viết chương trình tìm ước số chung lớn nhất của 2 số nguyên dương, chương trình viết bằng ngôn ngữ PASCAL, sử dụng phần mềm Free Pascal (IDE, version 2.6.2). Bước 1: Khởi động phần mềm Free Pascal, sử dụng trình soạn thảo nhập nội dung chương trình nguồn, sau đó lưu tệp mã nguồn dưới dạng .pas: Hình 6.6. Soạn thảo chương trình tìm ước chung lớn nhất với Free Pascal Bước 2: Nhấn tổ hợp phím Alt+F9 để biên dịch chương trình. Khi chương trình nguồn không có lỗi cú pháp, hệ thống sẽ đưa ra thông báo quá trình biên dịch đã thành công: Hình 6.7. Biên dịch chương trình tìm ước chung lớn nhất 118
  40. Bước 3: Nhấn tổ hợp phím Ctrl+F9 để chạy thử chương trình: Hình 6.8. Chạy thử chương trình tìm ước chung lớn nhất Sử dụng trình quản lý ổ đĩa Windows Explorer, kiểm tra trong thư mục lưu tệp mã nguồn, ta sẽ thấy bên cạnh tệp mã nguồn UCLN.pas được tạo ở bước 1, sẽ có thêm các tệp đối tượng UCLN.o và tệp thực thi UCLN.exe được tạo ở bước 2. Hình 6.9. Các tệp được tạo sau bước biên dịch chương trình tìm ước chung lớn nhất Những lần tiếp theo khi muốn chạy chương trình tìm ước chung lớn nhất của hai số nguyên dương, ta chỉ cần kích hoạt tệp UCLN.exe đã được lưu trữ. Ví dụ 2: Viết chương trình cho bài toán sắp xếp dãy số nguyên a1, a2 , an theo chiều tăng dần, sử dụng thuật toán lựa chọn (chương trình viết bằng ngôn ngữ lập trình PASCAL, sử dụng phần mềm Notepad++ để soạn thảo và trình biên dịch Free Pascal Compiler để biên dịch chương trình). Bước 1: Sử dụng phần mềm Notepad++ soạn thảo nội dung chương trình nguồn, sau đó lưu tệp mã nguồn dưới dạng .pas: 119
  41. Hình 6.10. Soạn thảo chương trình sắp xếp dãy số với trình soạn thảo Notepad++ Bước 2: Biên dịch chương trình, sử dụng trình biên dịch Free Pascal Compiler. Khi chương trình nguồn không có lỗi cú pháp, hệ thống sẽ đưa ra thông báo quá trình biên dịch đã thành công, tệp đối tượng và tệp thực thi đã được tạo: Hình 6.11. Biên dịch chương trình sắp xếp dãy số 120
  42. Bước 3: Kích hoạt tệp thực thi để chạy thử chương trình: Hình 6.11. Chạy thử chương trình sắp xếp dãy số CÂU HỎI VÀ BÀI TẬP 1. Hãy trình bày phương pháp giải quyết vấn đề bằng máy tính. 2. Thuật toán là gì? Hãy trình bày những đặc trưng cơ bản của thuật toán. 3. Có mấy cách để diễn đạt một thuật toán, là những cách nào? 4. Hãy thiết kế thuật toán cho các bài toán sau: a. Cho n là một số nguyên dương, n>1, hãy tính giá trị n! b. Cho n là một số nguyên dương, n>1, hãy tính tổng S theo công thức: S = 1/2 + 1/3 + + 1/n c. Cho dãy n số nguyên a1, a2 , an (n>1). Hãy sắp xếp dãy số đã cho theo chiều giảm dần. 5. Nêu khái niệm độ phức tạp tính toán của thuật toán. Hãy xác định độ phức tạp tính toán cho các thuật toán đã xây dựng ở câu 4. 6. Ngôn ngữ lập trình là gì? Trong lịch sử phát triển, ngôn ngữ lập trình có thể chia làm mấy loại, là những loại nào? 7. Chương trình dịch dùng để làm gì? Có những loại chương trình dịch nào? 8. Khi lập trình để giải quyết một bài toán cụ thể, các lập trình viên cần thực hiện các công việc nào? 121
  43. Chương 7 CÁC VẤN ĐỀ XÃ HỘI CỦA CÔNG NGHỆ THÔNG TIN Công nghệ thông tin ngày nay đã xâm nhập vào mọi lĩnh vực trong đời sống thường ngày của con người từ cách thức chúng ta làm việc, tương tác, trao đổi với đồng nghiệp, bạn bè và người thân tới những hoạt động thuần túy mang tính cá nhân, chúng ta thực sự đang sống trong thời đại thông tin với những cư xử gắn liền với hạ tầng công nghệ. Song hành với những hình thức cư xử mới này, tất yếu sẽ xuất hiện những chuẩn mực đạo đức mới cũng như những loại hình phạm tội mới và những chế tài pháp luật mới. Do đó, việc nắm được những kiến thức cơ bản nhằm nhận biết và phân biệt cũng như khả năng tự bảo vệ trước các hình thức phạm tội mới cũng như các chế tài pháp luật nhằm hạn chế các hành vi phạm tội mới này là vô cùng cần thiết. 7.1. CÁC TÀI NGUYÊN CÓ THỂ BỊ XÂM PHẠM 7.1.1. Nội dung thông tin Thông tin vốn đã quan trọng, thì ngày nay trong xã hội thông tin, lại càng trở nên quan trọng hơn bao giờ hết. Với sự tiện lợi trong lưu trữ, vận chuyển và chia sẻ, thông tin ngày càng được đưa vào nhiều hơn trong các hệ thống công nghệ thông tin. Từ những loại thông tin có tính chất công cộng tới những loại thông tin nghiệp vụ, thông tin bí mật chiến lược, tới những thông tin hết sức riêng tư, tất cả đều đã được đẩy vào các hệ thống thông tin. Cũng từ đây, những vấn đề tội phạm liên quan tới nội dung thông tin xuất hiện. Nội dung thông tin bị tấn công thường là mục tiêu chiếm đoạt hoặc phá hủy thông tin. Chiếm đoạt thông tin là có được nội dung thông tin mà bản thân kẻ tấn công không có thẩm quyền để xem thông tin đó; Phá hủy thông tin là việc xóa bỏ hoặc thay đổi thông tin một cách trái phép. Các tấn công vào nội dung thông tin gây hậu quả vô cùng nghiêm trọng tới chính phủ, tổ chức và cá nhân. Gần đây Edward Snowden làm rò rỉ thông tin bí mật của cục tình báo Mỹ là một ví dụ điển hình ở mức chính phủ. Với tổ chức, công ty, việc để lộ hay phá hủy những thông tin chiến lược quan trọng, các bí quyết sản xuất, chế biến sẽ ảnh hưởng lớn tới sự tồn vong của tổ chức, công ty đó. Với cá nhân, việc lộ những thông tin riêng tư không chỉ gây khó chịu cho cá nhân mà thậm chí còn dẫn tới những hậu quả nghiêm trọng cho tính mạng của cá nhân đó. Như vậy, bảo vệ nội dung thông tin trở thành một vấn đề vô cùng quan trọng nhằm đảm bảo cuộc sống bình thường của mọi người trong xã hội thông tin. 7.1.2. Tài nguyên hạ tầng công nghệ thông tin Xã hội thông tin ngày càng đẩy con người phụ thuộc vào hạ tầng công nghệ thông tin. Từ các giao dịch tài chính, nghiệp vụ tới các giao tiếp thông thường trong đời sống hàng ngày, tất thảy đều được thực hiện dựa trên hạ tầng công nghệ thông tin. Do vậy, việc hạ tầng này sụp đổ hoặc rơi vào trạng thái quá tải không thể đáp ứng, sẽ dẫn tới những hậu quả khôn lường. Tấn công trên hạ tầng công nghệ thông tin thường tập trung vào hạ tầng tính toán và lưu trữ. Đối tượng tấn công sẽ tìm mọi cách để tiêu thụ hết tài nguyên tính toán và lưu trữ khiến hạ tầng công nghệ thông tin bị quá tải, thậm chí bị sụp đổ. 7.1.3. Định danh người dùng Trong môi trường mạng, nhiều khi chúng ta sử dụng một định danh nhất định gắn với bản thân chúng ta trong đời sống thực. Định danh này làm cơ sở cho những hoạt động giao tiếp và giao dịch trong đời sống thực có thể được đưa vào các hệ thống thông tin. Nhờ có định danh này 122
  44. mà thông tin được trao đổi có tính tin cậy. Do đó, việc bị đánh cắp định danh hay giả mạo định danh sẽ gây ra những hậu quả khôn lường. Trước tiên sẽ là đánh mất uy tín của người sử dụng định danh đó, sau đó là những hiểm họa với bản thân người sở hữu định danh và các cá nhân tổ chức thực hiện giao dịch liên quan tới định danh đó. 7.2. CÁC HÌNH THỨC TẤN CÔNG Ở mục trên, chúng ta đã thấy được những loại tài nguyên thông tin có thể bị xâm phạm trong các hệ thống thông tin. Ở mục này, chúng ta sẽ xem xét những kẽ hở cũng như các cách thức mà kẻ xấu thực hiện tấn công vào các tài nguyên thông tin. 7.2.1. Tận dụng các lỗ hổng phần mềm Mặc dù được xây dựng với mục tiêu tốt đẹp, các sản phẩm phần mềm vẫn có thể chứa đựng những lỗi hoặc những điểm yếu mà kẻ xấu có thể lợi dụng để thực hiện các hành vi xâm phạm tới các tài nguyên thông tin kể trên. Ngày nay, hệ thống máy tính thường được cài đặt một lượng lớn các sản phẩm phần mềm để phục vụ các nhu cầu sử dụng khác nhau, do đó nguy cơ tiềm ẩn các lỗ hổng trong các hệ thống máy tính là rất lớn. Những lỗ hổng có thể đến từ bản thân thiết kế của sản phẩm, những lỗi lập trình trong quá trình phát triển, hay những lỗi trong quá trình cài đặt, cấu hình và vận hành sản phẩm. Các lỗ hổng cũng có thể đến từ hạ tầng đóng vai trò làm nền cho sản phẩm như hệ điều hành, hệ quản trị cơ sở dữ liệu hay những công cụ, thư viện được sử dụng trong quá trình phát triển sản phẩm phần mềm như ngôn ngữ lập trình, trình biên dịch. Những lỗ hổng đến từ bản thân thiết kế của sản phẩm hay logic chức năng của sản phẩm được gọi là những lỗ hổng logic ứng dụng, chúng rất đa dạng và biến đổi tùy thuộc vào bản thân ứng dụng, do đó rất khó để phát hiện. Để loại bỏ những lỗ hổng logic, ứng dụng cần sự tham gia của chuyên gia an ninh, ứng dụng không thể sử dụng các công cụ tự động. Ngược lại, những lỗ hổng đến từ hạ tầng, công cụ và thư viện có thể được phát hiện dễ dàng hơn. Thông thường dựa trên những lỗ hổng đã được biết trên hạ tầng, công cụ và thư viện, một ứng dụng tự động có thể thực hiện một tìm kiếm một cách có hệ thống để phát hiện các lỗ hổng đó. Mặc dù sự phát triển mạnh mẽ của kỹ nghệ phần mềm cũng như sự hỗ trợ của các công cụ kiểm thử hiện đại, sản phẩm phần mềm vẫn có thể tồn tại những lỗ hổng. Do đó, khai thác lỗ hổng phần mềm vẫn là một phương pháp hữu hiệu nhằm tấn công vào các hệ thống thông tin. 7.2.2. Sử dụng các phần mềm độc hại Phần mềm độc hại là phần mềm được xây dựng với mục đích xấu, được sử dụng như công cụ để tấn công vào các hệ thống thông tin. Ở cách thức tấn công này, phần mềm độc hại phải được cài đặt lên hệ thống máy tính của người dùng và phải được kích hoạt để chạy. Thông thường, phần mềm độc hại được cài đặt bởi tin tặc thông qua những lỗ hổng phần mềm hoặc trực tiếp bởi người sử dụng. Phần mềm độc hại có thể được kích hoạt trực tiếp bởi người sử dụng hoặc thông qua những lệnh khởi động của hệ điều hành. Phần mềm độc hại phát triển mạnh về số lượng và sự đa dạng, tính tới năm 2008 số lượng phần mềm độc hại đã vượt mốc 1 triệu, theo báo cáo của GData, chỉ trong nửa đầu năm 2010, đã phát hiện tới 1.017.208 phần mềm độc hại mới, con số này lớn hơn một nửa tổng số phần mềm độc hại năm 2009. Phần mềm độc hại thực sự trở thành mối nguy hại lớn với các hạ tầng công nghệ thông tin. Dưới đây chúng ta xem xét một số loại phần mềm độc hại chính. a. Virus máy tính Virus máy tính (thường được người sử dụng gọi tắt là virus hay vi-rút) là những chương trình hoặc đoạn mã lệnh được thiết kế để bám vào một tệp tin nào đó. Virus sẽ thi hành khi 123
  45. những thao tác nhất định xảy ra trên tệp tin mà nó lây nhiễm được thực hiện, chẳng hạn như người sử dụng yêu cầu hệ điều hành thi hành tệp tin đó hay mở tệp tin đó bằng một trình ứng dụng nào đó. Virus thi hành sẽ thực hiện hai nhiệm vụ chính: - Thực hiện chức năng mà virus được thiết kế để thực hiện. Những chức năng này có thể đơn giản là một trò đùa, cũng có thể là những hành động phá hoại với những hậu quả khôn lường. Nhiều virus cài đặt kỹ thuật đặt bẫy, để chức năng của virus chỉ thực sự hoạt động khi một số điều kiện cụ thể được thỏa mãn, chẳng hạn như virus Doodle Yankee đúng 17h là hát quốc ca. - Thực hiện tìm kiếm các tệp tin trên hệ thống máy tính, tạo ra các nhân bản của nó và bám vào các tệp tin được lựa chọn. Cơ chế nhân bản có thể đơn giản là tạo ra một bản sao của chính bản thân virus, cũng có thể vô cùng phức tạp nhằm giúp cho mỗi lần nhân bản có được những khác biệt nhất định so với virus ban đầu. Thuật ngữ Virus máy tính lần đầu tiên được đưa ra trong bài báo của Fred Cohen năm 1984 với tiêu đề Computer Viruses – Theory and experiments. Sau hơn 30 năm, virus máy tính cũng có sự phát triển mạnh mẽ về số lượng song hành cùng sự phát triển của phần mềm độc hại nói chung. Để phân loại virus máy tính cũng có nhiều cách khác nhau. Ở đây, ta phân loại virus thành 2 nhóm chính là virus biên dịch (compiled virus) và virus thông dịch (interpreted virus). Virus biên dịch: Virus biên dịch là loại virus có thể được thi hành trực tiếp bởi hệ điều hành. Để làm được điều đó, mã lệnh của virus biên dịch phải được biên dịch thành tệp tin có thể được thi hành bởi hệ điều hành. Với đặc trưng này, virus biên dịch chỉ có thể lây nhiễm trên một dòng hệ điều hành nhất định với một kiến trúc vi xử lý nhất định. Virus biên dịch lại có thể chia là ba nhóm chính là virus tệp tin (file virus), virus khởi động (boot virus) và virus đa năng (multipartite virus). - Virus tệp tin là những loại virus biên dịch lây nhiễm tới các tệp tin thi hành trên hệ thống máy tính như ứng dụng soạn thảo văn bản, bảng tính hay các chương trình trò chơi, các chương trình chát trên mạng Virus tệp tin lây lan đơn giản bằng cách gắn vào tệp tin thi hành. Khi tệp tin thi hành bị nhiễm virus tệp tin được kích hoạt để thực hiện, virus cũng sẽ thi hành, thực hiện chức năng của nó và lây lan sang các tệp tin thi hành khác. Hai ví dụ tiêu biểu cho virus tệp tin là Jerusalem và Cascade. Jerusalem là virus được phát hiện tại Jerusalem năm 1987, lây nhiễm các tệp tin thi hành trong môi trường DOS, nó có thể đơn giản là in ra các thông điệp hoặc xóa các tệp tin. Cascade là virus lây nhiễm rộng rãi suốt thập kỷ 1980 và những năm đầu của thập kỷ 1990. Cải tiến quan trọng của virus Cascade là việc sử dụng thuật toán mã hóa để lẩn tránh các phần mềm diệt virus. - Virus khởi động là loại virus biên dịch lây nhiễm vào phân vùng khởi động của các thiết bị lưu trữ. Như ta đã biết, phân vùng khởi động lưu trữ những thông tin về thiết bị lữu trữ, nó sẽ được các chương trình khởi động đọc để khởi tạo hệ điều hành hoặc để hệ điều hành lấy thông tin về thiết bị. Điểm mạnh của virus khởi động là nó có thể được kích hoạt tự động bởi các chương trình khởi động mà không cần chờ người sử dụng kích hoạt. Michelangelo và Stoned là những ví dụ tiêu biểu cho virus khởi động. Virus Michelangelo được phát hiện ngày mùng 4 tháng 2 năm 1991 và nó đã khiến thế giới máy tính nín thở chờ đợi ngày mùng 6 tháng 3 năm 1992 (ngày sinh của nghệ sĩ Michelangelo) - ngày virus Michelangelo sẽ hủy diệt thế giới máy tính. Tuy nhiên trên thực tế, theo thống kê chỉ khoảng 20.000 trường hợp xuất hiện sự cố mất dữ liệu được ghi nhận vào ngày 6 tháng 3 năm 1992. - Virus đa năng là loại virus biên dịch sử dụng nhiều phương thức lây nhiễm, thường bao gồm cả lây nhiễm theo tệp tin và lây nhiễm trên phân vùng khởi động. Virus đa năng tổ hợp 124
  46. những thuộc tính của virus tệp tin và virus khởi động. Những ví dụ tiêu biểu cho loại virus này là Flip và Invader. Ngoài ra, các virus biên dịch có thể cư trú trong bộ nhớ thi hành của hệ thống máy tính đã bị lây nhiễm và chiếm quyền điều khiển tệp tin của hệ điều hành. Do đó, khi hệ điều hành chạy một chương trình chưa bị lây nhiễm, hệ điều hành do bị virus chiếm quyền từ trước sẽ không thi hành ngay chương trình mà tiến hành lây nhiễm lên tệp tin thi hành đó trước. Với cách hoạt động như vậy, virus biên dịch còn được gọi là virus cư trú trong bộ nhớ (memory resident virus). Virus thông dịch: Trái ngược với virus biên dịch, virus thông dịch chứa đựng mã nguồn chương trình và chỉ được thi hành bởi một ứng dụng hay dịch vụ cụ thể nào đó. Do vậy, virus thông dịch trở nên phổ biến bởi đặc tính rất dễ để viết và sửa chữa. Một tin tặc với ít kỹ năng cũng có thể tìm kiếm trên mạng một virus thông dịch, đọc, sửa chữa và phát tán. Do đó, trên mạng có thể có hàng tá những biến thể khác nhau của cùng một virus thông dịch, hầu hết những khác biệt là rất nhỏ. Các virus thông dịch có thể được chia làm hai loại chính là virus macro và virus script. Virus macro là loại virus thông dịch khá phổ biến. Virus macro bám vào các tệp tin tài liệu chẳng hạn như các tệp tin văn bản, các bảng tính và sử dụng các trình thông dịch ngôn ngữ macro của ứng dụng để thi hành và lây lan. Một số loại phần mềm thường hỗ trợ người dùng viết các macro đơn giản để tự động hóa những nhiệm vụ phức tạp có tính chất lặp, đây chính là cơ sở cho các virus macro hoạt động. Một ví dụ tiêu biểu là ứng dụng Microsoft Office, một phần mềm được sử dụng rộng rãi và cho phép người sử dụng tạo các macro bằng ngôn ngữ VB.Script. Hơn nữa, đặc tính thường xuyên chia sẻ các tài liệu ứng dụng chính là cơ sở cho phép các virus macro lây lan nhanh chóng. Ngoài ra, trong trường hợp ứng dụng hỗ trợ template (template là một khuôn mẫu được trình ứng dụng sử dụng để mở hoặc tạo mới tệp tin), virus macro thường lây nhiễm các tệp tin template. Một khi tệp tin template đã bị lây nhiễm, mọi tài liệu được tạo hoặc mở với template sẽ bị lây nhiễm. Một số virus macro tiêu biểu có thể kể tới là Cocept, Marker và Melissa. Virus script về cơ bản không có gì khác biệt nhiều với virus macro. Sự khác biệt chính yếu là virus macro được biết bởi ngôn ngữ được hiểu bởi một ứng dụng cụ thể, do đó tính lây lan chỉ hạn chế trong phạm vi ứng dụng đó, ngược lại virus script lại được viết bởi những ngôn ngữ được hiểu bởi một dịch vụ nào đó, chạy bởi hệ điều hành. Chẳng hạn Windows Scripting Host là một dịch vụ của một vài phiên bản hệ điều hành Microsoft Windows có thể thi hành các kịch bản được viết bằng VBScript, do đó một virus script viết bằng VBScript có thể lây nhiễm trên mọi hệ thống máy tính cài đặt hệ điều hành Windows có hỗ trợ Windows Scripting Host. First và Love Stages là những ví dụ tiêu biểu cho virus script. b. Sâu máy tính Khác với virus là những chương trình, những đoạn mã lệnh sống bám trên một tệp tin nào đó và chỉ hoạt động khi tệp tin đó hoạt động, sâu máy tính (worm, thường được gọi tắt là sâu) là một chương trình hoàn chỉnh độc lập có khả năng nhân bản và di chuyển từ hệ thống máy tính này sang hệ thống máy tính khác. Do là một chương trình độc lập, sâu có thể tự nhân bản mà không cần chờ đợi sự kích hoạt của vật chủ như cơ chế nhân bản và lây lan của virus, chính ưu điểm này đã cho phép sâu lây lan với tốc độ nhanh hơn và được các tin tặc ưa chuộng hơn. Các sâu máy tính tận dụng mạng Internet để lây lan trên phạm vi lớn. Thông thường các sâu khai thác những lỗ hổng đã được biết, những điểm yếu trong cấu hình, các hệ thống thư điện tử và các hệ thống chia sẻ tệp tin để lây lan. 125
  47. Hầu hết các sâu máy tính được định hướng để tiêu thụ tài nguyên của máy tính và tài nguyên mạng. Tuy nhiên, một số sâu được sử dụng để cài đặt backdoor (chi tiết được đưa ra trong mục c) cho phép thực hiện một tấn công từ chối dịch vụ từ xa tới một máy chủ nào đó, hoặc xử lý những hoạt động nguy hiểm khác trên hệ thống máy tính. Các sâu máy tính được chia làm hai loại chính là sâu dịch vụ mạng (network service worm) và sâu thư điện tử (mass mailing worm), tương ứng với hai hình thức lan truyền chính của sâu. - Sâu dịch vụ mạng là những sâu máy tính lan truyền bằng cách khai thác những lỗ hổng trong một dịch vụ mạng gắn kết với hệ điều hành hoặc một ứng dụng nào đó. Sau khi sâu lây nhiễm vào hệ thống, nó thường sử dụng hệ thống đó để tìm kiếm những hệ thống khác đang chạy dịch vụ tương tự và tìm cách lây nhiễm vào các hệ thống đó. Hình thức lan truyền này hoàn toàn không cần bất kỳ sự tác động nào của người sử dụng, nên sâu dịch vụ mạng thường lan truyền nhanh hơn các loại phần mềm độc hại khác. Sasser và Witty là hai ví dụ cho sâu dịch vụ mạng. Sasser xuất hiện trong tháng 4 năm 2004, khai thác lỗ hổng tràn bộ đệm trong dịch vụ LSASS (Local Security Authority Subsystem Service) trên các hệ điều hành Windows (XP và 2000). Cũng trong năm 2004, sâu Witty lại khai thác lỗ hổng trên một loạt sản phẩm bảo mật mạng cụ thể là Internet Security Systems (hiện tại lấy tên là IBM Internet Security Systems). Witty có tốc độ lan truyền một cách khủng khiếp, chỉ với nửa giờ đã lây lan sang 12 ngàn máy tính và sinh ra lưu thông mạng lên tới 90 Gbits/s. - Sâu thư điện tử là những sâu máy tính thực hiện lan truyền dựa trên cơ chế phát tán thư điện tử. Về cơ bản, sâu thư điện tử có cơ chế lan truyền giống với những virus phát tán qua thư điện tử. Tuy nhiên, với virus thì tệp tin đính kèm trong thư điện tử đã bị nhiễm virus nhưng với sâu thì tệp tin đính kèm là một chương trình sâu hoàn chỉnh. Một khi sâu thư điện tử đã lây nhiễm một hệ thống, nó sẽ tự động tìm kiếm trên hệ thống những địa chỉ thư điện tử và sau đó gửi một bản copy của nó tới những địa chỉ đó. Để gửi thư, nó có thể sử dụng hệ thống thư điện tử trên máy nạn nhân hoặc sử dụng một chức năng gửi thư đơn giản được chứa sẵn trong bản thân nó. Các sâu thư điện tử thường gửi một bản copy của nó tới nhiều người nhận một lần. Bên cạnh việc làm tràn ngập các hệ thống máy chủ thư điện tử và mạng bằng một lượng lớn các thư điện tử được gửi qua lại, các sâu thư điện tử cũng có thể là nguyên nhân gây nên những vấn đề hiệu năng cho hệ thống bị lây nhiễm. Beagle là một sâu thư điện tử xuất hiện năm 2004 có thể lây nhiễm trên tất cả các phiên bản của hệ điều hành Windows. Chủng đầu tiên Beagle.A không lây nhiễm rộng rãi. Tuy nhiên, một biến thể có nó là Beagle.B lại lây lan rộng rãi và rất nguy hiểm. Beagle chứa trong nó một cài đặt giao thức SMTP riêng để gửi thư tới các địa chỉ mà nó thu thập được trên máy tính đã bị lây nhiễm. Beagle cũng mở một backdoor trên cổng 6777 (Beagle.A) và 8866 (Beagle.B). Ngoài ra, Mydoom và Nestky cũng là những sâu thư điện tử tiêu biểu. c. Trojan Trojan được lấy tên theo tên con ngựa gỗ trong truyền thuyết Trojan Horse (Con ngựa thành Troa) trong thần thoại Hy Lạp. Trojan sử dụng một chiến lược khác biệt hoàn toàn với virus và sâu, đó là nó hoàn toàn không có khả năng nhân bản, Trojan thường tỏ ra vô hại, thậm chí là có lợi cho người dùng nhưng ẩn trong nó là những mục đích xấu. Trojan là một phần mềm hoàn chỉnh có thể được cài đặt theo các lỗ hổng an ninh vào máy tính do sự sơ suất của người dùng khi truy cập mạng máy tính. Trojan cũng có thể núp danh một phần mềm tiện ích và được người dùng cài đặt một cách bình thường. Việc sử dụng các phần mềm không bản quyền, được download từ những nguồn không rõ xuất xứ là nơi cư ngụ của rất nhiều Trojan. Khi được cài đặt vào hệ thống máy tính, các chức năng xấu được tiến hành một cách âm thầm bên dưới sự hoạt động bình thường của các tiện ích thông thường mà nó cung cấp. Nhiều Trojan được định hướng để thay thế những tệp tin thi hành tồn tại trên hệ thống bằng những 126
  48. phiên bản độc hại (hoặc có lỗ hổng hoặc bị nhiễm virus), hoặc tự động cài đặt những ứng dụng khác tới hệ thống. Tuy nhiên, phần lớn Trojan đóng vai trò như một gián điệp trong hệ thống máy tính. Tùy theo mục đích khác nhau mà các Trojan có tên khác nhau, dưới đây là một số loại Trojan thường gặp: - Spyware (phần mềm gián điệp) đóng vai trò là gián điệp, nó thu thập những thông tin cần thiết trên hệ thống bị lây nhiễm và gửi thông tin đó tới một hệ thống nào đó. - Adware (phần mềm quảng cáo) đóng vai trò quảng cáo, nó thường hoạt động bằng cách bật những quảng cáo trên hệ thống bị lây nhiễm. - Key logger có nhiệm vụ ghi lại các phím đã được gõ trên bàn phím và gửi tới hệ thống phân tích nào đó bên ngoài. - Backdoor (cửa hậu) có nhiệm vụ mở ra một cổng sau để tin tặc có thể khai thác hệ thống máy tính bị lây nhiễm. - Rootkit được sử dụng để thu thập các tệp tin được cài đặt lên hệ thống và thay thế chúng, việc thay thế các tệp tin của rootkit đôi khi gây ra những hậu quả rất lớn. Tuy nhiên, nhiều trường hợp những thay đổi này nhằm che dấu một cuộc tấn công hay sự hoạt động của một phần mềm độc hại nào đó hay xóa bỏ những bằng chứng về sự hiện diện của chính bản thân rootkit. Những rootkit tiêu biểu có thể kể tới như LRK5, Knark, Adore và Hacker Defender. Trojan thường khó để phát hiện, bởi vì chúng được thiết kế để che dấu sự tồn tại trên hệ thống và xử lý những chức năng có vẻ hợp lý, nên người sử dụng và quản trị hệ thống thường không phát hiện ra. 7.2.3. Tấn công từ chối dịch vụ Ngày nay Internet được sử dụng trong hầu hết mọi khía cạnh của đời sống, nó trở thành một tài nguyên quan trọng có sức ảnh hưởng lớn. Do vậy việc phá hỏng nguồn tài nguyên Internet tạm thời dù chỉ là trong ít phút cũng có thể gây mất mát to lớn về tài chính, thậm chí gây xáo động đời sống con người. Cũng bởi thế nó nhanh chóng trở thành đối tượng đặc biệt quan tâm của giới tin tặc cũng như giới tội phạm. Sự thật là đã có nhiều đợt tấn công vào nguồn tài nguyên này trên phạm vi quốc gia và thế giới. Ngày 7 tháng 2 năm 2000, một hacker tuổi thiếu niên với nickname “mafiaboy” đã làm tê liệt website của yahoo trong gần 3 tiếng đồng hồ. Hai ngày sau, sáu website thương mại nổi tiếng khác như Amazon, CNN, Ebay, E*Trade và ZDNet cũng trở thành nạn nhân của mafiaboy. Năm 2001, sâu máy tính Code Red tấn công website của Nhà Trắng làm ảnh hưởng tới an ninh quốc gia của Mỹ, hay năm 2003, một đợt tấn công đã hạ gục Houston port system ở Texas đe dọa an ninh công cộng. Gần đây nhất, trong tháng 3 năm 2013, Spamhaus – tổ chức vốn chịu trách nhiệm duy trì danh sách đen các máy chủ chuyên gửi thư rác trên toàn cầu đang phải hứng chịu cuộc tấn công từ chối dịch vụ lớn chưa từng có với lưu lượng ở mức đỉnh lên tới 300 Gbits/s. Cuộc tấn công này đã làm trì trệ đường truyền mạng toàn thế giới trong đó khu vực châu Âu chịu ảnh hưởng nặng nề nhất. Những tấn công với mục tiêu là làm tê liệt các hệ thống máy tính hay các dịch vụ được gọi là tấn công từ chối dịch vụ - Denial of Service (DoS). Tấn công từ chối dịch vụ có thể được phân thành hai kiểu chính là tấn công dựa trên lỗ hổng phần mềm (vulnerability-based attack) và tấn công làm ngập lụt (flooding attack). - Tấn công dựa trên lỗ hổng phần mềm, hay còn gọi là tấn công ngữ nghĩa (semantic attack), là hình thức tấn công khai thác một hoặc nhiều lỗ hổng trong chính sách an ninh hoặc trong kỹ thuật nhằm hiệu lực chính sách đó, hoặc những lỗi tiềm ẩn trong phần mềm. Lợi dụng những lỗ hổng này, tin tặc chỉ cần gửi tới hệ thống một vài yêu cầu đặc biệt, những yêu cầu này 127
  49. sẽ tiêu thụ một lượng lớn tài nguyên của hệ thống và khiến hệ thống tê liệt. Ví dụ tiêu biểu của hình thức tấn công này là Ping-of-Death xuất hiện trong năm 1996, tin tặc đơn giản gửi tới hệ điều hành một yêu cầu theo giao thức ICMP (Internet Control Message Protocol) với kích thước lớn vượt mức cho phép. - Tấn công làm ngập lụt, hay còn gọi là brute-force attack, là hình thức tấn công từ chối dịch vụ bằng cách tạo ra một một lượng lớn yêu cầu hợp lệ (thường là giống nhau) nhằm tiêu thụ một tài nguyên mục tiêu nào đó trên hệ thống khiến tài nguyên đó bị quá tải không thể đáp ứng những yêu cầu đến từ những người dùng hợp lệ khác. Một ví dụ tiêu biểu là tấn công UDP (User Datagram Protocol), tin tặc sẽ gửi một lượng lớn gói tin UDP tới các cổng ngẫu nhiên của một máy chủ nào đó, điều này dẫn tới tiêu thụ hết băng thông của máy chủ, do đó người sử dụng bình thường sẽ không thể truy cập được vào máy chủ đó. Để thực hiện một cuộc tấn công từ chối dịch vụ, tin tặc có thể sử dụng một hoặc nhiều máy chủ để tấn công. Khi những yêu cầu nhằm mục đích tấn công của tin tặc đến từ nhiều máy tính khác nhau được phân tán trên mạng, thì được gọi là tấn công từ chối dịch vụ phân tán – distributed denial of service (DDoS). Ngược lại, khi những yêu cầu nhằm mục đích tấn công này đến từ cùng một máy chủ thì được gọi là tấn công từ chối dịch vụ đơn nguồn - single-source denial of service (SDoS). Trong hầu hết các tài liệu, thuật ngữ DoS được sử dụng thay thế cho SDoS. Tấn công lưu lượng mạng Ra lệnh & Điều khiển Hình 7.1. Mô hình tấn công từ chối dịch vụ phân tán Thông thường các tấn công DDoS sử dụng hai kiểu thành phần là agent (máy tác tử) và handler (máy điều khiển) như mô tả trong hình 7.1. Các Agent đơn giản là các máy tính có thể được điều khiển bởi handler để sinh ra các yêu cầu tấn công và gửi yêu cầu tấn công tới máy chủ nạn nhân. Các handler đơn giản là các máy tính có cài đặt chương trình nhằm điều khiển các agent. Handler có nhiệm vụ thông báo cho các agent biết khi nào thực hiện tấn công, tấn công 128