Bài giảng Tin học đại cương

2010 TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG [BÀI GIẢNG TIN HỌC ĐẠI CƢƠNG - IT1110] [Type the abstract of the document here. The abstract is typically a short summary of the contents of the document. Type the abstract of the document here. The abstract is typically a short summary of the contents of the document.] 2 THÔNG TIN MÔN HỌC Trình độ: Sinh viên đại học các ngành Khối lƣợng: 4(3-1-1-8)  Lý thuyết: 45 tiết  Bài tập/BTL: 15 tiết (bài tập, thảo luận)  Thí nghiệm: 5 bài (x 3 tiết) (thực hành) Mô tả vắn tắt nội dung: Khái niệm thông tin, biểu diễn thông tin trong máy tính. Hệ thống máy tính: phần cứng, phần mềm, hệ điều hành, mạng máy tính. Giải quyết bài toán bằng máy tính. Các cấu trúc lập trình cơ bản.. 3 MỤC LỤC PHẦN 1. TIN HỌC CĂN BẢN .............................................................................. 8 I.1. Thông tin và biểu diễn thông tin (5T lý thuyết) ............................................. 8 I.1.1. Các khái niệm cơ bản về thông tin và tin học (1T lý thuyết) ............................................ 8 I.1.1.1. Thông tin và xử lý thông tin ....................................................................................... 8 a. Thông tin - Dữ liệu – Tri thức....................................................................................... 8 b. Qui trình xử lý thông tin ............................................................................................... 9 I.1.1.2. Máy tính điện tử và phân loại .................................................................................... 9 a. Lịch sử phát triển của máy tính điện tử ........................................................................ 9 b. Phân loại máy tính điện tử .......................................................................................... 10 I.1.1.3. Tin học và các ngành công nghệ liên quan .............................................................. 10 a. Tin học ........................................................................................................................ 10 b. Công nghệ thông tin (Information Technology - IT) .................................................. 11 c. Công nghệ thông tin và truyền thông .......................................................................... 11 I.1.2. Biểu diễn dữ liệu trong máy tính (4T lý thuyết) ............................................................. 11 I.1.2.1. Biểu diễn số trong các hệ đếm ................................................................................. 11 a. Hệ đếm cơ số b ............................................................................................................ 11 b. Hệ đếm thập phân (Decimal system, b=10)................................................................ 12 c. Hệ đếm nhị phân (Binary system, b=2) ...................................................................... 13 d. Hệ đếm bát phân (Octal system, b=8) ........................................................................ 13 e. Hệ đếm thập lục phân (Hexa-decimal system, b=16) ................................................. 13 f. Chuyển đổi một số từ hệ thập phân sang hệ đếm cơ số b ........................................... 14 I.1.2.2. Biểu diễn dữ liệu trong máy tính và đơn vị thông tin .............................................. 14 a. Nguyên tắc chung ....................................................................................................... 14 b. Đơn vị thông tin .......................................................................................................... 15 I.1.2.3. Biểu diễn số nguyên ................................................................................................. 16 a. Số nguyên không dấu .................................................................................................. 16 b. Số nguyên có dấu ........................................................................................................ 16 c. Tính toán số học với số nguyên ........................................................................................ 17 Cộng/ trừ số nguyên ........................................................................................................ 17 Nhân/ chia số nguyên ...................................................................................................... 17 I.1.2.4. Biểu diễn số thực...................................................................................................... 18 a. Nguyễn tắc chung ....................................................................................................... 18 b. Chuẩn IEEE754/85 ..................................................................................................... 19 I.1.2.5. Biểu diễn ký tự ......................................................................................................... 20 a. Nguyên tắc chung ....................................................................................................... 20 b. Bộ mã ASCII .............................................................................................................. 20 c. Bộ mã Unicode ........................................................................................................... 22 I.2. HỆ THỐNG MÁY TÍNH (7 tiết) ................................................................. 23 I.2.1. Hệ thống máy tính (3T lý thuyết)................................................................................ 23 4 a. Mô hình cơ bản của máy tính ...................................................................................... 23 b. Bộ xử lý trung tâm – CPU .......................................................................................... 25 c. Bộ nhớ ......................................................................................................................... 26 d. Hệ thống vào-ra .......................................................................................................... 27 e. Liên kết hệ thống (buses) ............................................................................................ 29 I.2.1.2. Phần mềm máy tính ................................................................................................. 30 a. Dữ liệu và giải thuật .................................................................................................... 30 b. Chương trình và ngôn ngữ lập trình ........................................................................... 35 c. Phân loại phần mềm máy tính ..................................................................................... 37 I.2.2. Mạng máy tính (2T lý thuyết) ..................................................................................... 37 I.2.2.1. Lịch sử phát triển của mạng máy tính ...................................................................... 37 I.2.2.2. Phân loại mạng máy tính .......................................................................................... 38 I.2.2.3. Các thành phần cơ bản của một mạng máy tính ...................................................... 38 I.2.2.4. Mạng Internet ........................................................................................................... 40 I.2.3. Giới thiệu hệ điều hành (2T lý thuyết) ........................................................................ 41 I.2.3.1. Các khái niệm cơ bản ............................................................................................... 41 a. Khái niệm hệ điều hành .............................................................................................. 41 b. Tệp (File) .................................................................................................................... 41 c. Quản lý tệp của hệ điều hành ...................................................................................... 42 I.2.3.2. Hệ lệnh của hệ điều hành ......................................................................................... 43 I.2.3.3. Hệ điều hành Windows ............................................................................................ 44 a. Sự ra đời và phát triển ................................................................................................. 44 b. Khởi động và thoát khỏi Windows XP ....................................................................... 44 c. Một số thuật ngữ và thao tác thường sử dụng ............................................................. 45 d. Cấu hình Windows (Control Panel) ............................................................................ 47 e. Windows Explorer ...................................................................................................... 52 I.3. Các hệ thống ứng dụng (4T lý thuyết) .......................................................... 56 I.3.1. Các hệ thống quản lý thông tin........................................................................................ 56 I.3.1.1. Các khái niệm về thông tin và Hệ thống quản lý thông tin .......................................... 56 I.3.1.2. Phân loại ................................................................................................................... 56 a. Phân loại theo cấp bậc quản lý .................................................................................... 56 b. Phân loại theo chức năng nghiệp vụ ........................................................................... 59 c. Phân loại theo quy mô tích hợp .................................................................................. 60 I.3.2. Hệ thông tin bảng tính ..................................................................................................... 62 I.3.3. Hệ quản trị cơ sở dữ liệu ................................................................................................. 67 I.3.3.1. Cơ sở dữ liệu ............................................................................................................ 67 a. Khái niệm về Cơ Sở Dữ Liệu...................................................................................... 67 b. Hệ quản trị cơ sở dữ liệu ............................................................................................. 72 I.3.4. Các hệ thống thông minh ................................................................................................ 76 PHẦN II. GIẢI QUYẾT BÀI TOÁN .................................................................. 77 5 II.1. Thuật toán(4 tiết LT) .................................................................................... 77 II.1.1. Định nghĩa thuật toán ..................................................................................................... 77 II.1.2. Biểu diễn thuật toán ....................................................................................................... 78 II.1.2.1. Ngôn ngữ lưu đồ ..................................................................................................... 79 II.1.2.2. Mã giả ..................................................................................................................... 83 II.1.3. Thuật toán đệ qui ........................................................................................................... 84 II.1.4. Một số thuật toán thông dụng ........................................................................................ 85 II.1.4.1. Thuật toán số học .................................................................................................... 85 II.1.4.2. Thuật toán về dãy ................................................................................................... 86 II.1.5. Thuật giải heuristic ........................................................................................................ 87 II.1.5.1. Thuật giải – Sự mở rộng khái niệm của thuật toán ................................................. 87 II.1.5.2. Thuật giải heuristic ................................................................................................. 87 II.2. Giải quyết bài toán (4 tiết LT, 2 tiết BT) .................................................... 88 II.2.1. Khái niệm về bài toán .................................................................................................... 88 II.2.2. Các bước giải quyết bài toán bằng máy tính .................................................................. 89 Bài tập về Thuật toán (2 tiết BT) ......................................................................... 90 II.2.3. Các phương pháp giải quyết bài toán bằng máy tính ..................................................... 90 II.2.3.1. Giải quyết bài toán theo hướng xác định trực tiếp lời giải: .................................... 90 II.2.3.2. Giải quyết bài toán theo hướng tìm kiếm lời giải ................................................... 91 II.2.4. Phân loại bài toán ........................................................................................................... 91 II.2.4.1. Độ phức tạp thuật toán ............................................................................................ 91 II.2.4.2. Phân loại bài toán ................................................................................................... 93 PHẦN 3. LẬP TRÌNH .......................................................................................... 95 III.1. Tổng quan về ngôn ngữ C (3 tiết LT) ........................................................ 95 III.1.1. Lịch sử phát triển .......................................................................................................... 95 III.1.2. Các phần tử cơ bản của ngôn ngữ C ............................................................................. 96 1.2.1. Tập kí tự ................................................................................................................ 96 1.2.2. Từ khóa ................................................................................................................. 96 1.2.3. Định danh .............................................................................................................. 97 1.2.4. Các kiểu dữ liệu .................................................................................................... 98 1.2.5. Hằng ...................................................................................................................... 99 1.2.6. Biến ..................................................................................................................... 100 1.2.7. Hàm ..................................................................................................................... 100 1.2.8. Biểu thức ............................................................................................................. 101 1.2.9. Câu lệnh .............................................................................................................. 101 1.2.10. Chú thích ........................................................................................................... 102 III.1.3. Cấu trúc cơ bản của một chương trình C .................................................................... 102 6 III.1.4. Biên dịch chương trình C ........................................................................................... 105 III.1.5. Trình biên dịch Turbo C++......................................................................................... 105 III.1.6. Cài đặt và sử dụng Turbo C++ 3.0 ............................................................................. 105 III.2. Kiểu dữ liệu và biểu thức trong C (4 tiết LT) ......................................... 106 III.2.1. Các kiểu dữ liệu chuẩn trong C (1 tiết LT) ................................................................. 107 III.2.2. Các biểu thức .............................................................................................................. 109 III.2.3. Các phép toán ............................................................................................................. 110 III.2.3.1. Phép toán số học .................................................................................................. 110 III.2.3.2. Phép toán quan hệ ............................................................................................... 111 III.2.3.3. Các phép toán logic ............................................................................................. 112 III.2.3.4. Phép toán gán ...................................................................................................... 112 III.2.4. Thứ tự ưu tiên các phép toán ...................................................................................... 114 III.2.5. Một số toán tử đặc trưng trong C .............................................................................. 115 III.3. Cấu trúc lập trình trong C (6 tiết LT) ..................................................... 118 III.3.1. Vào/ra ......................................................................................................................... 118 III.3.1.1. Các lệnh vào ra dữ liệu với các biến (printf, scanf) ............................................ 118 III.3.1.2. Các lệnh nhập xuất khác ...................................................................................... 123 III.3.2. Cấu trúc lệnh khối ...................................................................................................... 124 III.3.3. Cấu trúc if ................................................................................................................... 126 III.3.4. Cấu trúc lựa chọn switch ............................................................................................ 127 III.3.5. Vòng lặp for ................................................................................................................ 130 III.3.6. Vòng lặp while và do – while ..................................................................................... 132 III.3.7. Các lệnh thay đổi cấu trúc lập trình ............................................................................ 135 III.3.7.1. continue .......................................................................................................... 136 III.3.7.2. break .............................................................................................................. 137 III.4. Mảng và xâu ký tự (5 tiết LT) .................................................................. 138 III.4.1. Mảng ........................................................................................................................... 138 III.4.1.1. Khái niệm mảng .................................................................................................. 138 III.4.1.2. Khai báo và sử dụng mảng .................................................................................. 138 III.4.1.3. Các thao tác cơ bản trên mảng ............................................................................ 139 a. Nhập dữ liệu cho mảng........................................................................................ 139 b. Xuất dữ liệu chứa trong mảng ............................................................................. 140 c. Tìm phần tử có giá trị lớn nhất, phần tử có giá trị nhỏ nhất ................................ 142 III.4.1.4. Tìm kiếm trên mảng ............................................................................................ 142 III.4.1.5. Sắp xếp mảng ...................................................................................................... 144 III.4.2. Xâu ký tự (2 tiết LT) ................................................................................................... 146 III.4.2.1. Khái niệm xâu ký tự ............................................................................................ 146 7 III.4.2.2. Khai báo và sử dụng xâu ..................................................................................... 147 a. Khai báo xâu kí tự ..................................................................................................... 147 b. Truy nhập vào một phần tử của xâu ......................................................................... 147 III.4.2.3. Các hàm xử lý ký tự ............................................................................................ 147 III.4.2.4. Các hàm xử lý xâu ............................................................................................... 149 a. Vào ra dữ liệu ...................................................................................................... 149 b. Một số hàm xử lí xâu kí tự khác .......................................................................... 149 III.5. Cấu trúc (2 tiết LT) ................................................................................... 151 III.5.1. Khái niệm cấu trúc ...................................................................................................... 151 III.5.2. Khai báo và sử dụng cấu trúc ..................................................................................... 152 III.5.2.1. Khai báo kiểu dữ liệu cấu trúc ............................................................................. 152 III.5.2.2. Khai báo biến cấu trúc: ........................................................................................ 152 III.5.2.3. Định nghĩa kiểu dữ liệu cấu trúc với typedef ...................................................... 153 III.5.3. Xử lý dữ liệu cấu trúc ................................................................................................. 154 III.5.3.1. Truy nhập các trường dữ liệu của cấu trúc .......................................................... 154 III.5.3.2. Phép gán giữa các biến cấu trúc .......................................................................... 156 III.6. Hàm (2 tiết LT) .......................................................................................... 157 III.6.1. Khái niệm hàm............................................................................................................ 157 III.6.1.1. Khái niệm chương trình con ................................................................................ 157 III.6.1.2. Phân loại chương trình con: ................................................................................ 158 III.6.2. Khai báo và sử dụng hàm ........................................................................................... 158 III.6.2.1. Khai báo hàm ...................................................................................................... 158 III.6.2.2. Sử dụng hàm ........................................................................................................ 161 III.6.3. Phạm vi của biến......................................................................................................... 163 8 BUỔI 1. PHẦN 1. TIN HỌC CĂN BẢN (16 tiết Lý thuyết, 4 tiết Bài tập, 6 tiết Thực hành) I.1. Thông tin và biểu diễn thông tin (5T lý thuyết) I.1.1. Các khái niệm cơ bản về thông tin và tin học (1T lý thuyết) I.1.1.1. Thông tin và xử lý thông tin a. Thông tin - Dữ liệu – Tri thức Thông tin- Information Khái niệm thông tin (information) được sử dụng thường ngày.Thông tin mang lại cho con người sự hiểu biết, nhận thức tốt hơn về những đối tượng trong đời sống xã hội, trong thiên nhiên,... giúp cho họ thực hiện hợp lý công việc cần làm để đạt tới mục đích một cách tốt nhất. Người ta quan niệm rằng, thông tin là kết quả xử lý, điều khiển và tổ chức dữ liệu theo cách mà nó sẽ bổ sung thêm tri thức cho người nhận. Nói một cách khác, thông tin là ngữ cảnh trong đó dữ liệu được xem xét Dữ liệu - Data Dữ liệu (data) là biểu diễn của thông tin được thể hiện bằng các tín hiệu vật lý. Thông tin chứa đựng ý nghĩa còn dữ liệu là các sự kiện không có cấu trúc và không có ý nghĩa nếu chúng không được tổ chức và xử lý. Dữ liệu trong thực tế có thể là:  Các số liệu thường được mô tả bằng số như trong các bảng biểu  Các ký hiệu qui ước, ví dụ chữ viết  Các tín hiệu vật lý ví dụ như ánh sáng, âm thanh, nhiệt độ, áp suất,… Theo quan niệm chung của những người làm công nghệ thông tin thì thông tin là những hiểu biết của chúng ta về một lĩnh vực nào đấy, còn dữ liệu là thông tin được biểu diễn và xử lý trong máy tính. Tri thức – Knowledge Tri thức theo nghĩa thường là thông tin ở mức trừu tượng hơn. Tri thức khá đa dạng, nó có thể là sự kiện, là thông tin và cách mà một người thu thập được qua kinh nghiệm hoặc qua đào tạo. Nó có thể là sự hiểu biết chung hay về một lĩnh vực cụ thể nào đó. Thuật ngữ tri thứ