Nhập môn điện toán - Chương 1: Khái niệm cơ bản

Giảng viên : Phạm Tường Hải, Nguyễn Xuân Minh, Phạm Hoàng Anh, Lê Ngọc Minh, . . . Đối tượng : Sinh viên năm thứ nhất Đại học Bách khoa tpHCM.Chương trình : C1. Khái niệm cơ bản. C2. Phần cứng máy tính. C3. Hệ điều hành và mạng máy tính. C4. Cơ sở dữ liệu. C5. Ngôn ngữ lập trình. C6. Phần mềm ứng dụng. C7. Vấn đề ứng dụng trong xã hội.Tài liệu tham khảo : [1] Computing, 3rd ed., Geoffrey Knott & Nick Waites, 2000.[2] Slide bài giảng.Giới thiệu môn học : Nhập môn điện toán Chương 1Khái niệm cơ bảnChương 1Nhập môn Công nghệ thông tin Tờ *1. Vài dòng lịch sử . . .Máy tính xuất hiện từ rất lâu theo nhu cầu buôn bán và trao đổi tiền tệ.Bàn tính tay abacus là dạng sơ khai của máy tính.5 đơn vị1 đơn vịChương 1Nhập môn Công nghệ thông tin Tờ *Các thế hệ máy tính sốĐènđiện tử(1945 - 1955)ENIAC (1946)18.000 bóng đèn1500 rờ le30 tấn140 KWVon Neumann (1945)Bộ nhớ dây trễ, tĩnh điện. Giấy, phiếu đục lổ. Băng từTransistors(1955 - 1965)PDP-1 (1961)Bộ nhớ xuyến từ. Băng từ, trống từ, đĩa từ.IC(1965 - 1980)IBM 360 (1965)Intel 8080 (1974)được xem như CPU đầu tiên được tích hợp trên 1 chip?(1980 - ????)80x86 (1978)Cơ(1642 - 1945)Blaise Pascal (Pháp-1642)Herman Hollerith lập IBM (International Business Machine) ở Mỹ - 1890Charles Babbage (Anh-1830)Chương 1Nhập môn Công nghệ thông tin Tờ *2. Hệ thống số đếmTrước khi có máy tính, con người dùng hệ số đếm thập phân (10).0 1 2 3 45 6 7 8 9Ký số0  1  2  . . .  9  10  11  12  . . .  19 20  21  22  . . .  29  . . .  90  91  92  . . .  99 100  101  . . .  109  . . .  990  991  . . .  999 1000  1001  1002  . . .  1009   . . .Quy tắc đếmThập phân (decimal)Chương 1Nhập môn Công nghệ thông tin Tờ *Hệ thống số đếm (tt.1)Sau khi máy tính số ra đời, các hệ số mới hình thành.0 1Ký số0  1 10  11 100  101  110  111 1000  1001  . . .  1110  1111 10000  10001   . . .Quy tắc đếmHệ nhị phân (Binary)Chương 1Nhập môn Công nghệ thông tin Tờ *Hệ thống số đếm (tt.2)Số ở hệ nhị phân dài, khó nhớ chỉ dùng cho máy.Con người dùng số hệ bát phân (8) và thập lục phân (16) thay cho hệ nhị phân.0 1 2 3 4 5 6 7Ký số0  1  2  . . .  7 10  11  12  . . .  17  20  21  22  . . .  77 100  101  102  . . .  107  . . .  777 1000  1001  1002  . . .  1007  . . .Quy tắc đếmHệ bát phân (Octal)Chương 1Nhập môn Công nghệ thông tin Tờ *Hệ thống số đếm (tt.3)Một ký số hệ 8 bằng 3 ký số hệ 2.Một ký số hệ 16 bằng 4 ký số hệ 2.0 1 2 3 4 5 6 78 9 A B C D E FKý số0  1  2  . . .  9  A  B  . . .  F 10  11  12  . . .  19  1A  . . .  1F  20  . . .  9F A0  A1  A2  . . .  AF  . . .  F0  F1  F2  . . .  FF 100  101  102  . . .  10F  . . .  FFF 1000  1001  1002  . . .  100F  . . .Quy tắc đếmHệ thập lục phân (hexadecimal)Chương 1Nhập môn Công nghệ thông tin Tờ *Công thức tính trị sốNếu B là cơ số, vi là ký số ở hàng i (0 là hàng đơn vị, 1 là hàng "chục", 2 là hàng "trăm", ...) thì giá trị Q của số tính trong hệ 10 theo công thức sau :Chấm B phânvnvn-1...v0.v-1...v-mQ = vn  Bn + vn-1  Bn-1 + . . . + v0  B0 + v-1  B-1 + . . . + v-m  B-må´ni = -mBviihayChương 1Nhập môn Công nghệ thông tin Tờ *Ví dụ số nguyên1011 2123 + 022 + 121 + 120173 8182 + 781 + 380 = 64+56+3 = 12310A4B5 16A163 + 4162 + B161 + 5160 104096 + 4256 + 1116 + 51 = 40960+1024+176+5= 42165= 8+0+2+1 =1110Chương 1Nhập môn Công nghệ thông tin Tờ *Ví dụ số lẻ1011.01 2123 + 022 + 121 + 120 + 02-1 + 12-218 + 04 + 12 + 11 + 00.5 + 10.25 = 11.251010.4 8181 + 080 + 48-1 18 + 01 + 40.125 = 8.510Chương 1Nhập môn Công nghệ thông tin Tờ *Học thuộc lòngSố hệ 10Số hệ 16Số hệ 200000011000122001033001144010055010166011077011188100099100110A101011B101112C110013D110114E111015F1111(8+0+2+1)(0+4+2+0)(8+4+0+1)Mã 8421011010111101Chương 1Nhập môn Công nghệ thông tin Tờ *Chuyển đổi hệ số102816Dec2BinBin2DecDec2OctOct2DecHex2DecDec2HexBin2OctOct2BinHex2BinBin2HexChương 1Nhập môn Công nghệ thông tin Tờ *Phương pháp chuyển đổi sốPhương pháp Chia lấy số dưĐịnh nghĩaXxx2DecDec2XxxChia cơ sốKết quả Số hệ 10Chia cơ sốKết quả Chia cơ sốKết quả Chia cơ sốkq = 0 : dừngSố dư Số dư Số dư Số dư . . .Số hệ XxxChương 1Nhập môn Công nghệ thông tin Tờ *Ví dụ Dec2Bin2171351= 0Số hệ 22820422200121Số hệ 1012Số hệ 10 : 35 =00032Chương 1Nhập môn Công nghệ thông tin Tờ *Ví dụ Dec2Hex161252004= 0Số hệ 167Số hệ 10Số hệ 10 : 2004 =7 x 2561613 x 1647D416Chương 1Nhập môn Công nghệ thông tin Tờ *Đổi hệ 2 ra hệ 8, 16Ghép nhóm  bảng thuộc lòng11Số hệ 20001013Số hệ 842(011)(100)(010)3 bit11Số hệ 20001013Số hệ 16(0011)4 bitA(1010)Mã 8421Mã 8421Bin2OctBin2Hex3 bit3 bit4 bitChương 1Nhập môn Công nghệ thông tin Tờ *Biểu diễn thông tin bằng hệ nhị phânBIT ( BInary digiT ) : 0 1BYTE = tổ hợp 8 bit : 01001101 11111111(BYTE được chọn làm đơn vị tổ chức thông tin trong máy tính)WORD = tổ hợp nhiều bit : 10110 10111001011 KiloByte (KB) = 1024 byte = 210 byte1 MegaByte (MB) = 1024 KB = 220 byte1 GigaByte (GB) = 1024 MB = 230 byte1 số dài n bit thì biểu diễn được 2n giá trịChương 1Nhập môn Công nghệ thông tin Tờ *3. Biểu diễn dữ liệuMáy tính làm việc trên số nhị phân.Con người không thể làm việc với số nhị phân vì dài, khó nhớ.Dữ liệu cần biểu diễn, xử lý, lưu trữ bằng máy tính gồm có đại lượng số và phi số.Dữ liệu đưa vào máy tính phải được mã hóa thành số nhị phân (code) rồi mới xử lý.Chương 1Nhập môn Công nghệ thông tin Tờ *Mã hóa thông tin đầu vàoThông tinMã hóaTổ hợp bitÂm thanhHình ảnhNhiệt độChữSốÁnh sángÁp suấtĐộ ẩmĐiện ápDòng điệnXử lýChương 1Nhập môn Công nghệ thông tin Tờ *Ví dụ : mã hóa chữ cáiABCDE 5FGHIJ 10KLMNO 15PQRST 20UVWXY 25Z 262n vừa lớn hơn 26n = 5 và 25 = 32A = 00000B = 00001C = 00010D = 00011. . .Y = 11000Z = 11001Các tổ hợp11010,1101111100,1110111110,11111không dùngChọn tổ hợp n bit sao choChương 1Nhập môn Công nghệ thông tin Tờ *Biểu diễn sốSố n bit có giá trị : 0  (2n – 1)Số 8 bit có giá trị : 0  255Số 16 bit có giá trị : 0  65 535Số 32 bit có giá trị : 0  4 294 967 295Số không dấuSố có dấuQui ước: chọn bit có trọng số cao nhất (MSB) làm bit dấuSố 8 bit có dấu có giá trị : -128  +127Số 16 bit có dấu có giá trị : -32768  +32767bit dấu = 0 là số dương - bit dấu = 1 là số âmsử dụng số bù 2 : -1 = 1111 1111, -2 = 1111 1110, . . . -127 = 1000 0001, -128 = 1000 0000MSB(Most Significant Bit)LSB(Least Significant Bit)Chương 1Nhập môn Công nghệ thông tin Tờ *Số BCD (Binary Coded Decimal)1 byte chứa 1 số BCDdồnSố BCD được dùng để tính toán trên số thập phân trong hệ nhị phân.Số BCD là số viết theo hệ 16 nhưng giá trị tính theo hệ 10.Số 12BCD được viết trong hệ 2 là 0001 0010 nhưng có giá trị là 12 thay vì 18 (1216 = 1810).Phân loại BCD1 byte chứa 2 số BCDdồn13946508không04020108Chương 1Nhập môn Công nghệ thông tin Tờ *Chỉnh dạng số BCD sau khi cộng1802+1A61809+216chỉnh dạng1801+không chỉnhkết quả không đúngkết quả đúng++2027Chỉnh dạng vì A không phải là số BCDChỉnh dạng vì có nhớ ở hàng đơn vị19Chương 1Nhập môn Công nghệ thông tin Tờ *Số thực - số chấm độngSố chấm động (floating point) dùng để tính toán trên số thực.± m  B ± em (mantissa) quyết định độ chính xácB (base)e (exponent) quyết định độ lớn/nhỏMột giá trị có thể biểu diễn dưới nhiều dạng913.55129.135512  10291.35512  1010.9135512  1039135.512  10-191355.12  10-2.Khó xử lý.Cần chuẩn hóaChương 1Nhập môn Công nghệ thông tin Tờ *Số chấm động theo chuẩn IEEE 754Chuẩn IEEE 754 qui định(-1)S2E-127(1.M)Có 2 dạngChính xác đơnChính xác képdài 64 bit11152SEMdài 32 bitMũ thừa 1023Cơ số 21  (1.M) < 2(-1)S2E-1023(1.M)Mũ thừa 127Cơ số 21  (1.M) < 21823EMSSignificandChương 1Nhập môn Công nghệ thông tin Tờ *Ví dụ số chấm độngSố N = -1.5E = 127M = 1.1(-1)12127-127(1.1)N = 10111111110000000000000000000000Giới hạn (-1)02-126(1.0)  2+127(2-2-23) 1.18  10-38  3.40  10+38nghĩa làS = 1Chương 1Nhập môn Công nghệ thông tin Tờ *Biểu diễn chữChữ cáiChữ sốKý tự đặc biệtmã hóaxấunhiễu1001011giải mãđúngsaiđường truyềncó biện pháp phát hiệnparity(do bit bị đổi)A0000000010ACThông tinChương 1Nhập môn Công nghệ thông tin Tờ *Parity - Kiểm tra chẳn lẻBit kiểm tra là kết quả của phép kiểm traPhát hiện sai khi có 1 số lẻ bit thông tin bị đổi giá trị trong quá trình truyềnThực hiện bằng cách gởi kèm theo thông tin 1 bit kiểm trabitkiểm tra=nếu số bit 1 là số chẳn10nếu số bit 1 là số lẻ00000100000truyềnnhận1000101kiểm tra lại0so sánhSAIchẳnchẳnlẻlẻChương 1Nhập môn Công nghệ thông tin Tờ *Các bảng mã dùng cho ký tự6 bit = 2 bit vùng + 4 bit số = 64 ký tựMã BCD8 bit = 256 ký tựMã EBCDICBinary Coded DecimalExtended Binary Coded Decimal Interchange Code7 bit = 128 ký tựMã ASCIIAmerican Standard Code for Information Interchange8 bit = 256 ký tựMã extended ASCIIlưu trữ 1 byte/ký tự16 bit = 65536 ký tựMã Unicodelưu trữ 2 byte/ký tựMáy tính ngày nayYếu tố chữ viết các dân tộc(Tiếng Việt trên máy tính chưa thống nhất)Chương 1Nhập môn Công nghệ thông tin Tờ *Mã Gray - biểu diễn góc quay0º (000)45º (001)90º (011)180º (110)135º (010)225º (111)270º (101)315º (100)Ánh sángxuyên quaÁnh sángbị cản lạiChiều quayTùy theo góc quay mà dữ liệu đọc được sẽ khác nhau.TrịGrayBinary00000001001001201101030100114110100511110161011107100111Chương 1Nhập môn Công nghệ thông tin Tờ *Lưu trữ bằng mã ASCIIComputer43H4FH4DH50H55H54H45H52H8 ký tự8 byteChương 1Nhập môn Công nghệ thông tin Tờ *4, Luận lý máy tínhLuận lý máy tính dựa trên nền tảng một nhánh của luận lý toán học được gọi là đại số Boole (George Boole).Biến luận lý (boolean variable) có hai giá trị, thường được biểu diễn bằng 1 và 0 (bit).Về mặt hiện thực, biến luận lý thể hiện trạng thái điện áp trên giây dẫn tín hiệu (1 = 5V; 0 = 0V).Chương 1Nhập môn Công nghệ thông tin Tờ *Các phép toán trên đại số BooleNotAndNandOrXorNorPhépluận lýEx-Nor(Not And)(Not Or)(Not Xor)(Ex-Or)Chương 1Nhập môn Công nghệ thông tin Tờ *Phép NotKý hiệu dấu gạch ngang trên đầux = 1011  x = 0100 x = 1011 = xxx0110Bảng sự thậtChương 1Nhập môn Công nghệ thông tin Tờ *Phép AndKý hiệu dấu chấmnhư phép nhâny . 0 = 0y . 1 = yNhận xétxyx . y000010100111Bảng sự thậtChương 1Nhập môn Công nghệ thông tin Tờ *Phép OrKý hiệu dấu cộngnhư phép cộngy + 0 = yy + 1 = 1Nhận xétxyx + y000011101111Bảng sự thậtChương 1Nhập môn Công nghệ thông tin Tờ *x . yx . yyx0000011101100111001100001100f(x,y)yxVí dụ phép luận lýTính hàm f(x,y) = x . y + x . yChương 1Nhập môn Công nghệ thông tin Tờ *Phép Xor (Ex-Or)Ký hiệu dấu cộng trong vòng tròn như phép moduloy  0 = yy  1 = yNhận xétxyx  y000011101110Bảng sự thậtChương 1Nhập môn Công nghệ thông tin Tờ *Bảng tóm tắtNOTANDORXORxy not yx and yx or yx xor y001000010011101011110110y and 0 = 0y and 1 = yy or 0 = yy or 1 = 1y xor 0 = yy xor 1 = not yBảng sự thậtChương 1Nhập môn Công nghệ thông tin Tờ *Cổng luận lýNOTANDORXORBUFFERNANDNOREX-NORChương 1Nhập môn Công nghệ thông tin Tờ *Chức năng đóng mởVCCR1S1mức luận lý 1 = 5Vmức luận lý 0 = 0Vy and 1 = ymức 1mức 00 = đóngCổng AND11 = mởy and 0 = 0Chương 1Nhập môn Công nghệ thông tin Tờ *0Chức năng đóng mở (tt.)VCCR1S1mức luận lý 1 = 5Vmức luận lý 0 = 0Vy or 1 = 1mức 1mức 00 = mởCổng OR1 = đóngy or 0 = yChương 1Nhập môn Công nghệ thông tin Tờ *Ứng dụng đơn giản của cổng luận lýMạch cộng bán phần thực hiện phép cộng trên hai bit, cho ra kết quả là bit tổng S và bit nhớ C.Mạch cộng toàn phần cũng tương tự mạch cộng bán phần nhưng đầu vào có cộng thêm bit nhớ C0.Mạch cộng toàn phần có thể được thiết kế dựa vào mạch cộng bán phần.Chương 1Nhập môn Công nghệ thông tin Tờ *Mạch cộng bán phầnMạch cộngySCxxySCxySC0000011010101101ANDXORChương 1Nhập môn Công nghệ thông tin Tờ *Mạch cộng toàn phầnMạch cộng toàn phầnySCxC0S = x + y + C0S = (x + y) + C0Tính: S1 = x + yTính: S2 = S1 + C0Cần bộ cộngbán phần 1Cần bộ cộngbán phần 2Chương 1Nhập môn Công nghệ thông tin Tờ *Mạch cộng toàn phần (tt.)Bán phầnSBán phầnyS1xC1C2Cổng gì?CC0Nhớ (C = 1) trong trường hợp nào ?Chương 1Nhập môn Công nghệ thông tin Tờ *Mạch cộng toàn phần (tt.)C0xySCC0S1C1C2C00000000000011001000010100100001101001011001010000101011101111001110111111110101C = 1 khi C1 = 1 hoặc C2 = 1Chương 1Nhập môn Công nghệ thông tin Tờ *Mạch cộng toàn phần (tt.)C0xyS1SC1C2CMạch cộng bán phầnMạch cộng bán phầnChương 1Nhập môn Công nghệ thông tin Tờ *Mạch cộng nhiều bity0S0x00S1S2S3Cx1x2x3y1y2y3Cộng 0Cộng 1Cộng 2Cộng 3x3x2x1x0S4 S3S2S1S0y3y2y1y0+