›

Khoa học máy tính - Chương 1: Giới thiệu tổng quan

ppt 79 trang vanle 4120
Download
Bạn đang xem 20 trang mẫu của tài liệu "Khoa học máy tính - Chương 1: Giới thiệu tổng quan", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

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

  • pptkhoa_hoc_may_tinh_chuong_1_gioi_thieu_tong_quan.ppt

Nội dung text: Khoa học máy tính - Chương 1: Giới thiệu tổng quan

  1. GIỚI THIỆU KHOA HỌC MÁY TÍNH NGUYỄN THANH TRUNG 1
  2. Chương1 – GIỚI THIỆU TỔNG QUAN ◼ 1.1. Sơ lược về máy tính và ngành KHMT ◼ 1.2. Biểu diễn thơng tin trong máy tính ◼ 1.3. Các cổng logic cơ bản 2
  3. 1.1. Sơ lược về máy tính • Máy tính (Computer) là một thiết bị điện tử dùng để lưu trữ và xử lý thơng tin theo các chương trình định trước. • Máy tính, máy tính tương tự (Analog), máy tính số (Digital) Sơ lược về lịch sử và phân loại máy tính 3
  4. 1.1.1.LỊCH SỬ PHÁT TRIỂN 4
  5. Các thế hệ máy tính Blaise Pascal (Pháp- 1642) ENIAC (1946) Intel 8080 (1974) Charles Babbage (Anh- 18.000 bĩng đèn được xem như CPU 1830) 1500 rờ le đầu tiên được tích hợp 30 tấn trên 1 chip 140 KW IBM 360 (1965) Von Neumann (1945) PDP-1 (1961) Cơ Đèn điện tử 80x86 (1978) Transistors IC ? (1642 - 1945) (1945 - 1955) (1955 - (1965 - (1980 - ????) Bộ nhớ dây trễ, tĩnh Bộ nhớ1965) xuyến 1980) +, -, X, : điện. Giấy, phiếu đục từ. Băng từ, lổ. Băng từ trống từ, đĩa từ. 5
  6. *Thế hệ thứ nhất (1945-1955) máy tính dùng đèn điện tử: Trong những năm 40- 50 các thiết bị đầu tiên của máy tính điện tử được xây dựng và phát triển với. + Phần cứng: Chủ yếu là dùng đèn điện tử, độ tin cậy thấp, tốc độ chậm tiêu hao năng lượng rất lớn. Ví dụ: Chiếc máy tính điện tử đầu tiên là chiếc ENIAC(Electronic Numberical Intergrator And Calculator) do John Mauchley và J.Presper Eckert thiết kế. Nĩ bao gồm 18.000 đèn điện tử, 1.500 rơle, nặng 30 tấn tiêu thụ 140 KW điện. Dùng hệ thập phân + Phần mềm: Chủ yếu dùng ngơn ngữ máy và đặt cơng tắc bật tắt trực tiếp. Ví dụ: Với chiếc ENIAC người ta phải đặt 6000 switch. 6
  7. Máy tính ENIAC 7
  8. Máy IAS (Institude of Advanced Study) ◼ Do Von Neumann thiết kế, gồm các thành phần cơ bản sau (1947-1952) ◼ Máy tính hệ 2 đầu tiên 8
  9. John von Neumann và IAS 9
  10. *Thế hệ thứ hai (1955-1965) máy tính dúng thiết bị bán dẫn: + Phần cứng: Dùng linh kiện mới là Transitor (được phịng thí nghiệm Bell phát triển năm 1948). Bộ nhớ máy tính được tăng lên đáng kể và trở nên nhỏ gọn hơn. Chiếc máy đầu tiên của thế hệ này là chiếc TX-0. + Phần mềm: Đã bắt đầu sử dụng các ngơn ngữ lập trình bậc cao như Cobol, PL1, 10
  11. Các máy tính tiêu biểu 11
  12. *Thế hệ thứ ba (1965-1980) dùng mạch hợp tích hợp IC: +Phần cứng: Cơng nghệ điện tử giờ đã phát triển rất nhanh cho phép đặt hàng chục Transitor vào một vỏ chung gọi là con chip. Linh kiện chủ yếu là các mạch tích hợp IC, đã bắt đầu xuất hiện đĩa từ để lưu trữ dữ liệu. Cho phép tốc độ tính tốn đạt vài triệu phép tính/giây, cĩ dung lượng bộ nhớ trong lên tới nhiều Mega bytes (MB). +Phần mềm: Đã xuất hiện các hệ điều hành thế hệ đầu tiên. Các phần mềm ứng dụng ngày càng phát triển. 12
  13. *Thế hệ thứ tư (1980-199x) sử dụng cơng nghệ (VLSI): + Phần cứng: Vào những năm 80 cơng nghệ (VLSI - Very Large Scale Integrator) ra đời cho phép tích hợp trong một con chip hàng triệu Transitor khiến cho máy tính trở nên nhỏ hơn, nhanh hơn với tốc độ hàng triệu phép tính một giây là nền tảng cho chiếc máy tính PC (Personal Computer) ngày nay. + Phần mềm: Cùng với sự phát triển của máy tính các phần mềm ứng dụng đã phát triển như vũ bão làm cho tin học len lỏi vào mọi ứng dụng trong cuộc sống. 13
  14. Thế hệ thứ 5: Người máy ? ◼ Hiện nay đang được nghiên cứu và phát triển dưới dạng các máy tính thơng minh, robot, ◼ Ví dụ: Deep Blue, Asimo, 14
  15. 1.1.2.Các loại máy tính + Máy tính cá nhân (Personal Computer): Là máy tính để bàn, chỉ cĩ một chíp xử lý và thường dùng cho một người. + Máy tính Mini (Minicomputer): Thường được dùng trong các lĩnh vực ứng dụng thời gian thực và cho các ứng dụng vừa và nhỏ trong các dây chuyền sản xuất hay trong hàng khơng. + Máy tính lớn (Main Frame): Thường dùng trong các trung tâm tính tốn địi hỏi phải tốc độ xử lý tốt. + Siêu máy tính (Super Computer): Là một hệ thống gồm nhiều máy lớn ghép song song cĩ tốc độ tính tốn cực kỳ lớn và thường dùng trong các lĩnh vực đặc biệt, chủ yếu trong quân sự và vũ trụ. Siêu máy tính Deep Blue là một trong những chiếc thuộc loại này. 15
  16. 1.1.3.CÁC KHÁI NIỆM CƠ BẢN ◼ Thơng tin: là một khái niệm trừu tượng mơ tả tất cả những gì đem lại hiểu biết, nhận thức của con người và các sinh vật sống khác. ◼ Dữ liệu ◼ Dữ liệu (dữ kiện) cĩ thể hiểu nơm na là vật liệu thơ mang thơng tin. ◼ Dữ liệu được tập hợp lại và được xử lí sẽ cho ta thơng tin. ◼ => Dữ liệu là nguồn gốc, là vật mang thơng tin, là vật liệu sản xuất ra thơng tin. 16
  17. Dữ liệu trong thực tế cĩ thể là ◼ Tín hiệu vật lí (Physical signal) ◼ Các số liệu (number) ◼ Kí hiệu (symbol) Thí dụ 1: Nhiệt độ cháu bé 39oC Thí dụ 2: 28, 27, 30, 32, 27 ? Thí dụ 3: Tính qui ước biểu diễn thơng tin I là chữ cái i hay là số I La mã ? 17
  18. Xử lí thơng tin ◼ lọc lấy thơng tin cần thiết ◼ truyền tin: nhanh, chính xác ◼ lọc nhiễu ◼ lưu trữ ◼ tìm kiếm, lấy ra ◼ sao chép ◼ mã hố bảo mật ◼ 18
  19. Xử lí thơng tin bằng máy tính ◼ Khi thơng tin ít, cĩ thể làm thủ cơng. ◼ Khi thơng tin nhiều lên, địi hỏi máy mĩc tự động làm thay, đặc biệt là máy tính điện tử. ◼ Ưu điểm của máy tính: Làm nhanh, khơng biết chán, chính xác Vµo d÷ liƯu Xư lÝ Ra d÷ liƯu (Input) (Processing) (Output) Lu tr÷ (Storage) 19
  20. ◼ Phần cứng (Hardware) ◼ Phần mềm (Software) ◼ Chương trình, lập trình ◼ 20
  21. 1.2. Biểu diễn thơng tin trong máy tính Làm thế nào để biểu diễn thơng tin trong máy tính ? →Ta phải dùng mã nhị phân ! Mã nhị phân là gì ? → 00111010 → bit (Binary Digit) Làm cách nào ? 21
  22. Các dạng Thơng tin Ánh sáng Âm Hình Độ ẩm thanh Số ảnh Nhiệt Điện áp Thơng tin độ Áp suất Chữ Mã hĩa Dịng điện Tổ hợp bit Xử lý 22
  23. Mã hĩa thơng tin ? ◼ Thơng tin để máy tính xử lí được thì cần phải biến đổi thành một dãy bit. Cách biến đổi như vậy gọi là mã hố thơng tin. Biến đổi ngược lại ? ◼ Người ta sử dụng mã ASCII để mã hố kí tự. Bảng mã ASCII gồm 256 kí tự ◼ Ví dụ: Kí tự “A” cĩ mã ASCII thập phân là 65 và mã ASCII nhị phân là 01000001. ◼ Để chuyển tín hiệu âm thanh → máy tính cần cĩ bộ chuyển đổi: Card âm thanh ◼ 23
  24. Đơn vị đo thơng tin ◼ Đơn vị cơ bản để đo thơng tin được gọi là bit. ◼ 1 bit cĩ 2 trạng thái : 0/1 ◼ Dãy số 0101 gọi là số nhị phân - số hệ 2 ◼ Dãy 8 bit = 1 byte. ◼ Ngồi ra ta cĩ các đơn vị lớn hơn để đo thơng tin. 24
  25. Các bội số của Byte Kilobyte (KB) 1 nghìn Byte Megabyte (MB) 1 triệu Byte Gigabyte (GB) 1 tỉ Byte Terabyte (TB) 1 Nghìn tỉ Byte Petabyte (PB) 1 nghìn triệu triệu Exabyte (EB) 1018 Byte Zettabyte (ZB) 1021 Byte Yottabyte (YB) 1042 Byte p. 350 Next 25
  26. Biểu diễn các dạng thơng tin cơ bản trong máy tính ◼ Dạng Số ◼ Dạng văn bản: Dạng quen thuộc gồm các chữ cái, chữ số ◼ Dạng hình ảnh: Bức tranh, bản đồ, băng hình ◼ Dạng âm thanh:Tiếng nĩi con người, tiếng sĩng, bản nhạc ◼ Nhiệt độ 26
  27. 1.2.1. Biểu diễn số Hệ đếm: Tập các ký hiệu, quy tắc dùng để biểu diễn , tính tốn các giá trị. Gồm: •Hệ đếm khơng theo vị trí: Số La mã •Hệ đếm theo vị trí: Hệ thập phân, nhị phân, Hexa, Ví dụ: 2356 = 2 x 103 + 3 x 102 + 5 x 101 + 6 x 100 → Một số X bất kỳ cĩ thể biểu diễn như sau: n-1 n-2 n-3 0 X = xn-1a + xn-2a + xn-3a + + x0a + -1 -2 x-1a + x-2a + (1) Trong đĩ : a gọi là cơ số 27
  28. Một số hệ đếm theo vị trí thơng dụng: Hệ thập phân – Decimal (cơ số 10 ): Dùng tập số {0,1, ,9} Ví dụ: 123d; 25,4 ; 580, Nhị phân – Binary (cơ số 2): Dùng tập số {0,1}, Ví dụ: 10001110b; 11000010b Hệ bát phân (cơ số 8): Dùng tập số {0,1, 7} Thập lục phân - HexaDecimal (cơ số 16): Dùng tập số {0,1, 9,A,B,C,D,E,F}, Ví dụ: AC0Dh, 123h, 28
  29. Số hệ 10 Số hệ 16 Số hệ 2 0 0 0000 1 1 0001 2 2 0010 3 3 0011 4 4 0100 5 5 0101 6 6 0110 7 7 0111 8 8 1000 9 9 1001 10 A 1010 11 B 1011 12 C 1100 13 D 1101 14 E 1110 15 F 1111 29
  30. Chuyển đổi giữa các hệ đếm •Thập phân (nguyên) → nhị phân: Chia liên tiếp cho 2, đến khi kết quả bằng 0. Đảo ngược trật tự các số dư → số nhị phân tương ứng. Vd: 12d = 1100b •Thập phân → Hexa: tương tự ta chia liên tiếp cho 16 •Nhị phân → Thập phân : Dùng cơng thức (1) •Hexa → thập phân : Dùng cơng thức (1). 30
  31. Chuyển đổi giữa các hệ đếm (tt) •Nhị phân → Hexa: Nhĩm 4 bit (Nibble) của số nhị phân tương ứng 1 số Hexa (Nhĩm từ phải sang). Ví dụ: 100 1100 0110 1010b = 4C6Ah •Hexa → nhị phân: Cứ 1 số Hexa tương ứng 4 số nhị phân. Ví dụ: 1ADFh= 0001 1010 1101 1111b 31
  32. Chuyển đổi giữa các hệ đếm (tt) •Trường hợp thập phân khơng nguyên → nhị phân thì : •phần nguyên : Chia liên tiếp cho 2, đến khi kết quả bằng 0. Đảo ngược trật tự các số dư → số nhị phân tương ứng. •Phần lẻ: Nhân kết quả với 2 liên tục cho đến khi hết phần lẻ Vd: 12,125d = 1100,0010b vì: Phần nguyên đổi sang được 1100 Phần lẻ : 0,125 x 2 = 0,25 x 2 = 0,5 x 2 = 1,0 → 001 32
  33. Chuyển đổi giữa các hệ đếm (tt) Trường hợp nhị phân khơng nguyên → thập phân thì áp dụng cơng thức (1) Ví dụ: 1100,0010b = 1x 23 + 1x 22 + 0x 21 + 0x 20 + 0x 2-1 + 0x 2-2 + 1x 2-3 = 8 + 4 +0 +0 + 0 + 0 + 0,125 = 12,125d Trường hợp số nhị phân khơng nguyên → Hexa ? 33
  34. Biểu diễn số trong máy tính Biểu diễn số nguyên Gồm số nguyên khơng dấu và số nguyên cĩ dấu. Biểu diễn Số nguyên khơng dấu Dùng để biểu diễn các đại lượng nguyên dương như địa chỉ ơ nhớ, mã ASCII, tuỳ vào số byte biểu diễn mà phạm vi biểu diễn của số nguyên khơng dấu là khác nhau, cụ thể: Số 8 bit (1 Byte): 256 số khác nhau từ 0, 1, 2, ,28 –1 Số 16 bit (2 Byte): 65536 số khác nhau từ 0, 1, 2, ,216 –1 35
  35. BIỂU DIỄN SỐ NGUYÊN CĨ DẤU ◼ Biểu diễn bằng giá trị tuyệt đối ◼ Biểu diễn bằng số bù 2 36
  36. BIỂU DIỄN BẰNG GIÁ TRỊ TUYỆT ĐỐI ◼ Bit cao nhất được sử dụng làm bit dấu ◼ Số dương biểu diễn bởi 0 ◼ Số âm biểu diễn bởi 1 ◼ Các bit cịn lại biểu diễn giá trị (tuyệt đối) n-1 n-1 ◼ Khoảng biểu diễn (-(2 -1), 2 -1) ◼ Hệ quả: cĩ 2 số 0 là số 0 dương (+0) và số khơng âm (-0) 37
  37. BIỂU DIỄN BẰNG SỐ BÙ 2 ◼ Số bù 1 của một số: là số thu được khi lấy số bao gồm tồn bit 1 trừ đi số đĩ. (Thực chất chính là đảo từng bit của số đĩ) ◼ Số bù 2 của một số: là số bù 1 của số đĩ cộng 1 ◼ Số bù 2 của một số: được sử dụng để biểu diễn giá trị đảo của số đĩ n-1 n-1 ◼ Khoảng biểu diễn (-2 , 2 -1) 38
  38. Biểu diễn số trong máy tính (tt) Biểu diễn Số thực: Bằng dấu chấm tĩnh và dấu chấm động Bằng dấu chấm tĩnh 39
  39. Bằng dấu chấm động (chuẩn IEEE/754) ĐỘ chính xác đơn (32 bit) S E F ◼ S - phần dấu (1 bit) là dấu của phần định trị (0 là dương; 1 là âm) ◼ E - phần mũ (8 bit) là số mũ với cơ số 2 ◼ F - phần định trị (23 bit) là phần phân s E - 127 ◼ Giá trị của số được biểu diễn (-1) x 2 x(1 .F) 40
  40. Bằng dấu chấm động (chuẩn IEEE/754) ĐỘ chính xác kép (64 bit) S E F ◼ S - phần dấu (1 bit) là dấu của phần định trị (0 là dương; 1 là âm) ◼ E - phần mũ (11 bit) là số mũ với cơ số 2 ◼ F - phần định trị (52 bit) là phần phân số s E - 1023 ◼ Giá trị của số được biểu diễn (-1) x 2 x(1.F) 41
  41. Biểu diễn ký tự Các loại mã khác biểu diễn ký tự ◼ASCII (Ameriacan Standard Code for Information Interchange) ◼ISO (International Organization for Standardization) ◼JIS (Japanese Industrial Standards) ◼EBCDIC (Extended Binary Coded Decimal Interchange Code) ◼Unicode 42
  42. ASCII Bảng mã ASCII Americain Standard Code for Information Interchange) Dùng 1 byte để mã hố nên cĩ 256 ơ kí tự. 26 chữ cái latin ‘a’ ’z’, 26 chữ cái hoa 10 chữ số thập phân ‘0’ ’9’ Các dấu chấm câu Các kí tự điều khiển 128 kí tự đầu tiên là chuẩn quốc tế 128 kí tự sau (128 255) thay đổi theo quốc gia 43
  43. ◼Mã từ 0 127 → chuẩn, người dùng khơng thể thay đổi. ✓Văn bản dùng mã này gọi là văn bản thơ (plain text) khác với văn bản Rich text với nhiều kiểu định dạng hơn. ✓32 ký tự đầu là mã điều khiển, khơng nhìn thấy được (32 ký tự này tương ứng ký tự A Z – 64 → dùng phím Ctrl trên bàn phím). ✓Ngồi ra 1 mã ASCII bất kỳ cĩ thể được nhận qua bàn phím bằng cách nhấn ALT + mã thập phân của ký tự đĩ. ✓Mã ASCII mở rộng tính từ 128 255 dùng cho các ký hiệu khác và người dùng cĩ thể thay đổi. ✓Với 256 ký tự cĩ thể biểu diễn các từ trong tiếng Anh, Đức, Và tạm đủ cho tiếng Việt nhưng khơng thể đủ cho các chữ tượng hình trong tiếng Trung Quốc, Nhật,44
  44. ◼ISO (International Organization for Standardization): Các mã ISO 10646 được đưa ra vào năm 1983 với 2 Byte, nhằm đáp ứng cho các chữ tượng hình nĩi trên nhưng cũng khơng được thống nhất. ◼JIS (Japanese Industrial Standards) ◼Unicode: Do hãng Xerox đưa ra dùng 2 Byte để mã hố 1 ký tự, hiện nay mã này đang được khuyến khích dùng như bản mã chuẩn. Là mã 16 bit nên khi dùng trong mơi trường 8 bit (truyền dữ liệu hoặc lập trình API) → chuỗi byte theo quy định UTF-8 (Unicode Transformation Format - 8). 45
  45. Biểu diễn âm thanh: Audio Người ta mã hố âm thanh theo hệ nhị phân bằng cách ngắt âm thanh ra thành nhiều giá trị cĩ khoảng thời gian nhất định. Sau đĩ máy tính gán cho mỗi giá trị tương ứng 1 mã nhị phân và lưu tuần tự trong tập tin. Với thính giác con người chỉ phân biệt được tần số âm thanh tối đa là 20 KHz nên khi lấy mẫu người ta ngắt âm thanh theo tần số lớn hơn 2 lần tần số tối đa đĩ. Chuẩn tần số lấy mẫu hiện nay là 44KHz. Để biểu diễn 1 giá trị âm thanh cĩ thể dùng 8 bit (256 giá trị khác nhau). Hiện nay người ta dùng 16 bit. Các định dạng file âm thanh như Wave, Midi 46
  46. Biểu diễn hình ảnh: Để biểu diễn ảnh đồ hoạ người ta cĩ thể dùng 2 phương pháp là đồ hoạ điểm và đồ hoạ vectơ. Đồ hoạ điểm: Đồ hoạ điểm biểu diễn ảnh bằng ma trận điểm ảnh. Cĩ thể dùng 1/2/3/4 Byte để biểu diễn 1 điểm ảnh. Người ta ghi thơng tin của điểm ảnh lên tập tin dưới các định dạng BMP, GIF, JPG, Ảnh biểu diễn theo cách này tốn rất nhiều bộ nhớ. 47
  47. Biểu diễn hình ảnh (tt) Đồ hoạ vectơ: Chia hình ảnh ra thành nhiều đối tượng như Điểm, đường thẳng, đa giác, mặt, khối. Máy tính dùng cơng thức tính tốn vectơ để dựng nên các hình ảnh từ các đối tượng cơ bản trên. Cĩ thể xử lý các đối tượng và đặc tính đối tượng bằng mã lệnh nên lưu trữ ít tốn bộ nhớ. Đồ hoạ vectơ cĩ thể hiển thị được hình ảnh 3-D. 48
  48. Biểu diễn hình ảnh động ◼ Để biểu diễn ảnh động theo điểm ảnh người ta cĩ thể cho hiển thị 30 ảnh / giây để tạo nên ảnh động → 1 đoạn phim 1 giây phải lưu đến 30 ảnh mới tạo nên cảm giác liên tục → tốn bộ nhớ → Nén dữ liệu. ◼ Các định dạng: MPEG, MOV, dùng để nén từng ảnh tĩnh và nén những phần ảnh khơng đổi theo thời gian. ◼ Đối với việc biểu diễn ảnh động theo vectơ, người ta thêm 1 hàm để mơ tả vị trí của đối tượng trong khơng gian theo thời gian.→ Cần máy cĩ cơng suất lớn. 49
  49. Biểu diễn các thơng tin khác ◼ Người ta cũng cĩ thể số hố các đại lượng dạng tương tự trong tự nhiên thành rời rạc trong máy tính bằng các bộ cảm biến để chuyển các tín hiệu vật lý → điện. ◼ Các thiết bị chuyển đổi như vậy gọi là ADC (Analog to Digital Convert) hay DAC (Digital to Analog Convert). 50
  50. 1.3. Các mạch cơ bản • Luận lý máy tính dựa trên nền tảng một nhánh của luận lý tố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. 51
  51. Các phép tốn trên đại số Boole Not Phép luận lý And Or Ex-Nor (Not Xor) Nor Xor (Ex-Or) (Not Or) Nand (Not And) 52
  52. Phép Not Ký hiệu dấu gạch ngang trên đầu Bảng sự thật x x 0 1 1 0 x = 1011 x = 0100 x = 1011 = x 53
  53. Phép And Ký hiệu dấu chấm như phép nhân Bảng sự thật x y x . y Nhận xét 0 0 0 y . 0 = 0 0 1 0 1 0 0 y . 1 = y 1 1 1 54
  54. Phép Or Ký hiệu dấu cộng như phép cộng Bảng sự thật x y x + y Nhận xét 0 0 0 y + 0 = y 0 1 1 1 0 1 y + 1 = 1 1 1 1 55
  55. Phép Xor (Ex-Or) Ký hiệu dấu cộng trong vịng trịn như phép modulo Bảng sự thật x y x  y Nhận xét 0 0 0 y  0 = y 0 1 1 1 0 1 y  1 = y 1 1 0 56
  56. Bảng tĩm tắt Bảng sự NOT AND OR XOR thật x y not y x and y x or y x xor y 0 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 1 1 0 1 1 0 y and 0 = 0 y or 0 = y y xor 0 = y y and 1 = y y or 1 = 1 y xor 1 = not y 57
  57. Các mạch cơ bản dùng trong máy tính 58
  58. Cổng luận lý NOT BUFFER AND NAND OR NOR XOR EX-NOR 59
  59. Chức năng đĩng mở mức luận lý 1 = 5V mức luận lý 0 = 0V y and 1 = y 1 = mở y and 0 = 0 0 = đĩng 60
  60. Chức năng đĩng mở (tt.) mức luận lý 1 = 5V mức luận lý 0 = 0V VCC R1 y or 1 = 1 mức 1 1 = đĩng S1 0 C ng OR y or 0 = y mức 0 ổ 0 = mở 61
  61. Các mạch tích hợp • 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 tồ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. • Các mạch dãy (Flip/flop) 62
  62. Mạch cộng bán phần x Mạch S XOR cộng y C x S y x y S C C 0 0 0 0 0 1 1 0 AND 1 0 1 0 1 1 0 1 63
  63. Mạch cộng tồn phần C 0 Mạch S cộng x tồn y phần C Cần bộ cộng S = x + y + C 0 bán phần 1 S = (x + y) + C0 Tính: S1 = x + y Cần bộ Tính: S2 = S1 + C0 cộng bán phần 2 64
  64. Mạch cộng tồn phần (tt.) C0 Mạch S cộng bán S1 C x Mạch phần 2 cộng bán C1 C y phần 65
  65. Mạch cộng nhiều bit x3x2x1x S + 0 0 0 x0 Cộng 0 y3y2y1y0 y0 S4 S1 S3S2S1S0 x1 Cộng 1 y1 S2 x2 Cộng 2 y2 S3 x3 Cộng 3 y3 C 66
  66. 1.4. Khoa học máy tính • Computer science hay computing science • Là ngành nghiên cứu các cơ sở lý thuyết về thơng tin và tính tốn cùng với việc thực hiện và ứng dụng của chúng trong các hệ thống máy tính. 67
  67. Các lĩnh vực của khoa học máy tính • Cơ sở tốn học • Lý thuyết tính tốn • Cấu trúc dữ liệu và giải thuật • Ngơn ngữ lập trình và trình biên dịch • Hệ thống phân tán, song song, tương tranh • Kỹ nghệ phần mềm • Kiến trúc máy tính • Truyền thơng • Cơ sở dữ liệu • Trí tuệ nhân tạo • 68
  68. Cơ sở tốn học • Lơgic tốn (Mathematical logic) – Lơgic Bool và các phương pháp tương ứng dùng để mơ hình hĩa các truy vấn lơgic; Sự sử dụng các phương pháp chứng minh hình thức (formal proof). • Lý thuyết số (Number theory) – Lý thuyết về chứng minh và các khảo nghiệm trong việc tìm những chứng minh trong giới hạn các số nguyên. Lý thuyết số được sử dụng trong mật mã học và đồng thời được dùng như một phương thức kiểm thử trong trí tuệ nhân tạo. • Lý thuyết đồ thị (Graph theory) – Cơ sở cho cấu trúc dữ liệu và các thuật tốn tìm kiếm 69
  69. Lý thuyết tính tốn • Lý thuyết Ơtơmat (Automata theory) – Các cấu trúc lơgic khác nhau cĩ thể sử dụng để giải quyết các bài tốn. • Lý thuyết khả năng tính tốn (Computability theory) – Những gì cĩ thể tính tốn được bằng các mơ hình máy tính hiện tại. Các chứng minh của Alan Turing và những người khác trình bày cho chúng ta biết được khả năng những gì cĩ thể tính tốn được và những gì khơng thể. • Lý thuyết độ phức tạp tính tốn (Computational complexity theory) 70
  70. Cấu trúc dữ liệu và giải thuật • Phân tích thuật tốn (Analysis of algorithms) – Độ phức tạp về thời gian và khơng gian của các thuật tốn. • Thuật tốn (Algorithms) – Các quá trình lơgic trên nguyên tắc được sử dụng cho việc tính tốn và tính hiệu quả của các quá trình này. • Cấu trúc dữ liệu (Data structures) – Tổ chức của dữ liệu và các quy tắc thao tác dữ liệu. 71
  71. Ngơn ngữ lập trình và trình biên dịch • Trình biên dịch (Compilers) – Những phương thức khác nhau dùng để dịch các chương trình máy tính, thường là từ các ngơn ngữ lập trình bậc cao sang các ngơn ngữ lập trình bậc thấp. • Trình thơng dịch (Interpreter) – Một chương trình sử dụng để biên dịch và thi hành trực tiếp một chương trình phần mềm khác dùng trong máy tính mà khơng phải thơng qua quá trình biên dịch. • Ngơn ngữ lập trình (Programming languages) – Các khuơn mẫu ngơn ngữ dùng để biểu diễn các thuật tốn. 72
  72. Hệ thống phân tán, song song, tương tranh • Tương tranh (Concurrency) – Lý thuyết và thực tiễn của tính tốn đồng thời; an tồn dữ liệu trong mơi trường đa nhiệm hay đa luồng bất kỳ. • Tính tốn phân tán (Distributed computing) – Tính tốn sử dụng nhiều thiết bị tính tốn trên một mạng để thực hiện một nhiệm vụ hoặc một mục tiêu chung. • Tính tốn song song (Parallel computing) – Tính tốn sử dụng nhiều luồng thực thi đồng thời. 73
  73. Kỹ nghệ phần mềm • Thiết kế thuật tốn (Algorithm design) • Lập trình máy tính (Computer programming) • Các phương pháp hình thức (Formal methods) – Sử dụng tốn học để miêu tả và lập luận đối với các thiết kế phần mềm. • Kỹ nghệ phần mềm (Software development) – Những nguyên lý và thực hành trong việc thiết kế, phát triển và kiểm thử các chương trình, cùng những phương pháp thực hành kỹ nghệ đúng đắn. • 74
  74. Kiến trúc máy tính • Kiến trúc máy tính (Computer architecture) – Việc thiết kế, tổ chức, tối ưu hĩa và kiểm định một hệ thống máy tính, chủ yếu về CPU và tiểu hệ bộ nhớ máy tính (và hệ thống bus nối giữa chúng). • Tổ chức máy tính (Computer organization) – Nghiên cứu các kiến trúc máy tính trên cơ sở các mơ tả mạch điện, bộ xử lý trung tâm, bộ xử lý tín hiệu số của máy tính. • Hệ điều hành – Những hệ thống dùng để quản lý các tài nguyên máy tính và cung cấp nền tảng cơ bản cho một hệ thống khả dụng. 75
  75. Truyền thơng • Xử lý âm thanh trong máy tính (Computer audio) – Những thuật tốn và cấu trúc dữ liệu dùng để kiến tạo, thao tác, lưu trữ, và truyền thanh các bản ghi âm thanh kỹ thuật số (digital audio), nhận dạng giọng nĩi (voice recognition). • Mạng máy tính (Computer networking) – Các giao thức dành cho việc truyền thơng dữ liệu một cách đáng tin cậy qua các mơi trường truyền thơng chuyên dụng hoặc chia sẻ khác nhau. Thường khi bao gồm cả việc sửa lỗi (error correction) trong truyền thơng. • Mật mã học (Cryptography) – Áp dụng kết quả của các lý thuyết độ phức tạp tính tốn, lý thuyết xác suất, và lý thuyết số để kiến tạo và phá mật76 mã.
  76. Cơ sở dữ liệu • Khai phá dữ liệu (Data mining) – Nghiên cứu các phương pháp sàng lọc, rút ra những thơng tin cần thiết từ các nguồn dữ liệu khác nhau. • Cơ sở dữ liệu quan hệ (Relational databases) – Nghiên cứu các thuật tốn tìm kiếm và xử lý thơng tin trong các tài liệu và cơ sở dữ liệu; cĩ quan hệ gần gũi với ngành thu thập thơng tin (information retrieval). • CSDL hướng đối tượng, 77
  77. Trí tuệ nhân tạo • Trí tuệ nhân tạo (Artificial intelligence) – Sự nghiên cứu và thực thi các hệ thống cĩ khả năng tự thể hiện trí thơng minh hoặc tự biểu đạt những hành vi của chính bản thân mình. • Lập luận tự động (Automated reasoning) – Nghiên cứu các động cơ giải quyết bài tốn, chẳng hạn như được sử dụng trong Prolog, các động cơ này tạo ra các bước dẫn đến một kết quả nếu cho trước một truy vấn về một sự kiện và một cơ sở dữ liệu gồm các luật (rule database). • Máy học (Machine learning) – Nghiên cứu việc tự động tạo nhĩm các luật và tiên đề dựa trên những dữ liệu cho trước. • Xử lý ngơn ngữ tự nhiên – Tự động hĩa việc tiếp thu và kiến tạo ngơn ngữ lồi người. • Rơbơ học (Robotics) :Các thuật tốn điều khiển hành vi của rơbơ. 78
  78. Bài tập • Tìm hiểu lỗi truyền thơng và các cơ chế kiểm tra, sửa lỗi: – Parity bit – Mã sữa lỗi • Nộp báo cáo bằng bản viết tay khoảng 1→2 trang A4 (tính vào điểm BTCN) • Tuần sau nộp 79