Bài giảng Các vấn đề cơ sở của khoa học máy tính - Chương 1 Giới thiệu về 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