Các vấn đề cơ sở của khoa học máy tính

Lý thuyết: 60 tiết Thực hành: 0 tiết CÁC VẤN ĐỀ CƠ SỞ CỦA KHOA HỌC MÁY TÍNH ĐẠI HỌC MỞ TP.HCM KHOA CÔNG NGHỆ THÔNG TIN Mục Tiêu Môn Học • Môn học này trình bày các nguyên lý tính toán về mặt lý thuyết và thực tiễn: những cơ sở lý thuyết thông tin và tính toán, lý thuyết ngôn ngữ, phân tích giải thuật, thực hiện các hệ thống tính toán, cơ sở dữ liệu, truyền dữ liệu, • Sau khi học xong môn này, sinh viên đạt được những kiến thức cơ bản về giải thuật, phần cứng, phần mềm, ngôn ngữ lập trình, kỹ thuật lập trình, mạng máy tính, cơ sở dữ liệu, Internet và nâng cao kỹ năng lập trình thông qua các bài tập. 2 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Tài Liệu • Tài liệu chính: - Carl Raynolds, Paul Tymann, Principles of Computer Science, Mc. Graw-Hill, 2008. • Tài liệu tham khảo: - J. Glenn Bookshear, Computer Science – An overview, 11th edition, Pearson-Addison Wesley, 2012 . 3 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Phương Pháp Đánh Giá • Thi lý thuyết giữa kỳ: 30%. • Thi lý thuyết cuối kỳ: 70%. 4 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Chương 1: GIỚI THIỆU VỀ KHOA HỌC MÁY TÍNH Nội Dung 1. Khoa học Máy tính là gì? 2. Giải thuật . 3. Phần cứng. 4. Ngôn ngữ máy (ngôn ngữ cấp thấp) . 5. Ngôn ngữ cấp cao. 6. Lập trình. 7. Phần mềm: phần mềm hệ thống, phần mềm ứng dụng. 8. Mạng máy tính. 9. Công nghệ cơ sở dữ liệu. 10. Internet, World Wide Web. 6 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Khoa Học Máy Tính Là Gì? • Khoa học máy tính là gì? Khoa học máy tính (computer science) được định nghĩa theo nhiều cách khác nhau. Sau đây là vài định nghĩa: • “Khoa học máy tính là tập của các phương thức có liên quan đến tính toán, gồm cả lý thuyết và thực tiễn: lý thuyết về thông tin và tính toán, lý thuyết ngôn ngữ, phân tích giải thuật, sự thực thi của các hệ thống tính toán, đồ hoạ máy tính, cơ sở dữ liệu, truyền thông, ” • “Sự nghiên cứu về máy tính và xử lý giải thuật, bao gồm những nguyên lý, thiết kế 7 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Khoa Học Máy Tính Là Gì? Phần cứng và phần mềm, ứng dụng và ảnh hưởng của nó đối với xã hội”. • Định nghĩa sau cùng nhấn mạnh sự phát triển và phân tích giải thuật là trọng tâm của khoa học máy tính. • Mặc dù các định nghĩa trên có khác nhau, nhưng tất cả đều nhằm nhấn mạnh đến sự nghiên cứu giải thuật. Khoa học máy tính kết hợp các khái niệm lý thuyết của thiết kế và phân tích giải thuật với thực tiễn là xem xét thế nào để hiện thực giải thuật trên máy tính và giải quyết vấn đề thực tiễn. 8 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Giải Thuật • Giải thuật là gì? Giải thuật (algorithm) định nghĩa chi tiết và rõ ràng một chuỗi các hành động nối tiếp nhau để giải quyết một vấn đề cụ thể hoặc thực thi một tác vụ nào đó. • Cho ví dụ, cần xác định ước số chung lớn nhất (greatest common divisor – GCD) của 2 số nguyên. • Theo định nghĩa, thì GCD của 2 số nguyên dương là số nguyên lớn nhất mà nó là ước số của cả 2 số đó. Ví dụ: GCD(42, 30) = 6. Chúng ta có thể sử dụng giải thuật sau để tìm GCD của 2 số nguyên a và b: - Nếu b = 0 thì GCD(a, b) = a. 9 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Giải Thuật - Gán r là phần dư của a và b. - Lặp lại các bước trên và dùng b và r. • Giải thuật là nền tảng để máy tính xử lý thông tin. Bởi vì chương trình máy tính thể hiện giải thuật và ra lệnh cho máy tính thực hiện các bước cụ thể được chỉ định trong giải thuật. • Giải thuật được biểu diễn bằng lưu đồ hay mã giả để chúng ta có thể dễ dàng đọc. Trong ví dụ trên, giải thuật được thể hiện bằng mã giả. • Để thực hiện các bước của giải thuật bằng máy tính, chúng ta cũng cần hiểu về thuật ngữ “phần cứng”. 10 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Phần Cứng • Bản chất của giải thuật là cách mà máy tính xử lý thông tin, bởi vì thực chất thì chương trình máy tính là một hình thái khác của giải thuật. Nó báo cho máy tính biết các bước cụ thể để thực thi tác vụ được chỉ định trong giải thuật. Để nguyên cứu về giải thuật, nhà khoa học máy tính cũng phải hiểu về máy tính vì nó là công cụ được sử dụng để thực hiện giải thuật. • Thuật ngữ phần cứng (hardware) dùng để mô tả những thành phần vật lý, hữu hình của máy tính. Bàn phím, chuột, bo mạch chủ, card đồ hoạ, bộ vi xử lý là tất cả những ví dụ 11 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Phần Cứng về phần cứng máy tính. • Cũng cần lưu ý rằng, một giải thuật thì được cho là tốt đối với một nền phần cứng nào đó và có thể sẽ là không đối với nền phần cứng khác. 12 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Chương Trình - Ngôn Ngữ Máy • Con người có thể dễ dàng đọc và hiểu được giải thuật. Cho ví dụ, giải thuật GCD của hai số nguyên trước đây được viết bằng ngôn ngữ Anh. Nhưng chỉ có ngôn ngữ mà máy tính hiểu được đó là ngôn ngữ máy (machine language). • Ngôn ngữ máy là một hệ thống các mã lệnh dạng nhị phân mà máy tính được thiết kế để thực thi chúng. Mỗi từ trong ngôn ngữ máy thể hiện cho một hành động đơn và có thể được máy tính thực hiện. • Một tập các chỉ thị/lệnh mô tả từng bước của một giải thuật được gọi là chương trình (program). 13 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Cấp Cao • Người lập trình khó có thể làm việc trực tiếp với ngôn ngữ máy. Các từ lệnh của ngôn ngữ máy gồm một dãy các số 0 và 1, chiều dài tiêu biểu là 8, 16, 32, hay 64 bit và đôi khi cũng thay đổi. • Vì lý do này, nhiều ngôn ngữ lập trình ra đời để người lập trình dễ dàng chuyển giải thuật thành chương trình và thực thi trên máy tính. Chúng ta xem các ngôn ngữ này như là ngôn ngữ cấp cao hơn (higher-level language), bởi vì chúng được thiết kế để người lập trình làm việc ở “mức cao hơn” hơn là ở mức ngôn ngữ máy. 14 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Cấp Cao • Ngôn ngữ máy được xem là ngôn ngữ cấp thấp (low-level language). Các ngôn ngữ như Java, FORTRAN, Basic, ADA, là các ngôn ngữ cấp cao (high-level language). Chúng được những nhà khoa học máy tính dùng để biểu diễn giải thuật. 15 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình – Phần Mềm • Hành động biểu diễn giải thuật sử dụng ngôn ngữ cấp thấp hay cấp cao được gọi là lập trình (programming). • Thuật ngữ phần mềm (software) dùng để mô tả một tập các lệnh hay chương trình mà máy tính dùng để thực hiện một giải thuật. Phần mềm chứa các lệnh trực tiếp thao tác với phần cứng. • Phần mềm làm cho các chức năng cơ bản của máy tính có thể sử dụng được thì được gọi là phần mềm hệ thống (system software). Phần mềm hệ thống chịu trách nhiệm điều khiển và quản lý phần cứng của hệ thống 16 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Phần Mềm máy tính. Nó còn làm cho máy tính dễ sử dụng đối với các nhà phát triển chương trình cũng như là những người sử dụng nói chung. • Cho ví dụ, phần mềm hệ thống gồm hệ điều hành, quản lý màn hình, chương trình chống virus, chương trình xử lý ngôn ngữ (trình biên dịch – compiler hay trình thông dịch – interpreter) và các chương trình điều khiển thiết bị. • Những chương trình như xử lý văn bản, bảng tính được gọi là phần mềm ứng dụng (application software). Phần mềm ứng dụng 17 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Phần Mềm dùng để thực hiện các tác vụ cụ thể. Phần mềm ứng dụng có thể là một chương trình đơn hay một tập các chương trình làm việc với nhau để thực hiện các yêu cầu của người sử dụng máy tính. • Hệ điều hành (operating system) là phần mềm hệ thống đặc biệt quan trọng và phức tạp. Quan trọng bởi vì hệ điều hành tác động đến toàn bộ hệ thống máy tính. • Hệ điều hành làm cho người sử dụng dễ dàng truy cập các thiết bị ngoại vi; lưu trữ thông tin như dữ liệu, văn bản, chương trình; tạo giao diện người dùng để dễ thực 18 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Phần Mềm thi chương trình ứng dụng; xem ngày giờ hệ thống; kết nối Internet; quản lý và cấp phát bộ nhớ; chia sẻ tài nguyên cho chương trình; cho phép truy cập đồng thời. • Các hệ điều hành thông dụng hiện nay như Microsoft Windows, Mac OS, Unix, Linux và MVS của IBM. 19 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Mạng Máy Tính • Cả khi vào thập niên 1980, hầu hết các máy tính không kết nối mạng. Trong khoảng từ năm 1970 đến 1980 các nhà khoa học máy tính đã khám phá ra những ưu điểm của mạng máy tính và đưa ra một số kết nối vật lý khác nhau giữa các máy tính, như là các giao thức mạng (networking protocol). • Vào thời điểm này, mỗi nhà cung cấp máy tính đưa ra một chuẩn giao thức khác nhau với hy vọng là sẽ bán được cho khách hàng. IBM đưa ra giao thức System Networking Architecture (SNA), Hewlett Packard đưa ra Distributed Systems (DS) và Xerox đưa ra 20 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Mạng Máy Tính Xerox Networking Systems (XNS). Các giao thức này không tương thích nhau. Tuy nhiên, chúng là cầu nối đến giữa các hệ thống với nhau. • Ngày nay, vấn đề mạng thì khác. Hầu hết trên thế giới chấp nhận các chuẩn IEEE 801 và các giao thức TCP/IP cho Internet. • Vấn đề bây giờ cần quan tâm là: - Mở rộng số lượng địa chỉ Internet. - Tăng tốc độ kết nối vật lý như dùng cáp quang. - Tăng tốc độ kết nối không dây, cho phép truyền tải dữ liệu lớn hơn như phim ảnh. - Năng lượng tiêu thụ và giá thành thấp. 21 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Công Nghệ Cơ Sở Dữ Liệu • Hỗ trợ cho hầu hết các ứng dụng ngày nay là công nghệ CSDL (database technology). Mô hình CSDL vượt trội là CSDL quan hệ, nó ra đời vào thập niên 1980. Các nhà khoa học máy tính đã phát triển các giải thuật lưu trữ và truy cập thông tin nhanh chóng từ kho dữ liệu khổng lồ. Cho ví dụ, Google có thể tìm kiếm ngay tức khắc hơn 400.000 bức ảnh từ hơn 1.5 tỷ bức ảnh trong CSDL của nó. • Có nhiều điều cần biết về việc tạo một CSDL tốt, truy xuất CSDL từ chương trình, phát triển và quản lý CSDL. Những người lập trình ứng dụng và quản trị CSDL cần hiểu 22 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Công Nghệ Cơ Sở Dữ Liệu CSDL ở mức này để sử dụng chúng một cách hiệu quả. • Một số hệ điều hành mới sử dụng công nghệ CSDL trong các hệ thống tập tin của nó để lưu trữ tất cả thông tin. Điều này làm cho hệ điều hành cải thiện về tốc độ, không gian lưu trữ và bảo mật dữ liệu. 23 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Internet – World Wide Web • Chúng ta có thể dễ dàng nhận thấy rằng máy tính đã thay đổi đột ngột đời sống của con người. • Những công nghệ như Internet, World Wide Web đã đặt khối lượng thông tin khổng lồ trên đầu ngón tay của chúng ta. Ví dụ, những phần mềm như Messenger, thư điện tử, điện thoại di động đã cách mạng hoá cách thức mà con người trao đổi thông tin. 24 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Chương 2: GIẢI THUẬT Nội Dung 1. Định nghĩa giải thuật . 2. Ví dụ về giải thuật. 3. Đặc tả giải thuật. 4. Phân tích giải thuật. 5. Giải thuật là công nghệ. 6. Mô hình hình thức tính toán. 2 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Định Nghĩa Giải Thuật • Định nghĩa giải thuật: Giải thuật là cách thức để giải quyết một tập các vấn đề. • Thuật ngữ “giải thuật” cũng áp dụng cho bất kỳ cách thức nào để giải quyết một vấn đề cụ thể. Cho ví dụ, các bước để thay phanh xe cũng được gọi là giải thuật. • Ví dụ: Tìm ước số chung lớn nhất. • Trong toán học, một giải thuật nổi tiếng và hữu dụng là giải thuật Euclid để tìm ước số chung lớn nhất (GCD) của hai số nguyên. Ông đã đưa ra giải thuật này vào khoảng 300 năm trước công nguyên. • Không có giải thuật Euclid, chúng ta tìm 3 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ví Dụ Về Giải Thuật GCD(372, 84) như thế nào? Phải phân tích hai số nguyên thành các thừa số nguyên tố và tìm thừa số chung lớn nhất. • Nếu các số nguyên này lớn, việc phân tích thành các thừa số trở nên khó khăn và tốn nhiều thời gian. Euclid đã tìm ra giải thuật một cách có hệ thống và nhanh chóng giảm kích thước của vấn đề, bằng cách thay giá trị ban đầu của hai số nguyên với giá trị nhỏ hơn cho đến khi một trong hai số bằng 0. Lúc này, GCD của hai số chính là giá trị của số còn lại. • Sau đây là giải thuật Euclid để tìm GCD của 4 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ví Dụ Về Giải Thuật hai số nguyên A và B: Repeat: Nếu B = 0, GCD(A, B) = A Ngược lại: Thay R bằng A modulo B Thay A bằng B Thay B bằng R • Cho ví dụ, để tìm GCD của 372 và 84: - Tìm GCD(84, 36) vì 372 % 84 = 36 - Tìm GCD(36, 12) vì 84 % 36 = 12 - Tìm GCD(12, 0) vì 36 % 12 = 0 - Vậy GCD(372, 84) = 12 5 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ví Dụ Về Giải Thuật • Như vậy, giải thuật là một chuỗi các phép toán thao tác trên tập giá trị nhập và sinh ra kết quả trong khoảng thời gian hữu hạn. Trong ví dụ trên, tập giá trị nhập là 2 số nguyên. Kết quả là ước số chung lớn nhất của hai số đó. • Có nhiều cách để giải quyết một lớp các vấn đề. Câu hỏi đặt ra là giải thuật nào tốt nhất? Thông thường, các nhà khoa học máy tính sử dụng các kỹ thuật để phân tích, đánh giá và so sánh hiệu quả giữa các giải thuật. 6 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Đặc Tả Giải Thuật • Đặc tả giải thuật (representing algorithm): Trong ngành khoa học máy tính, giải thuật thường được đặc tả bằng mã giả (pseudocode). Mã giả đủ để cho một ngôn ngữ lập trình có thể thể hiện các tác vụ mà máy tính phải thực hiện trong giải thuật. • Mã giả cũng độc lập với bất kỳ ngôn ngữ lập trình nào. Nó thể hiện chi tiết cú pháp và làm cho người lập trình dễ dàng đặc tả các thao tác cốt lõi của một giải thuật. • Không có một mẫu chuẩn nào cho mã giả. Các nhà khoa học máy tính sử dụng mã giả của riêng mình để đặc tả một giải thuật. Ví dụ sau là một kiểu mã giả đặc tả giải thuật GCD: 7 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Đặc Tả Giải Thuật GCD(a, b) While b != 0 { r ← a mod b a ← b b ← r } return a - Tên hàm và đối số - Trong khi b khác 0 - Bắt đầu thân vòng lặp - Gán r = a modulo b - Gán a = giá trị ban đầu của b - Gán b = r - Kết thúc thân vòng lặp - Khi b = 0, kết quả trả về là a • Để minh hoạ thế nào là hiệu quả khác nhau giữa các giải thuật, chúng ta sẽ thảo luận về sự đa dạng của các giải thuật mà các nhà khoa học máy tính đã đưa ra để giải quyết các vấn đề phổ biến trong tính toán. Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng 8 Đặc Tả Giải Thuật • Tìm kiếm tuần tự (sequential search): Giả sử chúng ta có danh sách của các sinh viên trong một lớp học, yêu cầu là hãy tìm tên của sinh viên Debbie Drawe. Giải thuật tìm kiếm tuần tự chỉ đơn giản là so sánh mỗi tên trong danh sách với tên cần tìm. Quá trình tìm kiếm kết thúc khi tên được tìm thấy hoặc khi giải thuật đã tìm hết tất cả các tên trong danh sách. • Sau đây là mã giả của giải thuật tìm kiếm tuần tự: 9 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Đặc Tả Giải Thuật Sequential_Search(listNames, name) length ← length of listNames matchFound ← false index ← 1 while matchFound = false AND index <= length { if listNames[index] = name then matchFound ← true index ← index + 1 } return matchFound end 10 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật • Phân tích giải thuật (analyzing algorithm): Nếu chúng ta biết chiều dài của mỗi câu lệnh và có bao nhiêu tên trong danh sách, chúng ta có thể tính được thời gian để thực thi giải thuật. • Tuy nhiên, thường thì chúng ta không biết giải thuật giải quyết vấn đề trong bao lâu và thời gian cần giải quyết vấn đề sẽ thay đổi theo độ lớn của vấn đề. • Giải thuật tìm kiếm tuần tự sẽ cần thời gian lâu hơn nếu số lần so sánh nhiều hơn. Những lệnh khác của giải thuật chỉ thực thi 1 lần, nhưng những lệnh trong vòng lặp sẽ 11 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Phân Tích Giải Thuật thực thi nhiều lần miễn là điều kiện lặp còn đúng. • Nếu tên cần tìm cần tìm nằm giữa danh sách thì giải thuật sẽ chỉ tìm một nửa danh sách. Nhưng nếu tên cần tìm ở cuối hoặc không có trong danh sách thì giải thuật sẽ phải tìm tất cả các tên trong danh sách. • Thời gian thực thi của giải thuật tìm kiếm tuần tự sẽ tăng tỷ lệ theo kích thước của danh sách. • Chúng ta nói rằng “bậc tăng” của giải thuật tìm kiếm tuần tự là n, ký hiệu là T(n). Chúng ta cũng nói rằng một giải thuật mà bậc tăng của nó giới hạn trong một yếu tố không đổi 12 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Phân Tích Giải Thuật nào đó có theta của n, ký hiệu Θ(n). Lưu ý: T(n) là hàm theta của g(n): T(n) = Θ(g(n)) nếu ∃ các hằng số dương c1, c2, n0 sao cho với mọi n >= n0: c1g(n) <= T(n) <= c2g(n) 1. Giải thuật tìm kiếm tuần tự ở trên có Θ(n). Bởi vì, trong trường hợp trung bình và xấu nhất, giải thuật thực hiện chậm tỷ lệ với chiều dài n của danh sách. 2. Sắp xếp bằng phương pháp chèn trực tiếp (insertion sort) - thời gian thực thi T(n) = Θ(n2): 13 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật Insertion_Sort(numList) length ← length of numList numIndex ← 2 while(numIndex <= length) { newNum ← numList[numIndex] sortedIndex ← numIndex - 1 while newNum 0 { numList[sortedIndex + 1] ← numList[sortedIndex] sortedIndex ← sortedIndex - 1 } numList[sortedIndex + 1] = newNum numIndex ← numIndex + 1 } end 14 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Phân Tích Giải Thuật • Để phân tích thời gian thực thi của giải thuật sắp xếp bằng phương pháp chèn trực tiếp, đầu tiên chúng ta lưu ý là thời gian thực thi tỷ lệ với số phần tử cần sắp xếp n. Ngoài ra, mỗi phần tử đang xét phải được so sánh một hay nhiều lần với các phần tử đã được sắp. Trong trường hợp tốt nhất, danh sách cần sắp xếp đã có thứ tự rồi, khi này mỗi phần tử chỉ so sánh một lần, vì thế trường hợp tốt nhất của giải thuật là Θ(n). • Trong trường hợp xấu nhất, danh sách cần sắp xếp có thứ tự ngược, khi này mỗi phần tử đang xét sẽ so sánh với tất cả phần tử đã 15 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật được sắp. Phần tử thứ 2 so sánh với phần tử đầu, phần tử thứ 3 so sánh với phần tử thứ 2 và phần tử đầu, Ví dụ danh sách có 4 phần tử có thứ tự ngược, số lần so sánh sẽ là 6. Nói chung, số lần so sánh trong trường hợp xấu nhất của giải thuật này là 𝑛𝑛 𝑛𝑛 + 12 − 𝑛𝑛 = 𝑛𝑛2 − 𝑛𝑛2 • Khi n lớn thì n2 lớn hơn rất nhiều so với n, vì vậy thời gian thực thi của giải thuật trong trường hợp này là T(n) = Θ(n2). • Trong trường hợp trung bình, mỗi phần tử đang xét sẽ so sánh với một nửa phần tử đã 16 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật được sắp. Vì vậy, thời gian thực thi của giải thuật trong trường hợp này cũng là T(n) = Θ(n2). 3. Sắp xếp bằng phương pháp trộn (merge sort) - thời gian thực thi T(n) = Θ(n log2n): merge(listA, listB) index ← 1 while listA is not empty AND listB is not empty if listA[1] < listB[1] sortedList[index] ← listA[1] discard listA[1] 17 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật else sortedList[index] ← listB[1] discard listB[1] index ← index + 1 while listA is not empty sortedList[index] ← listA[1] discard listA[1] index ← index + 1 while listB is not empty sortedList[index] ← listB[1] discard listB[1] index ← index + 1 return sortedList 18 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật • Trong hàm merge(), các phần tử được di chuyển từ một trong hai danh sách ban đầu là listA và listB vào danh sách kết quả sortedList. Trong đó, tổng số phần tử di chuyển bằng với tổng số phần tử của hai danh sách ban đầu. Vì vậy, thời gian thực thi của hàm merge() là Θ(nA + nB), với nA + nB là tổng số phần tử của hai danh sách. • Giải thuật sắp xếp bằng phương pháp trộn sẽ sử dụng hàm merge() ở trên để trộn hai danh sách có thứ tự thành danh sách mới cũng có thứ tự: 19 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật merge_sort(numList) length ← length of numList if length > 1 listA ← first half of numList listB ← second half of numList resultA ← merge_sort(listA) resultB ← merge_sort(listB) sortedList ← merge(resultA, resultB) return sortedList else return numList end 20 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật • Bài tập tại lớp: Hãy lấy ví dụ thực thi giải thuật sắp xếp trộn bằng lời gọi hàm merge_sort() với danh sách sau: numList = {1, 6, 4, 2}. • Tổng thời gian thực thi T(n) của giải thuật sắp xếp trộn gồm thời gian gọi đệ qui của hai nửa danh sách và thời gian kết hợp (trộn) các kết quả: T(n) = 2T(n/2) + merge • Như chúng ta đã biết, thời gian thực thi hàm merge() là nA + nB = n, nên: T(n) = 2T(n/2) + n 21 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật • Từ công thức trên, chúng ta xây dựng hệ thức truy hồi sau: • Giải hệ thức truy hồi trên, viết lại: T(n) = n + 2T(n/2) = n + 2[n/2 + 2T(n/4)] = n + n + 4T(n/4) = n + n + 4[n/4 + 2T(n/8)] = n + n + n + 8T(n/8) = 3n + 23T(n/23) = 22 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật Ở bước thứ i, ta có: T(n) = in + 2iT(n/2i) Quá trình tiếp tục cho đến khi gặp T(1). Tức là n/2i = 1 → n = 2i → i = log2n. Khi này: T(n) = nlog2n + 𝟐𝟐𝒍𝒍𝒍𝒍𝒍𝒍𝟐𝟐𝒏𝒏T(1) = nlog2n + nT(1) = nlog2n + nΘ(1) = nlog2n + Θ(n) = Θ(nlog2n + n) = Θ(max(nlog2n + n)) = Θ(nlog2n) 23 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật 4. Tìm kiếm nhị phân (binary search) - thời gian thực thi T(n) = Θ(log2n): • Trước đây, chúng ta đã xét giải thuật tìm kiếm tuần tự, độ phức tạp của nó là Θ(n). Nếu danh sách tìm kiếm đã có thứ tự, sử dụng giải thuật tìm kiếm nhị phân sẽ hiệu quả hơn. • Thời gian tìm kiếm của giải thuật tìm kiếm nhị phân là log2n. Nếu danh sách có 1.000.000 phần tử thì số lần tìm kiếm không quá 20 lần, trong khi giải thuật tìm kiếm tuần tự có số lần tìm kiếm trung bình là 500.000 lần. 24 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật • Sau đây là mã giả của giải thuật tìm kiếm nhị phân: BinarySearch(list, searchItem) begin ← 1 end ← length of list matchFound ← false while matchFound = false AND begin <= end midpoint ← (begin + end) / 2 if list[midpoint] = searchItem matchFound = true else if searchItem < list[midpoint] 25 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Phân Tích Giải Thuật end ← midpoint - 1 else begin ← midpoint + 1 return matchFound • Trong mỗi vòng lặp, giải thuật tìm kiếm nhị phân giảm một nửa kích thước danh sách. Vì vậy, nếu tìm thấy hay không tìm thấy phần tử trong danh sách thì số lần lặp tối đa là log2n. Do đó, thời gian thực thi của giải thuật này là T(n) = Θ(log2n). 26 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Giải Thuật Là Công Nghệ • Nhiều người cho rằng tốc độ phần cứng máy tính như là sự đo lường về kỹ thuật. Nhưng các giải thuật đã xét trước đây và hiệu quả thực thi của nó, cho thấy rằng một giải thuật tốt trên máy tính chậm hơn là một giải thuật chậm trên máy tính nhanh. • Giả sử chúng ta cần sắp thứ tự 1.000.000 (106) phần tử. Hoặc là chúng ta chọn máy tính đang sử dụng với giải thuật sắp xếp trộn hoặc là mua máy tính mới nhanh hơn 10 lần nhưng sử dụng giải thuật sắp xếp chèn. • Giải thuật chèn trên máy tính mới sẽ cần 27 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Giải Thuật Là Công Nghệ (106)2 chu kỳ, trong khi giải thuật trộn cần 106(log2106) = 106(20) = 20.000.000 chu kỳ. Nếu cần 20 giây để thực thi giải thuật trộn trên máy tính cũ thì sẽ cần đến 27 giờ để thực thi giải thuật chèn trên máy tính mới. 28 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán • Lý thuyết máy tính được cải tiến bởi mô hình hình thức tính toán bằng toán học. • Mô hình có tính thuyết phục nhất được đưa ra vào năm 1936 bởi nhà toán học người Anh - Alan Turing. • Khái niệm toán học của mô hình tính toán Turing được gọi là máy Turing (Turing machine) hay TM. • Một máy Turing thường được mô tả như là một máy đọc dải băng (tape): - Dải băng được chia thành các ô chứa các ký hiệu (symbol) và các khoảng trống (blank) và có thể dài vô hạn. 29 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán - Máy sẽ đọc một ký hiệu ở mỗi thời điểm, ký hiệu được đặt phía dưới “đầu đọc/ghi” của máy. - Máy cũng có thể xoá ký hiệu, ghi ký hiệu mới và có thể di chuyển đầu đọc/ghi một ô sang trái hay sang phải trên dải băng (hoặc dải băng di chuyển). - Tại mỗi thời điểm, máy luôn ở một trong một số trạng thái hữu hạn, khi đọc một ký hiệu có thể làm cho trạng thái của máy thay đổi. - Một trạng thái đặc biệt là trạng thái dừng (halting state), đây là trạng thái kết thúc. 30 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán - Khi máy bắt đầu, trạng thái của nó là 1, lúc này máy sẽ ở bên cực trái của dải băng và dải băng sẽ được mở rộng vô hạn về bên phải. • Một máy Turing cụ thể sẽ có một tập các lệnh. Mỗi lệnh gồm một bộ 5 giá trị: 1. Trạng thái hiện tại. 2. Ký hiệu hiện tại đang đọc. 3. Ký hiệu để thay thế ký hiệu hiện tại. 4. Trạng thái kế tiếp. 5. Hướng để di chuyển đầu đọc (Right (phải), Left (trái), Stationary (đứng yên)) 31 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán • Ví dụ 1: Giả sử máy Turing gồm 3 lệnh (Δ nghĩa là trống): 1.(1, 0, 1, 1, Right) 2.(1, 1, 0, 1, Right) 3.(1, Δ, Δ, halt, Stationary) • Lệnh thứ nhất: nếu ký hiệu đang đọc là 0, thay nó bằng 1 và chuyển sang phải dải băng. • Lệnh thứ hai: nếu ký hiệu đang đọc là 1, thay nó bằng 0 và chuyển sang phải dải băng. • Lệnh thứ ba: nếu ký hiệu đang đọc là trống, dừng máy không di chuyển. 32 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán • Giả sử dải băng dùng cho máy Turing ở trên chứa các ký hiệu sau: 1 1 0 1 0 1 0 0 Δ Δ Δ... • Bắt đầu ở trạng thái 1, máy ở cực trái của dải băng, máy đọc ký hiệu 1. Lệnh 2 được sử dụng, làm cho 1 được thay bằng 0, máy vẫn ở trạng thái 1 và di chuyển 1 ô sang phải dải băng. • Kế đến, máy đọc ký hiệu 1 kế tiếp. Lệnh 2 được sử dụng lần nữa, vì thế ký hiệu 1 thứ hai được thay bằng 0, máy vẫn ở trạng thái 1 và di chuyển sang phải. • Khi máy đọc ký hiệu 0, lệnh 1 được sử dụng, 33 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán lệnh này làm cho 0 được thay bằng 1, máy vẫn ở trạng thái 1 và di chuyển sang phải.. • Cuối cùng, máy đọc ký hiệu trống, lệnh 3 được sử dụng và máy sẽ dừng. • Bài tập tại lớp: a) Cho biết công dụng của máy Turing ở trên. b) Kết quả được ghi trên dải băng. • Ví dụ 2: Một ví dụ phức tạp hơn một chút là lấy bù 2 (two's complement) của số nhị phân. Phép toán này thường được máy tính sử dụng để thực hiện trừ nhị phân. • Trước đây, trên những máy cộng cơ học, 34 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán người ta thực hiện phép trừ tương tự nhưng trên cơ số 10, sử dụng phương pháp lấy bù 10 (10’s complement – bù 9 + 1). • Ví dụ để tính 17 – 14, người ta tìm bù 9 của 14 là 85, sau đó cộng thêm 1 là 86. Lấy 86 + 17 = 103, bỏ giá trị nhớ 1 bên trái nhất còn lại là 3. • Để thực hiện trừ nhị phân, lấy bù 2 số trừ và cộng với số bị trừ. Cho ví dụ để tính 5 – 2, lấy bù hai số 2 và cộng với số 5. Giả sử dùng 3 bit để biểu diễn giá trị nhị phân của 5 và 2: 35 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán Nhị phân Ý nghĩa 010 2 110 bù 2 (= bù 1 + 1) của 2 +101 cộng với 5 1011 3 (bỏ bit nhớ 1 bên trái nhất) • Sau đây là các lệnh của máy Turing để lấy bù 2 một số nhị phân: 1 (1, 0, 1, 1, Right) 2 (1, 1, 0, 1, Right) 3 (1, Δ, Δ, 2, Left) 4 (2, 0, 1, 3, Right) 5 (2, 1, 0, 2, Left) 36 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán 6 (3, 1, 1, 3, Right) 7 (3, 0, 0, 3, Right) 8 (3, Δ, Δ, halt, Stationary) • Lệnh 1 và 2 thực hiện lấy bù 1 các bit trên dải bằng. • Lệnh 3 thực thi khi máy Turing đã lấy bù 1 tất cả các bit và gặp ký tự trống bên cuối phải của dải băng. Khi lệnh này thực thi, máy sẽ đến trạng thái 2 và di chuyển sang trái. • Trong trạng thái 2, nếu máy gặp bit 0, lệnh 4 sẽ làm cho 0 được thay bằng 1, máy sẽ đến trạng thái 3 và di chuyển sang phải. 37 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán • Khi máy ở trạng thái 3, lệnh 6 và lệnh 7 làm cho máy di chuyển sang phải mà không thay đổi nội dung dải băng. Khi máy gặp ký tự trống bên phải lần nữa, lệnh 8 sẽ làm cho máy dừng. • Trong trạng thái 2, nếu máy gặp bit 1, lệnh 5 sẽ làm cho 1 được thay bằng 0, máy vẫn ở trạng thái 2 và di chuyển tiếp sang trái cho đến khi gặp bit 0, khi này lệnh 4 được thực thi như đã mô tả ở trên. • Ví dụ số nhị phân là 010, máy Turing sẽ tạo các nội dung như sau trên dải băng khi nó thực thi: 38 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán 0 1 0 Δ Δ nội dung ban đầu 1 0 1 Δ Δ lấy bù 1 hoàn tất 1 0 0 Δ Δ sau khi thực thi lệnh 5 1 1 0 Δ Δ sau khi thực thi lệnh 4 1 1 0 Δ Δ dừng sau khi thực thi lệnh 8 • Máy Turing thực hiện trên nhiều giá trị nhập nhưng không phải tất cả. Giả sử nội dung của dải băng ban đầu đều là 0: 0 0 0 Δ Δ nội dung ban đầu • Sau khi thực hiện lấy bù 1, tất cả các bit 0 thành 1: 1 1 1 Δ Δ 39 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Mô Hình Hình Thức Tính Toán • Khi này lệnh 5 được thực thi để tìm các bit 1 và thay bằng 0. Trong trường hợp này, không bao giờ máy gặp bit 0 để làm cho lệnh 4 thực thi và đưa máy vào trạng thái 3 để máy di chuyển vào cuối dải bằng và kết thúc thích hợp. 40 Các vấn Đề CSKH Của Máy Tính Th.S GVC Tô Oai Hùng Chương 3: TỔ CHỨC MÁY TÍNH Nội Dung 1. Kiến trúc von Neumann. 2. Biểu diễn dữ liệu. 3. Chiều dài từ của máy tính. 4. Dạng dữ liệu nguyên. 5. Dạng dữ liệu thực. 6. Dạng ký tự. 7. CPU / ALU. 8. Tập lệnh. 9. Bộ nhớ. 10. Nhập / Xuất . 2 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Kiến Trúc Von Neumann • Hầu hết các máy tính ngày nay hoạt động dựa vào “kiến trúc von Neumann”. Ý tưởng chính của kiến trúc này là chương trình và dữ liệu được lưu trữ trong bộ nhớ máy tính. John von Neumann đã đưa ra ý tưởng này vào năm 1945. • Kiến trúc von Neumann cũng được gọi là “máy tính có chương trình được lưu trữ - stored program computer”. Các bước (lệnh) của chương trình được lưu trữ trong bộ nhớ máy tính và chu kỳ thao tác của máy sẽ lấy bước kế tiếp (lệnh để thực thi) từ bộ nhớ, hoàn thành thao tác này và lấy bước kế tiếp. 3 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Kiến Trúc Von Neumann Quá trình này được lặp lại cho đến khi máy tính gặp lệnh “dừng - halt”. • Có 3 thành phần chủ yếu trong máy tính von Neumann. Bộ nhớ là nơi chứa chương trình và dữ liệu. Đơn vị xử lý trung tâm (central processing unit - CPU) truy xuất chương trình và dữ liệu trong bộ nhớ và thực thi chúng. Đơn vị nhập/xuất truy xuất các thiết bị nhập và xuất dữ liệu. 4 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Biểu Diễn Dữ Liệu • Chúng ta thường sử dụng các số được biểu diễn trong “cơ số 10 - base 10” – hệ thập phân. Có lẻ cơ số này dựa trên ý tưởng là chúng ta có 10 ngón tay. • Ví dụ: 427 = 4 * 102 + 2 * 101 + 7 * 100 • Chúng ta nói rằng số được biểu diễn trong cơ số 10 bởi vì các ký số của số đó được nhân với luỹ thừa của 10. • Máy tính sử dụng cơ số 2, bởi vì điều này sẽ làm cho dễ dàng trong việc xây dựng phần cứng khi máy tính chỉ dựa trên hai trạng thái on và off (1 và 0). 5 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Biểu Diễn Dữ Liệu • Cơ số 2 cũng được gọi là “hệ nhị phân - binary number system”. Các ký số (bit) của một số trong hệ nhị phân được nhân với luỹ thừa của 2. Ví dụ, tính giá trị thập phân (cơ số 10) của số nhị phân 10011010: 10011010 = 27 + 24 + 23 + 21 = 154 • Phép cộng trên hệ nhị phân: 0 + 0 = 0 0 + 1 = 1 1 + 1 = 10 (nhớ 1 - bit bên trái nhất) • Ví dụ, cộng hai số nhị phân 1100 và 0110: 1100 0110 10010 6 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Chiều Dài Từ Của Máy Tính • Mỗi máy tính khác nhau có thể truy xuất cùng lúc số bit khác nhau. Ví dụ, một máy tính có thể truy xuất 8 bit cùng lúc được gọi là “máy tính 8 bit”. Nói cách khác, máy tính đó có “chiều dài từ - word size” là 8 bit. • Máy tính PC đầu tiên của IBM sử dụng bộ xử lý 8088 của Intel có bus dữ liệu là 8 bit, nghĩa là nó có thể đọc/ghi 8 bit dữ liệu cùng lúc với thiết bị ngoại vi. • Ngày nay, hầu hết các máy tính có chiều dài từ là 32 hay 64 bit. 7 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Định Dạng Số Nguyên • Cho đến bây giờ, chúng ta chỉ thảo luận các số nguyên dương. Máy tính cũng cần thao tác với các số nguyên có dấu và cả số thực. • Để lưu trữ số có dấu, bit bên trái nhất (msb) được sử dụng làm bit dấu. Bit này có giá trị 0 nếu là số dương và 1 nếu là số âm. • Số nguyên âm được biểu diễn bằng cách lấy bù 2 (two’s complement) của số dương tương ứng. Để tính bù 2 của một số, đảo ngược các bit của số đó và cộng thêm 1. Ví dụ, bù 2 của 6 (00000110) trên máy tính 8 bit: 8 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Định Dạng Số Nguyên 11111001 +00000001 11111010 (−6) • Chúng ta có thể kiểm tra lại giá trị trên bằng cách cộng với 6, kết quả sẽ là 0: 11111010 (−6) +00000110 (+6) 100000000 (0, bỏ bit bên trái nhất) 9 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Định Dạng Số Thực • Biểu diễn số thực khó hơn số nguyên. Số thực gồm phần định trị (mantissa) và phần số mũ (exponent). • Phần định trị và phần số mũ có thể dương hoặc âm. Phần định trị lớn sẽ cho độ chính xác lớn, phần số mũ lớn sẽ cho miền trị lớn. • Trước đây vào thập niên 1980, các nhà sản xuất máy tính khác nhau đã sử dụng cách biểu diễn dữ liệu khác nhau. Vì vậy, chương trình và dữ liệu không tương thích trên các máy tính khác nhau. • Viện IEEE (Institute of Electrical and Electronic Engineers) đã đưa ra chuẩn để 10 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Định Dạng Số Thực biểu diễn số dấu chấm động dạng nhị phân sử dụng 32 và 64 bit. • Số dấu chấm động 32 bit có dạng như sau: dấu số mũ định trị SEEEEEEEEmmmmmmmmmmmmmmmmmmmmmmm • Bit msb là bit dấu, 8 bit kế tiếp là số mũ của cơ số 2 và 23 bit còn lại là phần định trị. • Dấu của số mũ được kết hợp vào giá trị biểu diễn của nó. Vì lý do kỹ thuật, chuẩn IEEE không sử dụng bù 2 để biểu diễn số mũ âm mà sử dụng phương pháp khác. • Ví dụ để biểu diễn 8.5, đầu tiên là chuyển 11 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Định Dạng Số Thực 8.5 về dạng nhị phân: 1000.1 • Theo chuẩn IEEE, chỉ có một ký số (bit) nằm bên trái dấu chấm. Do vậy, giá trị trên được viết lại: 1.0001 * 23 • Từ đây, chúng ta nhận ra số mũ của cơ số 2 là 3 và phần định trị là 0001. • Sự đặc tả chuẩn IEEE 32 bit sử dụng “độ lệch – bias” 127 ở phần số mũ (cách làm này không cần bit dấu riêng cho số mũ và làm cho việc so sánh các số mũ dễ dàng hơn là sử dụng bù 2, cũng làm cho dễ dàng thấy 12 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Định Dạng Số Thực được giá trị thật của nó). Trong ví dụ của chúng ta, phần số mũ có giá trị nhị phân của 127 + 3 = 130 (10000010). • Từ các kết quả trên, biểu diễn nhị phân của 8.5 sẽ là: 01000001000010000000000000000000 • Tính toán với số thực đòi hỏi máy tính phải làm việc nhiều hơn là với số nguyên. Vì vậy, một số máy tính được tích hợp bộ xử lý dấu chấm động (floating-point processor) để tăng tốc độ tính toán. • Bài tập tại lớp: a) Hãy cho biết vì sao giá trị 13 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Định Dạng Số Thực của độ lệch là 127 mà không phải là giá trị khác? b) Nếu giá trị của độ lệch là 127 thì miền trị của số mũ là bao nhiêu? 14 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Định Dạng Ký Tự • Dữ liệu dùng cho chương trình ở dạng ký tự nhiều hơn dạng số. Tên, địa chỉ, tựa đề, được biểu diễn bằng chuỗi ký tự. • Các ký tự được ánh xạ hay mã hoá thành các số nguyên. Có nhiều kiểu mã hoá như BCD (binary coded decimal), EBCDIC (extended BCD interchange coded). • Bộ mã ASCII (American Standard Code for Information Interchange) được đưa ra vào thập niên 1960 và trở thành bộ mã được ưa chuộng nhất. Ngày nay, Unicode được sử dụng phổ biến hơn bởi vì nó tương thích với bộ mã ASCII và cho phép mã hoá nhiều chữ 15 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Định Dạng Ký Tự cái phức tạp hơn tiếng Nga, Trung Quốc và những ngôn ngữ khác. Chúng ta sẽ sử dụng bộ mã ASCII để minh hoạ cho ý tưởng mã hoá ký tự, khi nó vẫn còn được sử dụng rộng rãi và mô tả đơn giản hơn là dùng Unicode. • Trong bộ mã ASCII, mỗi ký tự được gán một giá trị nguyên 7 bit. Cho ví dụ, ‘A’ = 65 (1000001), ‘B’ = 66 (1000010), ‘C’ = 67 (1000011), Bit thứ 8 trong byte ký tự được dùng như bit chẵn-lẻ (parity) để kiểm tra lỗi khi truyền thông tin hoặc mã hoá thành các ký tự dùng trong các phép toán, các ký tự có 16 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Định Dạng Ký Tự dấu hoặc các ký tự trang trí. • Một số ký tự điều khiển cũng được định nghĩa trong bộ mã ASCII. Các ký tự điều khiển không hiển thị ra màn hình nhưng được sử dụng để điều khiển thiết bị. Cho ví dụ, ‘line feed - LF’ = 10 (0001010), ‘tab’ = 11 (0001011), ‘backspace’ = 8 (0001000), • Để xuất chuỗi “Dog” và xuống dòng, một dãy các byte sau được gởi đi: 01000100 01101111 01100111 00001010 D o g LF • Tương tự, khi nhập dữ liệu từ bàn phím, bàn 17 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Định Dạng Ký Tự phím sẽ gởi một dãy các giá trị nguyên tương ứng với các ký tự đã nhập. • Làm thế nào để một chương trình biết dãy bit nào là của số nguyên, ký tự hay dấu chấm động. Câu trả lời là chương trình sẽ dựa vào kiểu dữ liệu của các đối tượng phần mềm trong chương trình. 18 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng CPU/ALU • CPU (Central Processing Unit) là thành phần mà người ta nghĩ đến đầu tiên khi mô tả về máy tính. Một chu kỳ trong máy tính von Neumann là: - Nạp một lệnh từ bộ nhớ vào CPU. - Giải mã và thực thi lệnh đó. • Thực thi lệnh bao gồm thực hiện các phép tính số học hay luận lý và cũng là nạp hay lưu trữ dữ liệu trong bộ nhớ. • Khi thực thi lệnh xong, máy tính sẽ lấy lệnh tiếp theo từ bộ nhớ và thực thi lệnh đó. Quá trình trên tiếp tục cho đến khi CPU gặp lệnh dừng. 19 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng CPU/ALU • CPU gồm đơn vị điều khiển (control unit - CU), đơn vị số học và luận lý (arithmetic and logic unit - ALU) và các thanh ghi. • Đơn vị điều khiển chịu trách nhiệm duy trì đều đặn chu kỳ lấy và thực thi lệnh, ALU thực thi các phép toán số học, so sánh (>, <, =, ) và luận lý (AND, OR, NOT, ). • Cả hai đơn vị điều khiển và ALU có các ô nhớ đặc biệt và tốc độ thực thi rất cao được gọi là các thanh ghi (register). • Một số thanh ghi có công dụng đặc biệt và một số có công dụng chung. • Các thanh ghi có công dụng đặc biệt là bộ 20 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng CPU/ALU đếm chương trình (program counter - PC) và thanh ghi lệnh (instruction register – IR). • Thanh ghi PC lưu giữ địa chỉ của lệnh thực thi kế tiếp. Khi đơn vị điều khiển bắt đầu chu kỳ lấy và thực thi lệnh, đơn vị điều khiển chuyển lệnh có địa chỉ được lưu trong PC đến thanh ghi IR. Khi này, đơn vị điều khiển tự động tăng thanh ghi PC để nó trỏ đến lệnh kế tiếp. • Đơn vị điều khiển giải mã lệnh trong IR và thực thi. Khi thực thi xong, đơn vị điều khiển lấy lệnh mà PC đang trỏ đến và tiếp tục chu kỳ mới. 21 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng CPU/ALU • Các thanh ghi có công dụng chung được sử dụng để lưu giữ dữ liệu cho CPU truy xuất. Truy xuất dữ liệu trong thanh ghi nhanh hơn truy xuất trong bộ nhớ. • Những máy tính khác nhau có số thanh ghi khác nhau, kích thước thanh ghi bằng với chiều dài từ của máy tính (16, 32, 64 bit, ) • Trong kiến trúc Intel x86, có 4 thanh ghi 32 bit có công dụng chung (EAX, EBX, ECX và EDX) và 4 thanh ghi 32 bit dùng để lưu địa chỉ stack và chuỗi (ESP, EBP, ESI và EDI). 22 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Tập Lệnh • Định nghĩa cốt lõi của một kiến trúc máy tính là là tập lệnh máy. Đó là danh sách các chỉ thị mà phần cứng máy tính có thể thực thi. • Các lệnh của máy tính bao gồm: - Nạp dữ liệu từ bộ nhớ vào thanh ghi. - Lưu dữ liệu từ thanh ghi vào bộ nhớ. - Nhảy đến vị trí nào đó trong chương trình. - Dịch các bit của một giá trị sang trái hay sang phải. - So sánh 2 giá trị. - Cộng giá trị của hai thanh ghi. - Thực hiện các phép toán luận lý, 23 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Tập Lệnh • Phần lớn, các lệnh của máy chỉ thực hiện các thao tác cơ bản. • Hợp ngữ (assembly language) là ngôn ngữ lập trình cấp thấp dạng gợi nhớ (mnemonic) để viết chương trình thay vì bằng ngôn ngữ máy. • Các tập lệnh khác nhau cho chúng ta thấy tại sao một chương trình chỉ thực thi được trên một số máy tính. • Ngày nay, hầu hết các chương trình được viết bằng ngôn ngữ cấp cao hơn hợp ngữ. • Khi một chương trình viết bằng ngôn ngữ 24 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Tập Lệnh lập trình cấp cao (Java, C, Python, ), bộ xử lý ngôn ngữ (language processor - trình biên dịch hay thông dịch) sẽ chuyển các lệnh của chương trình thành các lệnh mã máy để thực thi. • Nếu chúng ta muốn thực thi chương trình đó trên máy tính khác với tập lệnh khác, thường thì chỉ cần thay đổi bộ xử lý ngôn ngữ thích hợp với máy tính mới, mã nguồn của chương trình không thay đổi. • Lệnh máy gồm một dãy các bit 0 và 1. Một số bit được dùng làm mã lệnh (op-code). Ví dụ, một số mã lệnh như ADD, Jump, Compare và 25 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Tập Lệnh AND. Một số bit khác dùng làm toán hạng (operand). Toán hạng có thể là thanh ghi, biến bộ nhớ hay hằng. • Ví dụ lệnh máy của Intel x86 sau đây là lệnh ADD (cộng) để thực hiện thao tác “Cộng 40 vào thanh ghi DX”: 00000001 11000010 00000000 00101000 ADD DX 40 • Byte đầu tiên là mã lệnh của lệnh ADD. Byte thứ 2 cho biết toán hạng đích là thanh ghi DX, hai byte còn lại là toán hạng nguồn có trị là 40. 26 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Tập Lệnh • Một ví dụ khác là lệnh JMP (Jump – nhảy) để thực hiện thao tác “Thiết lập bộ đếm chương trình trỏ/nhảy đến địa chỉ 20.476”: 11101001 11111100 01001111 JMP byte thấp byte cao • Byte đầu tiên là mã lệnh của lệnh JMP. Byte thứ 2 và 3 lần lượt là byte thấp và byte cao của địa chỉ muốn nhảy đến. • Sau đây là một số lệnh máy tiêu biểu của tập lệnh máy Intel x86: 27 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Tập Lệnh MOV Gán toán hạng nguồn cho đích. ADD Cộng hai toán hạng. SUB Trừ hai toán hạng. DIV Chia thanh ghi cho toán hạng đích. IMUL Nhân số có dấu. DEC Giảm toán hạng đích 1 đơn vị. INC Tăng toán hạng đích 1 đơn vị. AND Lấy VÀ hai toán hạng. OR Lấy HOẶC hai toán hạng. XOR Lấy XOR hai toán hạng. NOT Lấy NOT toán hạng đích. IN Đọc dữ liệu từ cổng. 28 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Tập Lệnh OUT Xuất dữ liệu ra cổng. JMP Nhảy không điều kiện. JG Nhảy nếu lớn hơn. JZ Nhảy nếu bằng 0. CALL Gọi chương trình con. RET Trả về của chương trình con. CLC Xoá cờ nhớ. CMP So sánh hai toán hạng. HLT Dừng CPU. INT Thực hiện ngắt. LOOP Lặp vòng. NEG Chuyển thành số âm (bù 2). 29 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Tập Lệnh OUT Xuất dữ liệu ra cổng. JMP Nhảy không điều kiện. JG Nhảy nếu lớn hơn. JZ Nhảy nếu bằng 0. CALL Gọi chương trình con. RET Trả về của chương trình con. CLC Xoá cờ nhớ. CMP So sánh hai toán hạng. HLT Dừng CPU. INT Thực hiện ngắt. LOOP Lặp vòng. NEG Chuyển thành số âm. 30 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Tập Lệnh POP Lấy dữ liệu từ stack. PUSH Nạp dữ liệu vào stack. ROL Quay các bit sang trái. ROR Quay các bit sang phải. SHL Dịch các bit sang trái. SHR Dịch các bit sang phải. XCHG Hoán đổi nội dung hai toán hạng. 31 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Tập Lệnh POP Lấy dữ liệu từ stack. PUSH Nạp dữ liệu vào stack. ROL Quay các bit sang trái. ROR Quay các bit sang phải. SHL Dịch các bit sang trái. SHR Dịch các bit sang phải. XCHG Hoán đổi nội dung hai toán hạng. 32 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Bộ Nhớ • Bộ nhớ (memory) máy tính được tổ chức thành các ô (cell), mỗi ô được đánh địa chỉ riêng biệt. • Trước đây, các nhà sản xuất máy tính không thống nhất với nhau về kích thước của một đơn vị bộ nhớ. Các máy tính khác nhau sử dụng kích thước ô nhớ khác nhau. • Ngày nay, byte được dùng làm đơn vị của bộ nhớ máy tính. Hầu hết các máy tính, bất chấp chiều dài từ của nó là bao nhiêu, mỗi byte bộ nhớ có địa chỉ duy nhất và có thể đọc/ghi giá trị tại đó. 33 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Bộ Nhớ • Như chúng ta đã biết, đơn vị đo lường bộ nhớ như sau: - 1 kilobyte (KB) = 1.024 byte (210). - 1 megabyte (MB) = 1.048.576 byte (220). - 1 gigabyte (GB) = 1.037.741.824 byte (230). - 1 terabyte (TB) = 1.099.511.627.776 byte (240) - 1 petabyte (PB) = 1.125.899.906.842.624 (250) • Bộ nhớ được sử dụng để lưu giữ các lệnh của chương trình và dữ liệu. Các thao tác cơ bản với bộ nhớ là lưu/ghi và lấy/đọc/nạp. • Có ít nhất hai thanh ghi kết hợp với mạch điều khiển bộ nhớ để làm cho dễ dàng đọc và ghi 34 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Bộ Nhớ dữ liệu. Đó là thanh ghi MAR (thanh ghi địa chỉ - memory address register) và MDR (thanh ghi dữ liệu - memory data register). • Khi ghi dữ liệu, đầu tiên CPU chuyển giá trị được ghi đến MDR và địa chỉ để ghi đến MAR. Ở chu kỳ truy xuất bộ nhớ tiếp theo, giá trị trong MDR sẽ được chép vào địa chỉ trong MAR. • Khi đọc dữ liệu, đầu tiên CPU chứa địa chỉ để đọc vào MAR. Ở chu kỳ truy xuất bộ nhớ tiếp theo, giá trị tại địa chỉ trong MAR được chép vào MDR. Từ thanh ghi MDR, giá trị có thể được chuyển đến các thanh ghi khác 35 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Bộ Nhớ hoặc nơi nào đó. • Bộ nhớ chính của máy tính được biết đến là bộ nhớ RAM (bộ nhớ truy cập ngẫu nhiên - random access memory). Chúng ta có thể truy xuất bất kỳ địa chỉ nào của bộ nhớ thì thời gian truy xuất là như nhau. • Ngoài bộ nhớ chính, các nhà thiết kế máy tính cũng tích hợp vào CPU một bộ nhớ có dung lượng nhỏ, tốc độ truy cập nhanh được gọi là bộ nhớ cache (bộ nhớ đệm). • Bộ nhớ cache lưu giữ nội dung của dữ liệu đã được truy cập để sau này có thể dùng lại, nhằm làm tăng tốc độ của máy tính. 36 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Nhập/Xuất • Hầu hết dữ liệu sử dụng cho chương trình không nằm trên máy tính. Khi dữ liệu được xử lý xong, chúng ta thường muốn chúng hiển thị ra màn hình hay xuất ra máy in. • Có nhiều thiết bị nhập/xuất khác nhau: - Giao tiếp với người: bàn phím, chuột, màn hình. - Máy tính trực tiếp sử dụng: đĩa, thiết bị kết nối mạng. • Các thiết bị nhập/xuất có tốc độ rất khác nhau, nhưng tất cả đều chậm hơn CPU và bộ nhớ chính. 37 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Nhập/Xuất • Trong những máy tính trước đây, CPU sẽ đợi để nhập ký tự. Một lệnh máy giao tiếp với bàn phím để sẵn sàng nhận ký tự và lệnh máy kế tiếp sẽ kiểm tra xem ký tự đã nhập chưa. Nếu ký tự chưa nhập, chương trình sẽ lặp vòng để kiểm tra (polling). Phương pháp này được gọi là “programmed I/O with polling” hay “busy waiting”. • Các máy tính ngày nay sử dụng hệ thống ngắt (interrupt system) để tránh trường hợp phải chờ và hệ điều hành quản lý tất cả nhập/xuất. • Mỗi thiết bị nhâp/xuất được kết nối với máy 38 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Nhập/Xuất tính thông qua “bộ điều khiển nhập/xuất - I/O controller”. Bộ điều khiển nhập/xuất có gắn bộ nhớ với dung lượng nhỏ để làm bộ đệm (buffer) chứa dữ liệu tạm thời trong quá trình nhận hay gởi. • Khi chương trình yêu cầu xuất, hệ điều hành sẽ chuyển dữ liệu đến bộ nhớ đệm của bộ điều khiển nhập/xuất, bộ điều khiển nhập/xuất sẽ chuyển dữ liệu đến thiết bị xuất. Khi dữ liệu được chuyển xong, bộ điều khiển nhập/xuất tạo một ngắt (interrupt) để báo cho hệ điều hành biết là đã chuyển xong. Hệ điều hành sẽ đáp lại ngắt đó bằng cách bắt đầu thực thi thao tác xuất khác. 39 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Nhập/Xuất • Khi chương trình yêu cầu nhập, hệ điều hành sẽ tạm dừng thực thi nó và ra lệnh cho bộ điều khiển nhập/xuất của thiết bị bắt đầu đọc dữ liệu. Sau đó, hệ điều hành chuyển điều khiển của CPU đến chương trình thứ hai để thực thi, trong khi chương trình đầu đang đợi để nhập. Khi dữ liệu được nhập xong, bộ điều khiển nhập/xuất sẽ sinh ra một ngắt. Hệ điều hành sẽ đáp lại bằng cách tạm dừng chương trình thứ hai, rồi chuyển dữ liệu từ bộ nhớ đệm của bộ điều khiển nhập/xuất đến chương trình đầu và tiếp tục thực thi chương trình đầu. 40 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Nhập/Xuất • Các thiết bị nhập/xuất được phân làm 2 loại là thiết bị ký tự (character device) và thiết bị khối (block device): 1. Thiết bị ký tự: giao tiếp với bên ngoài từng byte, các byte này không có địa chỉ. Nghĩa là chỉ có thể truy xuất dữ liệu theo dạng tuần tự. Đa số các thiết bị nhập/xuất dùng với máy tính thuộc loại này như bàn phím, chuột, card mạng, máy quét, máy in, 2. Thiết bị khối: giao tiếp với bên ngoài từng khối dữ liệu, mỗi khối có địa chỉ cố định và độc lập. Các thiết bị loại này như CD-ROM, âm thanh, các thiết bị hiển thị, 41 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Nhập/Xuất • Các thiết bị ký tự sẽ sinh ra ngắt cho mỗi ký tự được truyền đi, các thiết bị khối sẽ sinh ra ngắt chỉ khi toàn bộ khối đó được truyền đi. • Hầu hết các máy tính ngày nay đều có bộ điều khiển truy xuất bộ nhớ trực tiếp (direct memory access - DMA) để dùng với thiết bị khối. • Bộ điều khiển DMA dùng để truy xuất trực tiếp bộ nhớ và chia sẻ công việc truy xuất bộ nhớ với CPU. DMA truyền dữ liệu trực tiếp giữa bộ đệm của bộ điều khiển nhập/xuất với bộ nhớ chính, nó không yêu cầu bất cứ phục vụ nào từ CPU. 42 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Chương 4: PHẦN MỀM Nội Dung 1. Các thệ hệ của ngôn ngữ lập trình. 2. Trình biên dịch và trình thông dịch. 3. Máy ảo. 4. Lập trình thủ tục. 5. Lập trình hướng đối tượng. 6. Ngôn ngữ kịch bản. 7. Ngôn ngữ lập trình hàm. 8. Cú pháp ngôn ngữ và ngữ nghĩa. 2 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình • Các nhà khoa học máy tính gọi chung các ngôn ngữ lập trình, các chương trình và các sản phẩm là phần mềm (software). • Một lệnh máy là một dãy các bit 0 và 1 được chứa trong bộ nhớ máy tính. • Khi máy tính đọc bộ nhớ, nó xác định xem dãy bit đã đọc có phải là lệnh máy không. Nếu đúng, máy tính thực thi lệnh đó, ngược lại máy tính sẽ dừng vì lệnh không hợp lệ. • Mỗi máy tính (một họ CPU) có một tập lệnh máy hữu hạn. Hầu hết các máy tính ngày nay có từ 75 đến 150 lệnh máy trong tập lệnh. • Mỗi kiến trúc máy tính được thể hiện trong 3 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình tập lệnh. Các tập lệnh của các kiển trúc khác nhau sẽ khác nhau. Ví dụ, tập lệnh của Intel Pentium khác với của Sun SPARC. Cả khi thực hiện cùng một tác vụ, một lệnh của kiến trúc này cũng sẽ khác với kiến trúc khác. • Trong các máy tính trước đây, việc lập trình được thực hiện trực tiếp bằng lệnh máy. Người lập trình làm việc với các bit 0 và 1 để viết mã cho mỗi lệnh. Ví dụ sau là ba lệnh của máy tính 16 bit để cộng hai giá trị được chứa trong bộ nhớ tại địa chỉ 64 và 65 và lưu kết quả vào địa chỉ 66: 4 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình 0110000001000000 Nạp giá trị tại 64 vào AX 0100000001000001 Cộng với giá trị tại 65. 0111000001000010 Chứa giá trị AX vào 66. • Khi tất cả lệnh máy được tạo, người lập trình lưu chúng vào bộ nhớ. Sau đó, thiết lập thanh ghi PC trỏ đến lệnh đầu tiên của chương trình và thực thi. • Các thao tác cơ bản của máy tính là đọc lệnh trong bộ nhớ được trỏ bởi thanh ghi PC, tăng thanh ghi PC, thực thi lệnh và lặp lại. • Một sự cải tiến trước đây để lập trình hiệu quả hơn là sử dụng hợp ngữ (assembly language). Trong hợp ngữ, chúng ta có thể 5 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình đọc mã lệnh bằng từ gợi nhớ (chữ và số - mnemonic) thay vì mã máy và mỗi từ gợi nhớ ứng với một lệnh máy. • Hợp ngữ được gọi là ngôn ngữ thế hệ thứ hai (second-generation language). Trong hợp ngữ, người lập trình viết mã lệnh gợi nhớ và nó sẽ được biên dịch (bằng trình hợp dịch – assembler) trực tiếp thành mã máy. Một số từ gợi nhớ tiêu biểu như sau: - LDA m: Nạp giá trị tại địa chỉ m vào thanh ghi AX. - ADA m: Cộng giá trị của AX với giá trị tại địa chỉ m, kết quả chứa trong AX. 6 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình - ALS: Dịch các bit trong AX sang trái 1 đơn vị. - SSA: Nếu bit msb của AX là 1, bỏ qua lệnh kế tiếp. Ngược lại, thực thi lệnh kế tiếp. - JMP m: Nhảy đến địa chỉ m. • Sau đây là mã hợp ngữ để viết lại 3 lệnh máy ở trên: LDA 100 // 100 octal = 64 ADA 101 // 101 octal = 65 STA 102 // 102 octal = 66 • Người lập trình thường sử dụng hợp ngữ để viết chương trình vì nó gần gũi với phần 7 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình cứng máy tính hoặc những chương trình tối ưu tốc độ hay bộ nhớ. • Như là một công cụ giáo dục, lập trình hợp ngữ rất quan trọng, bởi vì nó là cách tốt nhất để biết được máy tính làm gì và làm như thế nào. • Vào năm 1954, ngôn ngữ thế hệ thứ ba ra đời. Ngôn ngữ đó là FORTRAN, do John Backus của IBM phát minh. • FORTRAN là chữ viết tắt của FORmula TRANslation. Ngôn ngữ này giúp người lập trình làm việc ở mức trừu tượng cao hơn. • Thay vì bị hạn chế bởi tập lệnh máy, người 8 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình lập trình bây giờ sử dụng các câu lệnh giống như tiếng Anh và các biểu thức toán học. Ngôn ngữ cũng bao gồm các lệnh rẽ nhánh, lặp và nhập/xuất. • Sau đây là câu lệnh của FORTRAN. Các tên biến X, Y và Z trở thành tên đại diện cho các vị trí nhớ. Câu lệnh sẽ cộng nội dung của Y với Z và chứa tổng vào X: X = Y + Z • So sánh với hợp ngữ, câu lệnh của FORTRAN dễ đọc, dễ viết và ngắn gọn hơn. • FORTRAN là “ngôn ngữ thủ tục” (procedural language). Nghĩa là, người lập trình phải tổ 9 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình chức hợp lý một dãy các bước cần thiết để thực thi tác vụ nào đó. • Các ngôn ngữ thủ tục còn được gọi là các “ngôn ngữ mệnh lệnh” (imperative language), bởi vì các câu lệnh của ngôn ngữ là những mệnh lệnh cho máy tính – các bước của chương trình chỉ định mỗi hành động của máy tính. • Khác với các ngôn ngữ mệnh lệnh là các ngôn ngữ “hướng đối tượng” (object- oriented). Hầu hết, nhưng không phải là tất cả các chương trình ngày nay được viết bằng các ngôn ngữ mệnh lệnh. 10 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình • Cho đến nay, các ngôn ngữ thế hệ thứ ba gồm: LISP (for LISt Processing), Cobol, PL/1, BASIC, ADA, C, Smalltalk, C++, Java. Trong đó, Smalltalk, C++ và Java là các ngôn ngữ lập trình hướng đối tượng. 11 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Trình Biên Dịch và Trình Thông Dịch • Với sự ra đời của FORTRAN, chương trình trở nên phức tạp hơn để tạo ra mã máy. Một chương trình khác được gọi là trình biên dịch (compiler) dùng để dịch ngôn ngữ lập trình cấp cao thành mã máy. • Đầu vào của trình biên dịch là mã nguồn được viết bằng ngôn ngữ cấp cao. Đầu ra của trình biên dịch là mã máy. • Ví dụ sau là đoạn mã của ngôn ngữ FORTRAN: DIMENSION X(1000) READ(*, 1) N, M FORMAT(2I5) WRITE(*, 2) M, N 12 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Trình Biên Dịch và Trình Thông Dịch FORMAT('AVERAGES ON ', I6, ' TESTS FOR EACH OF ', I6, 1’ SUBJECTS’) EM=M DO 5 J=1, N READ(*, 3) ID, (X(K), K=1, M) FORMAT(I5, 25F3.0/ (5X, 25F3.0)) SUM = 0.0 DO 4 K=1, M SUM = SUM + X(K) AV = SUM / EM WRITE(*, 6 ) J, ID, AV FORMAT(I6, 3X, 'SUBJECT ', I6, 3X, 'AV= ', F9.2) STOP END 13 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Trình Biên Dịch và Trình Thông Dịch • Trình biên dịch xử lý mã nguồn qua hàng loạt các bước: 1. Bước đầu tiên gọi là “quét” (scanning) hay “phân tích từ vựng” (lexical analysis) và xuất ra một chuỗi các “token” (từ tố/thẻ từ). Token là từ của ngôn ngữ, ví dụ “READ”, “FORMAT”, “AV”, “4” và “3X” là các token trong chương trình ví dụ. 2. Kế đến, trình biên dịch “phân tích từ loại” (parse) chuỗi token đó. Bước này được gọi là “phân tích cú pháp” (syntax analysis). Xem xét “văn phạm” hay các qui tắc của ngôn ngữ. Trình biên dịch sử dụng “cây 14 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Trình Biên Dịch và Trình Thông Dịch phân tích cú pháp” (parse tree) để thẩm tra các lệnh trong mã nguồn là những lệnh hợp lệ của ngôn ngữ. Tại bước này, trình biên dịch trả về thông báo lỗi, ví dụ thiếu dấu phẩy hay sai từ khoá. 3. Nếu tất cả câu lệnh đều hợp lệ, trình biên dịch tiếp tục “phân tích ngữ nghĩa” (semantic analysis). Trong giai đoạn này, ý nghĩa (meaning) của các lệnh được tạo, các lệnh sẽ được chuyển thành các mã thực thi (executable code). • Các trình biên dịch ngày nay thường biên dịch chương trình nguồn thành “ngôn ngữ 15 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Trình Biên Dịch và Trình Thông Dịch trung gian” (intermediate language) và sau đó sẽ chuyển thành mã máy. Trong khi các trình biên dịch trước đây hoặc là tạo mã hợp ngữ và sau đó sẽ hợp dịch (assemble) bằng trình hợp dịch (assembler) hoặc là tạo trực tiếp thành mã máy. • Ưu điểm của trình biên dịch ngày nay là có thể biên dịch nhiều ngôn ngữ khác nhau thành mã trung gian ở dạng tổng quát, không phụ thuộc vào môi trường/nền (platform) và sau đó có thể sinh ra mã máy tối ưu cho từng loại máy. • Kết quả của sự biên dịch chương trình là tập 16 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Trình Biên Dịch và Trình Thông Dịch tin mã đối tượng (object code). Nó là tập tin nhị phân của các lệnh máy và sẽ thực thi khi chương trình chạy. • Trình biên dịch thực hiện dịch mã nguồn thành mã thực thi chỉ 1 lần, khi chương trình chạy, các mã này sẽ thực thi ngay lập tức. • Đối với trình thông dịch (interpreter) thì khác. Trình thông dịch thực hiện dịch từng dòng mã nguồn thành mã máy ở mỗi thời điểm khi chương trình thực thi. Ví dụ, BASIC là ngôn ngữ sử dụng trình thông dịch. • Nói chung, một chương trình được thực thi bằng trình thông dịch sẽ chạy chậm hơn 17 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Trình Biên Dịch và Trình Thông Dịch chương trình đã được biên dịch thành mã máy. Bởi vì, ở mỗi thời điểm trình thông dịch phải phân tích từng dòng lệnh và chuyển nó thành mã máy khi chương trình chạy. • Trình thông dịch thường cung cấp thông báo chuẩn đoán tốt hơn vì nó làm việc trực tiếp với từng dòng lệnh. • Sự khác biệt giữa ngôn ngữ sử dụng trình biên dịch và thông dịch đôi khi cũng không rõ ràng. Có một số ngôn ngữ sử dụng cả trình thông dịch và biên dịch như BASIC, PERL, LISP, Java, 18 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Máy Ảo • Máy ảo (virtual machine) là máy tính được định nghĩa bởi phần mềm hơn là phần cứng. Máy ảo chạy các chương trình giống như máy tính thật, nhưng máy ảo thực sự được điều khiển bởi chương trình khác, một sự tạo dựng bởi phần mềm đó là lấy, giải mã và thực thi các lệnh của chương trình. • Thuật ngữ máy ảo mô tả một lớp trừu tượng được thêm vào giữa người dùng và phần cứng, vì thế các nhà khoa học máy tính cũng sử dụng thuật ngữ này để mô tả phần mềm tạo nên sự thể hiện ở các dạng khác nhau của máy tính. 19 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Thủ Tục • Theo nhiều người, lập trình thủ tục (procedural programming) là mô hình tự nhiên. Một chương trình được mô tả đơn giản chỉ là một danh sách các lệnh được thực thi theo trình tự, tức là một thủ tục. • Các ngôn ngữ lập trình thủ tục cũng được gọi là các ngôn ngữ mệnh lệnh (imperative language). • Trong lập trình thủ tục, mã lệnh cho một công việc cụ thể được chứa trong một thủ tục có tên. Thủ tục cũng còn được gọi là subroutine. Cho ví dụ, hãy tạo một thủ tục để tìm độ lệch chuẩn của một dãy số. 20 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Thủ Tục • Độ lệch chuẩn được định nghĩa như sau. Gọi σ là độ lệch chuẩn và 𝒙𝒙� là trung bình của các phần tử trong dãy số: 𝝈𝝈 = (�𝒙𝒙𝒊𝒊𝟐𝟐 − 𝒏𝒏𝒙𝒙�𝟐𝟐)𝒏𝒏 𝒊𝒊=𝟏𝟏 /𝒏𝒏 • Sau đây là thủ tục được viết bằng mã giả để tính độ lệch chuẩn: 21 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Thủ Tục SUM = 0.0, SUMSQUARES = 0.0 n = size of the array of scores Start with the first score and continue until all the scores have been processed SUM = SUM + score SUMSQUARES = SUMSQUARES + score2 End of loop MEAN = SUM / n Return SquareRoot((SUMSQUARES − n * MEAN2) / n) • Sau đây là đoạn mã lệnh được viết bằng Java với lớp Sd chứa phương thức stdDev(): 22 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Thủ Tục import java.lang.Math; class Sd { public static void main(String args[]) { float[] numbers = {3, 5, 7, 9}; System.out.println("Std. dev. = " + stdDev(numbers)); } public static float stdDev(float scores[]) { float sum = 0; float sumSquares = 0; int n = scores.length; 23 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Thủ Tục for(int i = 0; i < n; i++) { sum = sum + scores[i]; sumSquares = sumSquares + scores[i]*scores[i]; } float mean = sum / n; float variance = (sumSquares - n * mean * mean) / n; return (float)Math.sqrt(variance); } } 24 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Thủ Tục • Trong lập trình thủ tục, các mã lệnh có thể được viết trong một khối gọi là thủ tục (procedure)/hàm (function). Khối này được truy xuất thông qua tên của nó và có thể tái sử dụng. • Thủ tục nhận tập giá trị nhập và trả về tập kết quả. Lưu ý là các biến bên trong thủ tục như sum và sumSquares có tầm vực (scope) chỉ bên trong thủ tục đó. Điều này giúp tránh lẫn lộn các biến đang sử dụng với các biến cùng tên ở tầm vực/khối bao. • Một thủ tục có thể được truy xuất bởi chương trình khác. Chỉ đơn giản là chúng ta thêm thủ tục đó vào thư viện. 25 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Thủ Tục • Khái niệm lập trình cấu trúc (structured programming) được hiểu như là tập con của lập trình thủ tục. Phương pháp lập trình cấu trúc thường đi đôi với phương pháp phân tích trên xuống (top-down). Tác vụ của chương trình được chia thành nhiều thủ tục/hàm. Điều này rất quan trọng trong thiết kế chương trình, bởi vì chương trình được cục bộ hóa nên dễ đọc, dễ bảo trì, độ tin cậy cao, tái sử dụng và tạo thư viện . • Lập trình cấu trúc sử dụng các lệnh có cấu trúc như các lệnh rẽ nhánh, lặp để gọi các thủ tục/hàm đã được định nghĩa. Các ngôn ngữ 26 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Thủ Tục hỗ trợ lập trình cấu trúc như ALGOL, ADA, Pascal, C, • Nhược điểm: Trong lập trình cấu trúc, giải thuật luôn phụ thuộc chặt chẽ vào cấu trúc dữ liệu, do đó khi thay đổi cấu trúc dữ liệu, phải thay đổi giải thuật. Nghĩa là phải viết lại chương trình. • Khái niệm lập trình không cấu trúc (unstructured/non-structured programming) được hiểu là chương trình có sử dụng các lệnh GOTO hay JUMP. Kết quả sẽ làm cho chương trình khó đọc, khó tìm lỗi, khó tái sử dụng. • Các ngôn ngữ hỗ trợ lập trình không cấu trúc như Assembly, BASIC, 27 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Hướng Đối Tượng • Lập trình hướng đối tượng (Object-oriented programming – OOP) được phát triển sau này, nó cung cấp độ tin cậy và tái sử dụng phần mềm xa hơn nữa. • Thay vì lập trình thủ tục, lập trình hướng đối tượng dựa vào các đối tượng phần mềm như là các đơn vị của chương trình. • Một đối tượng là một thể hiện (instance) của một “lớp” (class). Để tạo ra một thể hiện, người ta sử dụng các đặc tả của lớp đó. Ví dụ MyCar là một thể hiện của lớp Automobile: có 4 bánh, có động cơ, có ghế ngồi, 28 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Hướng Đối Tượng • Một thể hiện của một lớp có “trạng thái” hay các nét đặc trưng (characteristic) của riêng nó. Ví dụ, màu của thể hiện MyCar là đỏ và của YourCar là xanh. Hoặc MyCar có 170 hp (mã lực) và YourCar có 200 hp, Tất cả các đặc trưng màu sắc, dung tích động cơ (và các đặc trưng khác) được gọi là thuộc tính (attribute) hay các biến thể hiện (instance variable). • Các đối tượng cũng có “hành vi” (behavior). Hành vi được xác định bởi các thủ tục của lớp đó, các thủ tục như thế được gọi là các phương thức (method). Ví dụ, lớp 29 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Hướng Đối Tượng Automobile có phương thức như changeSpeed() để thay đổi tốc độ xe nhanh hay chậm hơn, park() xác định kích thước của chỗ đậu xe. Phương thức còn được gọi là phương thức thể hiện (instance method) • Lập trình hướng đối tượng “đóng gói” (encapsulate) trạng thái và hành vi của đối tượng. Chương trình chỉ có thể truy xuất các thuộc tính public và phương thức public của đối tượng. • Một ý tưởng quan trọng trong lập trình hướng đối tượng là “sự thừa kế” (inheritance). Nghĩa là chúng ta có thể tạo một lớp mới “mạnh 30 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Hướng Đối Tượng hơn” bằng cách thừa kế từ lớp trước đó và thêm những tính năng mới của nó. Ví dụ, lớp Limousine thừa kế từ lớp Automobile. • Có liên quan đến thừa kế là khái niệm về “tính đa hình” (polymorphism) - tính chất thể hiện nhiều hình thái của đối tượng. Tính đa hình là sự thực thi của một phương thức có thể cho kết quả khác nhau phụ thuộc vào lớp của đối tượng mà phương thức đó được gọi. • Ví dụ, lớp Automobile và Limousine (xe ô tô hạng sang) đều có phương thức park(). Tuy nhiên, phương thức park() của Limousine yêu cầu chỗ đậu xe lớn hơn trong phương thức park() của Automobile. 31 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Kịch Bản • Ngày nay, có một số ngôn ngữ lập trình là ngôn ngữ kịch bản (scripting language). Ý tưởng ban đầu của “script” (kịch bản) là một tập các lệnh của hệ điều hành được đặt trong tập tin. Khi người sử dụng thực thi tập tin kịch bản (script file), tập lệnh trong đó được thực thi. Các kịch bản rất hữu dụng trong việc tự động hoá công việc thường ngày. • Do tính hữu dụng của ngôn ngữ kịch bản đã khơi dậy nhiều nhà phát minh phát triển ngôn ngữ mới với nhiều tính năng và tiện lợi hơn. Các ngôn ngữ như Perl, PHP, Python, JaVaScript, là những ngôn ngữ kịch bản. Tuy nhiên, ngôn ngữ kịch bản được thông dịch, vì thế tốc độ thực thi không phải là ưu điểm chính của nó. 32 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Lập Trình Hàm • Các ngôn ngữ lập trình hàm (functional programming language) được phát minh từ rất sớm trong lịch sử máy tính. Năm 1958, John McCarthy đã cho ra đời ngôn ngữ LISP (LISt Processing). • Ngôn ngữ lập trình hàm thường dùng để xử lý các hàm toán học. Một hàm cần một hay nhiều đối số và trả về một trị. Cho ví dụ, phương trình của đường parabol là: f(x) = 2x2 + 5 Khi chúng ta cung cấp giá trị cho x (ví dụ x = 3), thì hàm trên sẽ trả về kết quả như sau: f(3) = 2(3)2 + 5 = 23 33 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Lập Trình Hàm • Với ngôn ngữ lập trình hàm, việc tính toán được thực hiện bằng cách truyền các đối số đến một hàm và nhận kết quả trả về của hàm đó. • Trong các ví dụ, chúng ta sẽ sử dụng ngôn ngữ Scheme. Ngôn ngữ Scheme được gọi là ngôn ngữ thao tác ký hiệu (symbolic manipulation), ra đời năm 1975 và thuộc họ LISP. • Một biểu thức trong Scheme là một atom (nguyên tử) hay một list (danh sách). Một atom là một số, ký tự, tên hay hàm. Một list là một tập các biểu thức được chứa trong dấu 34 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Lập Trình Hàm ngoặc (). Các phần tử trong list có thể là atom hay là một list khác. • Trong bất kỳ ngôn ngữ lập trình hàm nào, một số hàm cơ bản sẽ được tạo sẵn. Ngoài ra, người lập trình có thể tự định nghĩa hàm. Sau đây là một số ví dụ về Scheme: 1.(+ 3 5) → 8 2.(+ 3 5 7 4 2) → 21 3.(/ (+ 3 5) (- 7 5)) → 4 4.(list 1 5 6) →(1 5 6) 5.(car (list 1 5 6)) → 1 6. (cdr (list 1 5 6)) → (5 6) 35 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Scheme/ LISP Ngôn Ngữ Lập Trình Hàm 7.(define sum (lambda (n m) (+ n m))) > (sum 4 3) 7 Trong ví dụ trên, định nghĩa hàm sum sử dụng ký pháp lambda (lambda notation). Ưu điểm là không phân biệt định nghĩa hàm với định nghĩa giá trị. 8.(define factorial (lambda (n) (if (<= n 1) 1 (* n (factorial( - n 1)))))) 36 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Lập Trình Hàm > (factorial 5) 120 • Lưu ý: Thay vì sử dụng các lệnh if lồng nhau, Scheme cho phép sử dụng lệnh cond. Ví dụ: cond((>= grade 8) “Gioi”) ((>= grade 7) “Kha”) ((>= grade 6) “TB kha”) ((>= grade 5) “Trung binh”) (else “Kem”))) 37 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Lập Trình Hàm 9.(define listSum (lambda (n) (cond ((null? n) 0) ((null? (cdr n)) (car n)) (else (+ (car n) (listSum( cdr n)))) ))) > (listSum (list 2 4 5)) 11 • Lập trình hàm thường được sử dụng trong trí tuệ nhân tạo (artificial intelligence) và hệ chuyên gia (expert system). 38 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa • Trước khi biên dịch chương trình ngôn ngữ cấp cao thành mã máy, bộ xử lý ngôn ngữ (chương trình dịch) phải thực hiện nhiều tác vụ như phân tích từ vựng (lexical analysis), phân tích cú pháp (syntax analysis) và sinh mã (phân tích ngữ nghĩa - semantic analysis). • Trong bước phân tích từ vựng, chương trình dịch đọc dãy ký tự từ tập tin mã nguồn và tạo các token của ngôn ngữ đó. Token là từ của ngôn ngữ và có nhiều dạng, có thể là từ khoá (key word) như String, một ký hiệu như ‘+’, một danh hiệu như myCount, một hằng như 3.14 hay một chuỗi ký tự như “Please enter your name:”. 39 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa • Sau khi các token được tạo, bộ phân tích cú pháp (parser) xây dựng cây phân tích cú pháp (parse tree) theo các qui tắc văn phạm của ngôn ngữ và tìm lỗi nếu có. • Cú pháp của ngôn ngữ mô tả các lệnh hợp lệ của ngôn ngữ đó. Cú pháp đúng, không đảm bảo là kết quả của chương trình đúng, nhưng một chương trình đúng phải có cú pháp đúng. • Ngày nay, các qui tắc cú pháp thường biểu diễn ở dạng Backus-Naur form (BNF) hay BNF mở rộng (EBNF). Từ “Backus-Naur” được 40 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa ghép từ tên John Backus là nhà phát minh ra ngôn ngữ FORTRAN và Peter Naur. • BNF sử dụng một tập các qui tắc hay luật sinh (production rule) để mô tả văn phạm hay cú pháp. • Bên trái của luật sinh, BNF cho thấy một khái niệm ngôn ngữ học được biết như là các “ký hiệu không kết thúc” (non-terminal). Ví dụ, ký hiệu không kết thúc trong tiếng Anh là “câu” (sentence) và “ngữ động từ” (verb phrase). Trong ngôn ngữ lập trình, ký hiệu không kết thúc có thể là “expression” hay “term”. 41 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa • Bên phải của luật sinh, BNF cho thấy sự kết hợp của ký hiệu không kết thúc và/hoặc ký hiệu kết thúc thay thế cho ký hiệu không kết thúc bên trái. • Ví dụ sau là văn phạm của các biểu thức toán học: 1.expression → term | expression addop term 2.term → factor | term multop factor 3.factor → identifier | number | -factor | (expression) 4.addop → + | - 5.multop → * | / 42 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa • Các vạch đứng “|” nghĩa là “hoặc”. Các luật sinh 3, 4, và 5 tạo các ký hiệu kết thúc. • Trong luật sinh 1, một biểu thức có thể là term hoặc là một biểu thức khác addop (+ | -) với term. • Trong luật sinh 2, term có thể là factor hoặc là một term khác multop(* | /) với factor. • Cho ví dụ, phân tích cú pháp biểu thức sau dựa vào văn phạm ở trên: X * 3 + 4 • Áp dụng luật sinh 1: X * 3 + 4 → (X * 3) addop term expr + 4 43 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa • Áp dụng luật sinh 2 và 3 cho term: term → factor → number 4 • Áp dụng luật sinh 1 và 2 cho (X * 3): (X * 3) → term → term multop factor (X * 3) X * 3 • Áp dụng luật sinh 3 cho factor: factor → number 4 • Áp dụng luật sinh 2 và 3 cho term: term → factor → identifier X X X 44 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa • Sự phân tích một biểu thức thành các ký hiệu kết thúc dựa vào các qui tắc văn phạm được gọi là dẫn xuất (derivation). Kết quả của sự dẫn xuất thành công là cây phân tích cú pháp hay cây cú pháp (syntax tree). Sau đây là cây phân tích cú pháp của dẫn xuất mà chúng ta vừa thực hiện: 45 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa 46 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa • Để tính ý nghĩa của biểu thức, cây phân tích cú pháp được duyệt (traverse) từ dưới lên. Tính phép nhân trước rồi đến phép cộng. Lúc này, trình biên dịch sẽ tạo các lệnh máy tương ứng để thực thi biểu thức. Đây là giai đoạn cuối cùng được gọi là sinh mã (code generation). 47 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Chương 6: CƠ SỞ DỮ LIỆU Nội Dung 1. Giới thiệu. 2. Các loại cơ sở dữ liệu. 3. Các ưu điểm khi sử dụng CSDL. 4. Mô hình hóa miền dữ liệu. 5. Xây dựng CSDL quan hệ từ mô hình dữ liệu 6. Chuẩn hóa dữ liệu. 7. Ngôn ngữ SQL. 8. Ngôn ngữ định nghĩa dữ liệu (DDL). 9. Ngôn ngữ thao tác dữ liệu (DML). 2 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Giới Thiệu • Ngày nay, CSDL có mặt ở khắp nơi. Hầu hết trong các ứng dụng, chúng ta đều gặp CSDL. CSDL tạo hiệu quả, an toàn và linh động trong việc lưu trữ dữ liệu. • Ngay sau khi máy tính thế hệ thứ hai ra đời (sau thập niên 1950), sự có mặt của các ngôn ngữ lập trình cấp cao đòi hỏi dung lượng lưu trữ lớn. Dữ liệu được chứa trong các tập tin (tập các mẫu tin) trên băng từ. Cách lưu trữ này sớm bộc lộ những trở ngại nhất định. • Đầu tiên là những tập tin lớn, cần thời gian tìm kiếm lâu hơn. Chúng ta hãy xem lại các giải thuật đã thảo luận trước đây, thời gian 3 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Giới Thiệu của giải thuật tìm kiếm tuần tự là O(n). Vì thế, những tập tin lớn, cần nhiều thời gian hơn để tìm phần tử nào đó. Chẳng hạn, chúng ta cần tìm một khách hàng trong hàng triệu khách hàng là điều không thể. • Một vấn đề khác trong việc tổ chức dữ liệu không hợp lý, chẳng hạn cùng một thông tin của khách hàng nhưng được lưu lại nhiều lần sẽ dẫn đến việc sử dụng bộ nhớ lưu trữ không hiệu quả. 4 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Loại Cơ Sở Dữ Liệu • Bắt đầu từ sau thập niên 1960, các hệ CSDL (database system) đã được phát triển. Hai loại CSDL đầu tiên là loại phân cấp (hierarchy) và mạng (network). IBM đưa ra DL/1 là mô hình CSDL phân cấp và hàng loạt phần cứng và phần mềm khác cùng với mô hình CSDL mạng. • Các cấu trúc CSDL phân cấp và mạng được tổ chức thành nhiều tập tin quan hệ với nhau để truy cập thông tin nhanh hơn, bảo mật tốt hơn và dễ dàng cập nhật hơn. Tuy nhiên, các cấu trúc này khá phức tạp và không linh động. 5 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Loại Cơ Sở Dữ Liệu • Vào năm 1970, E. F. Codd của IBM đưa ra mô hình CSDL quan hệ (relational database). Mô hình quan hệ dựa nhiều vào lý thuyết toán. • Theo mô hình này, dữ liệu được chứa trong các bảng, gọi là các “quan hệ”. Mỗi quan hệ/bảng lưu giữ thông tin về một kiểu thực thể (entity type) và các thực thể quan hệ nhau bởi thông tin đã lưu trong các bảng đó. • Codd cũng đưa ra một ngôn ngữ để truy vấn dữ liệu dựa vào lý thuyết tập hợp. Vào thập niên 1980, ngôn ngữ truy vấn có cấu trúc (Structured Query Language - SQL) được thế giới biết đến. Sau đó, IBM bắt đầu bán CSDL 6 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Loại Cơ Sở Dữ Liệu quan hệ có tên là DB2. • Ngày nay, mô hình dữ liệu quan hệ được sử dụng rộng rãi và là mô hình mà chúng ta sẽ thảo luận. 7 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Ưu Điểm Khi Sử Dụng CSDL • Động cơ chính của việc sử dụng CSDL là tốc độ truy xuất. Một CSDL được thiết kế đúng cách, sự truy xuất các phần thông tin riêng biệt có thể thực hiện ngay tức thời, bất kể số mẫu tin hay kích thước của CSDL. Tốc độ truy xuất có thể biểu diễn là O(k), trong đó k là hằng số có giá trị bé. • Việc sử dụng CSDL làm cho các chương trình truy xuất dữ liệu mà không cần biết nó như thế nào. Nếu một chương trình đọc tập tin thông thường, nó phải biết kiểu dữ liệu, các định dạng và thứ tự các trường (field) của tập tin đó. 8 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Ưu Điểm Khi Sử Dụng CSDL • Tuy nhiên, khi chương trình đọc từ tập tin CSDL, nó thường chỉ cần xác định rõ thông tin gì mà nó muốn. • CSDL cũng cho phép tận dụng hiệu quả không gian lưu trữ, giảm dư thừa dữ liệu đến mức tối tiểu. • Các hệ quản trị CSDL (Database management system - DBMS) cũng tăng tính bảo mật CSDL thông qua một số cách. Cho ví dụ, các tiện ích sao lưu và khôi phục dữ luôn có sẵn trong các DBMS và dữ liệu có thể được sao lưu cả khi nó đang được sử dụng. • Các hệ CSDL cũng hỗ trợ cho khái niệm về 9 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Ưu Điểm Khi Sử Dụng CSDL giao tác (transaction). Một giao tác là một nhóm các thay đổi có quan hệ nhau tác động đến CSDL. Nghĩa là, tất cả thay đổi phải xảy ra hoặc là không xảy ra. • Ví dụ, chúng ta đang chuyển tiền từ tài khoản tiền gởi tiết kiệm (savings account) và gởi tiền này vào tài khoản tiền gởi thanh toán (checking account). • Chúng ta muốn cả hai thao tác rút và gởi thực hiện thành công, nhưng nếu rút tiền thành công và gởi tiền bị lỗi thì sao? Do vậy, chúng ta phải khôi phục lại tiền đã rút từ tài khoản tiền gởi tiết kiệm. 10 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Ưu Điểm Khi Sử Dụng CSDL • Các hệ CSDL cho phép những thay đổi dữ liệu được nhóm vào trong các giao tác để thực hiện thành công trọn vẹn hoặc là không thực hiện điều gì. • Các DBMS cũng tăng tính bảo mật dữ liệu vì nó cho phép nhiều người dùng. Ví dụ như doanh nghiệp Amazon.com cho phép nhiều người dùng từ khắp thế giới truy cập CSDL để xem và đặt hàng cùng lúc. Những thay đổi của người dùng này sẽ không gây trở ngại cho người dùng khác. • DBMS quản lý những khả năng xung đột có thể xảy ra bằng cách khóa dữ liệu tạm thời khi cần thiết. 11 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Ưu Điểm Khi Sử Dụng CSDL • Với tất cả lý do trên, các hệ CSDL được sử dụng phổ biến. Như chúng ta thấy, việc sử dụng các hệ CSDL cũng trở nên thuận tiện hơn khi dùng ngôn ngữ SQL. Do vậy, hầu hết các ứng dụng ngày nay đều sử dụng CSDL. 12 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Mô Hình Hóa Miền Dữ Liệu • Trước khi tạo CSDL quan hệ, người thiết kế phải qua một quá trình gọi là mô hình hóa dữ liệu (data modeling). • Giai đoạn mô hình hóa nhận dạng các “thực thể” (entity), các “thuộc tính” (attribute) của mỗi kiểu thực thể (entity type) và các “mối quan hệ” (relationship) giữa các kiểu thực thể khác nhau. • Cho ví dụ, trong việc xây dựng CSDL cho một trường đại học, các kiểu thực thể gồm các sinh viên, các giảng viên, các ký túc xá, các phòng học, các chuyên ngành, các khóa học, 13 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Mô Hình Hóa Miền Dữ Liệu • Hình sau cho thấy mô hình dữ liệu của các thực thể và các mối quan hệ mà chúng ta đang thảo luận được thể hiện trong lược đồ thực thể - mối quan hệ (entity-relationship: E- R). 14 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Mô Hình Hóa Miền Dữ Liệu 15 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Mô Hình Hóa Miền Dữ Liệu • Các thuộc tính của một sinh viên gồm tên, địa chỉ, ký túc xá đang ở, số phòng, chuyên ngành, cố vấn, • Một mối quan hệ giữa kiểu thực thể giảng viên với sinh viên là mối quan hệ advisor/advisee. • Thực thể là “thứ gì đó” mà CSDL sẽ lưu trữ. Khái niệm kiểu thực thể thường tương ứng với lớp của các đối tượng thế giới thực, chẳng hạn các giảng viên, các xe, các tòa nhà. Đôi lúc kiểu thực thể được hiểu theo nghĩa trừu tượng hơn. Vấn đề chính của mô hình hóa dữ liệu là xác định các kiểu thực thể của mô hình. 16 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Mô Hình Hóa Miền Dữ Liệu • Với các khái niệm quen thuộc trong lập trình hướng đối tượng, một kiểu thực thể tương tự như một lớp. Mỗi thực thể riêng biệt của một kiểu thực thể (một thể hiện của một lớp – đối tượng) sẽ được biểu trưng bởi một tập các giá trị thuộc tính. • Thực thể như là “danh từ”, trong khi thuộc tính như là “tính từ” hay từ ngữ để mô tả của thực thể mà CSDL sẽ lưu trữ. Cho ví dụ, thực thể sinh viên cụ thể có các thuộc tính là “Bill Smith”, “Akron, OH”, “Fisher Dorm”, 323, “Computer Science”, “Professor Findley”, 17 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Mô Hình Hóa Miền Dữ Liệu • Cấu trúc của một CSDL được mô tả bởi “lược đồ” (schema) của nó. Như chúng ta sẽ thấy sau này, để chuyển mô hình dữ liệu thành lược đồ CSDL quan hệ , mỗi thực thể của một kiểu thực thể phải duy nhất. • Tập giá trị các thuộc tính của mỗi thực thể phải khác với tất cả thực thể khác trong cùng kiểu. Ví dụ, chúng ta có thể gán thuộc tính “khóa” cho mỗi thực thể của kiểu thực thể sinh viên để phân biệt các sinh viên với nhau. • Giả sử mối quan hệ giữa kiểu thực thể giảng viên với sinh viên là mối quan hệ advisor/advisee. Điều quan trọng là chúng 18 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Mô Hình Hóa Miền Dữ Liệu ta phải quyết định xem mối quan hệ này là 1:1 (một-một), 1:N (một-nhiều) hay N:M (nhiều- nhiều). Các tỷ số này được gọi là tỷ số lực lượng (cardinality ratio). Chúng ta có thể hiểu “lực lượng” là số lượng thể hiện của một kiểu thực thể. • Trong ví dụ trên, chúng ta có thể chọn mối quan hệ 1:N (một cố vấn cho nhiều sinh viên). Ngược lại, nếu nhà trường yêu cầu nhiều cố vấn cho mỗi sinh viên (ví dụ, một cố vấn học tập và một cố vấn đời sống) thì mối quan hệ sẽ được chọn là N:M (nhiều cố vấn cho mỗi sinh viên và nhiều sinh viên cho mỗi cố vấn). 19 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Mô Hình Hóa Miền Dữ Liệu • Một vấn đề nữa là chúng ta cần xác định số thể hiện tối thiểu của kiểu thực thể. Ví dụ, nếu yêu cầu là mỗi sinh viên phải có cố vấn thì số thể hiện tối thiểu phía giảng viên của mối quan hệ advisor/advisee phải là 1. Ngược lại là 0 (nghĩa là có thực thể sinh viên nhưng không được kết hợp với cố vấn nào). • Tương tự, nếu yêu cầu là mỗi giảng viên đều là cố vấn thì số thể hiện tối thiểu phía sinh viên của mối quan hệ advisor/advisee phải là 1. Ngược lại là 0 (nghĩa là có thực thể giảng viên nhưng không cố vấn cho sinh viên nào). 20 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Xây Dựng CSDL Quan Hệ Từ Mô Hình Dữ Liệu • Mô hình dữ liệu gồm có lược đồ khái niệm (conceptual schema) hoặc sự mô tả cấu trúc của CSDL. • Sau khi lược đồ khái niệm được tạo, công viêc kế đến là chuyển đổi mô hình dữ liệu thành các bảng, các mối quan hệ và các qui tắc toàn vẹn dữ liệu (data integrity). • Một kiểu thực thể là một bảng, mỗi hàng trong bảng là một thể hiện của kiểu thực thể. Trong thuật ngữ CSDL quan hệ, một bảng được gọi là một “quan hệ” (relation). Lưu ý là quan hệ khác với “mối quan hệ” (relationship). 21 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Xây Dựng CSDL Quan Hệ Từ Mô Hình Dữ Liệu • Một quan hệ gồm các hàng, mỗi hàng là một thể hiện của kiểu thực thể và mỗi cột là một thuộc tính của kiểu thực thể. • Mỗi hàng của quan hệ được gọi là một bộ (tuple). Người ta thường dùng từ “hàng” nhiều hơn từ “bộ”. Bộ là một hàng của bảng, một thể hiện của quan hệ, một thể hiện của kiểu thực thể. Mỗi bộ gồm giá trị các thuộc tính của thể hiện của kiểu thực thể. Thuộc tính cũng còn được gọi là trường (field). • Tóm lại, các từ đồng nghĩa: quan hệ/bảng, bộ/hàng, thuộc tính/trường/cột . 22 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Xây Dựng CSDL Quan Hệ Từ Mô Hình Dữ Liệu • Bước đầu tiên là tạo một quan hệ cho mỗi thực thể trong mô hình dữ liệu. Mỗi thuộc tính của kiểu thực thể trong mô hình trở thành tên cột trong quan hệ. Khi này, chúng ta phải chọn một thuộc tính hay một tập thuộc tính được gọi là khóa chính (primary key), dùng để nhận dạng duy nhất mỗi hàng của quan hệ. • Một khóa chính lý tưởng thì ngắn, dạng số và không bao giờ thay đổi. Để đạt được điều lý tưởng thì không phải lúc nào cũng có được, nhưng nó giúp chúng ta khi chọn khóa. 23 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Xây Dựng CSDL Quan Hệ Từ Mô Hình Dữ Liệu • Cho ví dụ, nếu bảng “Student” gồm các thuộc tính name, address, social security number (SSN) và một số thuộc tính khác, chúng ta có thể chọn hai thuộc tính name– address hoặc một thuộc tính SSN để làm khóa. Chọn SSN thì tốt hơn, bởi vì SSN làm cho hiệu quả hơn khi xử lý, do nó là kiểu số và ít thay đổi hơn là tên hay địa chỉ. • Đôi khi không có thuộc tính rõ ràng để chọn làm khóa tốt trong các thuộc tính của bảng. Thay vì chọn nhiều trường làm khóa, cách tốt hơn là chúng ta sử dụng khóa đại diện (surrogate key). 24 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Xây Dựng CSDL Quan Hệ Từ Mô Hình Dữ Liệu • Khóa đại diện chỉ đơn giản là một số, được sinh ra bởi hệ quản trị CSDL và gán cho mỗi bộ. Trong ví dụ trên, nếu thuộc tính SSN không tồn tại trong bảng “Student”, chúng ta sẽ tạo ra khóa đại diện cho bảng Student và gọi nó là “StudentID”. • Khi các quan hệ được tạo cho tất cả thực thể trong mô hình dữ liệu, tiếp theo là tạo các mối quan hệ cho mô hình. • Với mối quan hệ 1:1, chọn một quan hệ là “cha” và quan hệ còn lại là “con”, tạo cột khóa ngoại trong quan hệ con mà nó dùng để kết hợp mỗi bộ trong quan hệ con với một bộ 25 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Xây Dựng CSDL Quan Hệ Từ Mô Hình Dữ Liệu tương ứng trong quan hệ cha. • Nếu số thể hiện tối thiểu trên cả hai phía của mối quan hệ 1:1 là 1 thì việc chọn quan hệ nào làm cha sẽ không có vấn đề gì. Tuy nhiên, nếu số thể hiện của một phía là 0, thì chọn quan hệ còn lại làm quan hệ cha. • Với mối quan hệ 1:N, quan hệ trên phía 1 sẽ là “cha” và quan hệ trên phía N sẽ là “con”. Chúng ta tạo cột khóa ngoại trong quan hệ con để “nhiều con” sẽ được kết hợp với “một cha”. Cho ví dụ, với mối quan hệ advisor/ advisee, chỉ đơn giản là chúng ta thêm cột 26 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Xây Dựng CSDL Quan Hệ Từ Mô Hình Dữ Liệu khóa ngoại vào quan hệ Student, tên của cột khóa ngoại là “AdvisorID” và kết hợp với cột khóa chính trong quan hệ Professor. • Với mối quan hệ N:M thì phức tạp hơn. Chúng ta phải tạo một bảng mới, một quan hệ mới. Quan hệ như thế đôi khi được gọi là “bảng giao” (intersection table) hay “quan hệ mối quan hệ” (relationship relation). • Bảng giao gồm các cột khóa ngoại là các khóa chính của cả hai thực thể trong mối quan hệ. Khóa chính của bảng giao thường được ghép từ hai khóa ngoại đó. 27 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Xây Dựng CSDL Quan Hệ Từ Mô Hình Dữ Liệu • Cho ví dụ, để tạo mối quan hệ M:N giữa các bảng Student và Course, chúng ta sẽ tạo quan hệ “StudentCourseIntersection”. StudentCourseIntersection sẽ có các cột khóa ngoại cho Student (ví dụ StudentID) và cho Course (ví dụ CourseID). Mỗi hàng trong StudentCourseIntersection sẽ chứa thông tin về một sinh viên học ở khóa học cụ thể. Bất kỳ sinh viên nào cũng có thể học ở nhiều khóa và nhiều sinh viên có thể học chung một khóa. 28 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Chuẩn Hóa Dữ Liệu • Một số mô hình dữ liệu thì tốt hơn một số khác. Khi thiết kế CSDL không đúng, sẽ làm tăng khả năng dư thừa dữ liệu (data redundancy) dẫn đến những dị thường (anomaly) trong CSDL. Chẳng hạn, khi xóa thông tin của kiểu thực thể này thì lại mất thêm thông tin của kiểu thực thể khác. • Sự chuẩn hóa (normalization) là quá trình kiểm tra các quan hệ. Sau khi chuẩn hóa, các quan hệ có cấu trúc tốt hơn. • Mục tiêu của chuẩn hóa là đảm bảo rằng mỗi quan hệ chỉ thể hiện cho một chủ đề (theme). Cho ví dụ, quan hệ chứa thông tin về các sinh 29 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Chuẩn Hóa Dữ Liệu viên, quan hệ chứa thông tin về các ký túc xá, nhưng không có quan hệ chứa thông tin cho cả hai. • Có nhiều dạng chuẩn hóa. Dạng chuẩn (normal form) ở mức cao hơn sẽ giảm dư thừa dữ liệu và tránh được những dị thường. Bất kỳ dạng chuẩn nào ở mức cao hơn cũng thích hợp với các dạng thấp hơn. Do vậy, một quan hệ ở dạng chuẩn 3 (3NF) thì cũng ở dạng chuẩn 2 (2NF) và dạng chuẩn 1 (1NF). • Các dạng chuẩn dựa vào khái niệm phụ thuộc hàm (functional dependency). Phụ thuộc hàm nghĩa là giá trị của một thuộc tính hoặc tập 30 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Chuẩn Hóa Dữ Liệu các thuộc tính xác định giá trị của thuộc tính khác. • Giả sử chúng ta đã tạo quan hệ với các thuộc tính sau. Cũng giả sử rằng không có sinh viên cùng tên ở trong cùng ký túc xá và không có giảng viên cùng tên trong trường: • Khóa của quan hệ Student gồm hai thuộc tính Sname và DormID. Theo định nghĩa, thuộc 31 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Chuẩn Hóa Dữ Liệu tính khóa xác định duy nhất một bộ trong quan hệ. Với giá trị cụ thể của Sname và DormID, giá trị của tất cả thuộc tính khác được xác định. • Tuy nhiên, không phải tất cả các phụ thuộc hàm đều là khóa. Trong quan hệ Student, có một phụ thuộc hàm giữa thuộc tính MajorAdvisorName và AdvisorDept. Ví dụ, với tên của cố vấn cụ thể thì tên khoa của cố vấn đó sẽ được xác định. • Dạng chuẩn đầu tiên (1NF) được định nghĩa đơn giản. Mỗi thuộc tính trong quan hệ phải là thuộc tính nguyên tử (atomic attribute), thuộc tính đơn trị (single-valued attribute). 32 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Chuẩn Hóa Dữ Liệu • Cho ví dụ, nếu thuộc tính trong quan hệ Student là TelephoneNumber, thì một bộ bất kỳ trong quan hệ chỉ có một giá trị cho TelephoneNumber. Nếu chúng muốn một sinh viên có thể có nhiều số điện thoại, thì chúng ta phải tạo một quan hệ riêng cho vấn đề này. Mỗi bộ trong quan hệ PhoneNumber mới chỉ có một số điện thoại và nhiều bộ trong quan hệ này được kết hợp thông qua mối quan hệ 1:N với một sinh viên cụ thể. • Dạng chuẩn thứ 2 (2NF) yêu cầu quan hệ là dạng chuẩn 1 và mỗi thuộc tính không khóa phụ thuộc hàm đầy đủ vào khóa chính (không 33 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Chuẩn Hóa Dữ Liệu phụ thuộc hàm vào bất kỳ tập con nào của khóa - còn gọi là phụ thuộc hàm bộ phận). • Nếu quan hệ có khoá chính chỉ gồm một thuộc tính hoặc quan hệ có khóa đại diện (surrogate key) thì luôn ở dạng chuẩn 2. • Câu hỏi đặt ra là có phải mọi thuộc tính không khoá trong mô hình quan hệ ở trên phụ thuộc hàm đầy đủ vào khoá của nó không. Nghĩa là các quan hệ có ở dạng chuẩn 2 không? • Trong trường hợp này, câu trả lời là “Không”. Giả sử là có một RA cho mỗi ký túc xá Dorm, thì giá trị RA phụ thuộc vào DormID chứ không phụ thuộc vào Sname. Để đưa quan hệ 34 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Chuẩn Hóa Dữ Liệu Student và Dorm về dạng chuẩn 2, chúng ta phải tạo một quan hệ mới và bỏ thuộc tính RA khỏi quan hệ Dorm : • Dạng chuẩn 3 (3NF) yêu cầu quan hệ ở dạng chuẩn 2 và không có thuộc tính không khoá nào phụ thuộc bắc cầu (transitive dependency) vào khóa chính (hoặc phụ thuộc hàm giữa các thuộc tính không khoá). • Trong ví dụ trên, quan hệ vừa tạo không phải dạng chuẩn 3 vì thuộc tính MajorAdvisor- 35 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Chuẩn Hóa Dữ Liệu Name và AdvisorDept đều phụ thuộc vào khóa chính, nhưng thuộc tính AdvisorDept cũng phụ thuộc bắc cầu vào MajorAdvisor- Name. • Nghĩa là, với một sinh viên cụ thể, chúng ta có thể xác định được tên cố vấn (MajorAdvisorName) của sinh viên đó và khi biết được tên cố vấn, chúng ta có thể xác định được khoa (AdvisorDept) của cố vấn đó. Đây là phụ thuộc bắc cầu. • Để đưa quan hệ mới tạo trở thành dạng chuẩn 3NF, chúng ta phải bỏ phụ thuộc bắc cầu trong quan hệ: 36 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Chuẩn Hóa Dữ Liệu • Bây giờ các quan hệ ban đầu được chia thành 3 quan hệ: quan hệ về sinh viên, ký túc xá và các giảng viên làm cố vấn. • Trong thực tế, chúng ta nên chọn giá trị khoá tốt hơn cho quan hệ sinh viên và giảng viên. 37 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Chuẩn Hóa Dữ Liệu Chẳng hạn, thuộc tính khoá là ID có kiểu dữ liệu dạng số nguyên thay vì là kiểu chuỗi. Ngoài ra, trong quan hệ giảng viên nên thêm các thuộc tính như địa chỉ, lương, 38 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ SQL • Công ty IBM đầu tiên đưa ra ngôn ngữ SQL (structured query language - ngôn ngữ truy vấn có cấu trúc) để xử lý CSDL. Nó là ngôn ngữ cấp cao để tạo CSDL, thao tác dữ liệu và truy lục/lấy các tập dữ liệu. • SQL là ngôn ngữ phi thủ tục (nonprocedural language), nghĩa là các câu lệnh SQL mô tả dữ liệu và các thao tác cần phải “làm gì” nhưng nó không chỉ rõ từng bước tiến hành là làm “thế nào” để hệ CSDL thực hiện. • Các chuẩn ANSI (American National Standards Institute - Viện Tiêu chuẩn Quốc gia Hoa Kỳ) cho SQL được công bố vào năm 39 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ SQL 1986, 1989, 1992, 1999 và 2003. • Trong thực tế, các nhà cung cấp khác nhau đưa ra một số thay đổi nhỏ về cú pháp và ngữ nghĩa với mỗi ngôn ngữ SQL của họ. Tuy nhiên, phần lớn các lệnh SQL đều tương thích với SQL chuẩn. • Một số hệ quản trị CSDL phổ biến được nhiều người biết đến là DB2 (IBM), MySQL (nguồn mở), Oracle và SQL Server (Microsoft). • Các câu lệnh SQL thường được phân biệt thành hai phần là ngôn ngữ định nghĩa dữ liệu (data definition language - DDL) và ngôn 40 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ SQL ngữ thao tác dữ liệu (data manipulation language - DML). • Các lệnh của DDL tạo các cấu trúc CSDL như bảng (table), khung nhìn (view), thủ tục kích khởi (trigger) và thủ tục lưu (stored procedure). • Các lệnh của DML như chèn, cập nhật, chọn hay xóa dữ liệu trong CSDL. • SQL không phân biệt dạng chữ. Các lệnh và tên có thể nhập ở dạng chữ hoa hay thường. Tuy nhiên, một số người thích sử dụng chữ hoa và chữ thường để phân biệt từ khóa với tên. 41 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Định Nghĩa Dữ Liệu • Câu lệnh đầu tiên của ngôn ngữ định nghĩa dữ liệu (DDL) để học là CREATE. Lệnh CREATE TABLE dùng để tạo một quan hệ. Trong SQL, quan hệ được gọi là bảng, bộ được gọi là hàng và thuộc tính được gọi là cột. • Sau đây là cú pháp của lệnh CREATE TABLE: CREATE TABLE ( [, ] [CONSTRAINT [,CONSTRAINT ]] ); • Sự đặc tả cú pháp này nói rằng câu lệnh phải 42 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Định Nghĩa Dữ Liệu bắt đầu bằng từ khóa CREATE TABLE, sau đó là tên bảng và dấu ngoặc mở. Kế tiếp là một hay nhiều đặc tả cho tên cột, kiểu dữ liệu mỗi cột và các thuộc tính mỗi cột (ví dụ, cho phép null hay không). Sau danh sách các tên cột là phần tùy chọn các ràng buộc bắt đầu bằng từ khóa CONSTRAINT, đến tên ràng buộc và kiểu ràng buộc (ví dụ, PRIMARY KEY hay UNIQUE). Cuối cùng là dấu ngoặc đóng và dấu chấm phẩy. • Người thiết kế CSDL tự do chỉ định tên bảng, tên cột hay tên ràng buộc. SQL chuẩn có các qui tắc đặt tên, nhưng mỗi nhà cung cấp hệ 43 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Định Nghĩa Dữ Liệu quản trị CSDL có các qui tắc riêng của họ và có một ít thay đổi so với SQL chuẩn. • Cho ví dụ, SQL2003 chuẩn cho phép tên có thể dài đến 128 ký tự, nhưng MySQL thì chỉ giới hạn 64 ký tự và Oracle thì chỉ 30 ký tự. • Các kiểu dữ liệu của SQL cũng có thay đổi. Nói chung, các kiểu có thể sử dụng là: - Integer. - Number/Numeric (số dấu chấm động). - Varchar (chuỗi ký tự có chiều dài thay đổi). - Date/DateTime. - Char (chuỗi ký tự có chiều dài cố định). 44 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Định Nghĩa Dữ Liệu • Chúng ta phải tham khảo tài liệu của hệ quản trị CSDL đang sử dụng để chọn kiểu dữ liệu thích hợp. • Các thuộc tính phổ biến nhất mà chúng ta chỉ định cho các cột là NULL, NOT NULL và DEFAULT. • Thuộc tính NOT NULL không cho phép giá trị rỗng trên cột tương ứng của hàng được thêm vào. Theo mặc định thì cột chứa giá trị null. • Thuộc tính DEFAULT cho phép chúng ta sử dụng một biểu thức để tạo giá trị mặc định cho cột nếu không có giá trị nào của cột đó được cung cấp khi chèn một hàng mới. 45 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Định Nghĩa Dữ Liệu • Cho ví dụ, sự khai báo sau đây chỉ định giá trị mặc định cho cột State là “NY”: State Char(2) DEFAULT 'NY', • Có 4 ràng buộc