Bài 1: Tin học là một ngành khoa học

BÀI 1. TIN HỌC LÀ MỘT NGÀNH KHOA HỌC

1. Sự hình thành và phát triển của khoa học.

- Tin học được hình thành và phát triển thành một ngành khoa học độc lập, có nội dung, mục tiêu, phương pháp nghiên cứu riêng.
- Tin học có ứng dụng trong hầu hết các lĩnh vực hoạt động của xã hội loài người.
- Ngành tin học gắn liền với việc phát triển và sử dụng máy tính điện tử.

2. Đặc tính và vai trò của máy tính điện tử

 a. Đặc tính:

- Máy tính có thể "làm việc không mệt mỏi" trong suốt 24/24 giờ.
- Tốc độ xử lý thông tin nhanh
- Độ chính xác cao.
- Lưu trữ được một lượng lớn  thông tin trong một không gian hạn chế.
- Giá thành ngày càng hạ.
- Máy tính ngày càng gọn nhẹ, tiện dụng và phổ biến.
- Các máy tính có thể liên kết với nhau thành một mạng và có thể chia sẻ tài nguyên giữa các máy với nhau.

b. Vai trò:

- Là một công cụ lao động do con người sáng tạo ra để trợ giúp trong công việc, hiện không thể thiếu trong kỉ nguyên thông tin.

3. Thuật ngữ “Tin học”:

- Tin học là một ngành khoa học có mục tiêu là phát triển và sử dụng máy tính điện tử để nghiên cứu cấu trúc, tính chất của thông tin, phương pháp thu thập, lưu trữ, tìm kiếm, biến đổi, truyền thông tin và ứng dụng vào các lĩnh vực khác nhau của đời sống xã hội.

Bài 2: Thông tin và dữ liệu

BÀI 2: THÔNG TIN VÀ DỮ LIỆU

1. Khái niệm về thông tin và dữ liệu

 a. Thông tin

- Những hiểu biết có được về một thực thể nào đó được gọi là thông tin về thực thể đó.

- VD: Bình cao 1.5m, nặng 50kg, học giỏi, chăm ngoan, cần cù, ...

 b. Dữ liệu

- Là những thông tin đã được đưa vào máy tính.

2. Đơn vị đo lượng thông tin

- Bit là đơn vị nhỏ nhất để đo lượng thông tin, sử dụng hai ký hiệu là 0 và 1 để biểu diễn thông tin trong máy tính.

- Các đơn vị khác để đo thông tin:

• 1 Byte (1B) = 8 Bit
• 1 KB (Kilôbyte) = 1024B
• 1 MB (Mêgabyte) = 1024KB
• 1 GB (Gigabyte) = 1024MB
• 1 TB (Têgabyte) = 1024GB
• 1 PB (Pêtabyte) = 1024TB

3. Các dạng thông tin

- Có thể phân loại thông tin thành hai loại: 

• Số: số nguyên, số thực,…
• Phi số: có ba dạng: 
  • Văn bản: báo, sách, vở, …
  • Âm thanh: tiếng nói con người, tiếng nhạc, …
  • Hình ảnh: tranh vẽ, ảnh chụp, bản đồ,…

4. Mã hóa thông tin trên máy tính

- Để máy tính xử lý được, thông tin cần phải được biến đổi thành dãy bit. Cách biến đổi như vậy gọi là mã hoá thông tin.

- Để mã hoá văn bản dùng mã ASCII (8 bit) gồm 256 ký tự được đánh số từ 0-255, số hiệu này được gọi là mã ASCII thập phân của ký tự.

- Bộ mã Unicode (16 bit) có thể mã hóa 65536 ký tự khác nhau, cho phép thể hiện trong máy tính văn bản của tất cả các ngôn ngữ trên thế giới.

5. Biểu diễn thông tin trong máy tính

 a. Thông tin loại số

* Hệ đếm:

- Bất kỳ số tự nhiên b nào lớn hơn 1 đều có thể chọn làm cơ số cho hệ đếm. Số lượng các ký hiệu được sử dụng bằng cơ số của hệ đếm đó.

- Quy tắc: giá trị của mỗi ký hiệu ở hàng bất kỳ có giá trị bằng “số hệ đếm” đơn vị của hàng kế cận bên phải.

* Hệ thập phân: là hệ dùng các số 0, 1,…,9 để biểu diễn. VD: 536,4 = 5 x 10² + 3 x 10¹ + 6 x 10⁰ + 4 x 10^-1

- Các hệ đếm dùng trong tin học:

• Hệ nhị phân: là hệ chỉ dùng 2 số 0 và 1 để biểu diễn. Vd: 1102 = 1 x 2² + 1 x 2¹ + 0 x 2⁰ = 6₁₀
• Hệ cơ số 16: là hệ dùng các ký hiệu 0, 1,…,9 và A, B, C, D, E, F để biểu diễn. Trong đó: A = 10, B = 11, C = 12, D = 13, E = 14, F = 15.

Vd: A0116 = 10 x 16² + 0 x 16¹ + 1 x 16⁰ = 2561₁₀

* Biểu diễn số nguyên:

- Số nguyên có dấu: bit cao nhất xác định số nguyên đó là âm (1) hay dương (0).

- Một byte biểu diễn được số nguyên trong phạm vi -127 đến 127.

- Số nguyên không âm: toàn bộ 8 bit được dùng để biểu diễn giá trị số, phạm vi từ 0 đến 256.

	bit 7	bit 6	bit 5	bit 4	bit 3	bit 2	bit 1	bit 0
	các bit cao				các bit thấp

* Biểu diễn số thực: Mọi số thực có thể biểu diễn được dưới dạng:  (được gọi là dấu phẩy động). Trong đó:

• M : phần định trị             
• K : phần bậc

Ví dụ: 12,345 = 0,12345 x 10²

b. Thông tin loại phi số:

- Văn bản : để biểu diễn một xâu ký tự máy tính có thể dùng một dãy byte, mỗi byte biễu diễn một ký tự theo thứ tự từ trái sang phải. VD: biểu diễn xâu ký tự “TIN” : 01010100 01001001 01001110

- Các dạng khác: (hình ảnh, âm thanh,…) ta cũng phải mã hóa chúng thành dãy bit.

* Nguyên lí mã hóa nhị phân:

- Thông tin có nhiều dạng khác nhau như số, văn bản, hình ảnh, âm thanh… Khi đưa vào máy tính, chúng đều được biến đổi thành dạng chung – dãy bit. Dãy bit đó là mã nhị phân của thông tin mà nó biểu diễn.

Bài 3: Giới thiệu về máy tính

BÀI 3: GIỚI THIỆU VỀ MÁY TÍNH

1. Khái niệm về hệ thống tin học

 - Hệ thống tin học dùng để nhập, xử lí, xuất, truyền và lưu trữ thông tin.

 - Hệ thống tin học gồm 3 phần:

• Phần cứng (Hardware)
• Phần mềm (Software)
• Sự quản lí và điều khiển của con người. Đây là yếu tố quan trọng nhất.

2. Sơ đồ cấu trúc của một máy tính

- Máy tính là thiết bị dùng để tự động hóa quá trình thu thập, lưu trữ và xử lý thông tin. 

- Máy tính gồm các bộ phận chính sau:

• Bộ xử lý trung tâm (CPU –Central Procesing Unit).
• Bộ nhớ trong (Main Memory).
• Bộ nhớ ngoài (Sencondary Memory).
• Thiết bị vào (Input Device)
• Thiết bị ra (Output Device)

Sơ đồ cấu trúc máy tính:

a. Bộ xử lý trung tâm (CPU)

- CPU là thành phần quan trọng nhất của máy tính, đó là thiết bị chính thực hiện và điều khiển việc thực hiện chương trình.

- CPU gồm hai bộ phận chính:

• Bộ điều khiển (CU – control Unit): điều khiển các bộ phận thực hiện chương trình.
• Bộ số học/lôgic (ALU – Arithmetic/Logic Unit): thực hiện các phép toán số học và lôgic.

- Ngoài ra còn có thanh ghi (Register) và bộ nhớ truy cập nhanh (Cache). Tốc độ truy cập đến Cache khá nhanh, chỉ sau tốc độ truy cập thanh ghi. 

b. Bộ nhớ trong (Main memory)

- Bộ nhớ trong còn có tên là bộ nhớ chính.
- Bộ nhớ trong là nơi chương trình được đưa vào để thực hiện và là nơi lưu trữ dữ liệu đang được xử lý.
- Bộ nhớ trong gồm 2 thành phần:

• ROM (read only memory): chứa một số chương trình hệ thống được hãng sản xuất nạp sẵn.
  • Chương trình trong ROM ktra các thiết bị và tạo sự giao tiếp ban đầu với các chương trình.
  • Dữ liệu trong ROM không xóa được và cũng không bị mất đi.

• RAM (random access memory): là phần bộ nhớ có thể đọc và ghi dữ liệu trong lúc làm việc. Khi tắt máy dữ kiệu trong RAM sẽ bị mất đi.

- Các địa chỉ trong máy được ghi trong hệ Hexa, mỗi ô nhớ có dung lượng 1 byte. 

c. Bộ nhớ ngoài (Secondary Memory)

- Dùng để lưu trữ lâu dài dữ liệu và hỗ trợ cho bộ nhớ trong.

- Bộ nhớ ngoài thường là đĩa cứng, đĩa mềm, đĩa CD, thiết bị nhớ flash.

d. Thiết bị vào (Input device)

- Thiết bị vào dùng để đưa thông tin vào máy tính.

- Có nhiều loại thiết bị vào như:

• Bàn phím (keyboard)
• Chuột (mouse)
• Máy quét (scanner)
• Micro
• Webcam (là một camera kĩ thuật số)

e. Thiết bị ra (Output device)

- Thiết bị ra dùng để đưa dữ liệu ra từ máy tính.

- Có nhiều loại thiết bị ra như:

• Màn hình (monitor)
• Máy in (printer)
• Máy chiếu (projector)
• Loa và tai nghe (speaker and headphone)
• Modem (thiết bị vào/ra): Là thiết bị dùng để truyền thông giữa các hệ thống máy tính thông qua đường truyền.

3. Hoạt động của máy tính

* Nguyên lý điều khiển bằng chương trình:

- Máy tính hoạt động theo chương trình.

- Tại mỗi thời điểm máy chỉ thực hiện 1 lệnh, nó thực hiện rất nhanh.

* Nguyên lý lưu trữ chương trình: 
Lệnh được đưa vào máy tính dưới dạng mã nhị phân để lưu trữ, xử lý như những dữ liệu khác.

* Nguyên lý truy cập theo địa chỉ: 
Việc truy cập dữ liệu trong máy tính được thực hiện thông qua địa chỉ nơi lưu trữ dữ liệu đó.

* Nguyên lý Phôn Nôi-man:
Mã hóa nhị phân, điều khiển bằng chương trình, lưu trữ chương trình và truy cập theo địa chỉ tạo thành một nguyên lý chung gọi là nguyên lý Phôn Nôi-man.

Bài 4: Bài toán và thuật toán

BÀI 4. BÀI TOÁN VÀ THUẬT TOÁN

1. Khái niệm bài toán

- Bài toán là một việc nào đó ta muốn máy tính thực hiện. Ví dụ: Giải phương trình bậc 2, quản lý nhân viên…

- Các bài toán được cấu tạo bởi 2 thành phần cơ bản:

• Input: các thông tin đã có.
• Output: Các thông tin cần tìm từ Output.

2. Khái niệm thuật toán

- Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo 1 trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận ra Output cần tìm.

- Ví dụ: Tìm giá trị lớn nhất của 1 dãy số nguyên.

=> Ta có 3 bước thực hiện như sau:

* Xác định BT
- Input: Số nguyên dương N và dãy N số nguyên a1, a2, …, aN.
- Output: Giá trị lớn nhất Max của dãy số.
* Ý tưởng
- Khởi tạo giá trị Max = a1.
- Lần lượt với i từ 2 đến N so sánh ai với Max, nếu ai>Max thì Max= ai.
* Thuật toán:
Cách liệt kê:

• B1: Nhập N và dãy a1,...,aN;
• B2: Max \(\leftarrow\) a1, i \(\leftarrow\) 2;
• B3: nếu i>N thì đưa giá trị Max rồi kết thúc;
• B4: Nếu ai>Max thì Max \(\leftarrow\) ai;
• B5: i \(\leftarrow\) i+1 rồi quay lại bước 3;

Cách lập sơ đồ khối:
- Thuật toán còn được diễn tả bằng sơ đồ khối.
- Quy định:

• Hình ô van: các thao tác nhập, xuất dữ liệu.
• Hình thoi: Thao tác so sánh.
• Hình chữ nhật: Các phép toán.
• Mũi tên: trình tự thực hiện các thao tác.

Ví dụ: Mô phỏng việc thực hiện thuật toán với N=8 và dãy số: 5, 1, 4, 7, 6, 3, 15, 11

Ds	5	1	4	7	6	3	15	11
i	2	3	4	5	6	7	8	9
Max	5	5	5	7	7	7	15	15

=> Các tính chất của thuật toán:

• Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác.
• Tính xác định: Sau một số lần thực hiện thao tác, hoặc là kết thúc hoặc xác định để thực hiện bước tiếp theo.
• Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm.

3. Một số ví dụ về thuật toán

Ví dụ 1: Kiểm tra tính nguyên tố của một số nguyên dương.

- Xác định bài toán:

• Input: Số nguyên dương N.
• Output: “N là số nguyên tố” hoặc “N không là số nguyên tố”.

- Ý tưởng: Ta nhớ lại định nghĩa: Một số nguyên dương N là số nguyên tố nếu nó có đúng 2 ước số khác nhau là 1 và chính nó. Do đó ta có:

• Nếu N = 1 thì N không là nguyên tố.
• Nếu 1 < N < 4 thì N là số nguyên tố.
• Nếu N \(\ge\) 4 và không có ước số trong phạm vi từ 2 đến phần nguyên căn bậc 2 của N thì N là số nguyên tố.

- Thuật toán:

• B1: Nhập số nguyên dương N.
• B2: Nếu N = 1 thì thông báo N không là số nguyên tố rồi kết thúc.
• B3: Nếu N < 4 thì thông báo N là số nguyên tố rồi kết thúc.
• B4: i \(\leftarrow\) 2
• B5: Nếu N>[\(\sqrt{N}\)](*) thì thông báo N là số nguyên tố rồi kết thúc.
• B6: Nếu N chia hết cho i thì thông báo N là số không nguyên tố rồi kết thúc.
• B7: i \(\leftarrow\) i + 1 rồi quay lại bước 5.

Ví dụ 2: Bài toán sắp xếp

Cho dãy A gồm N số nguyên a1, a2, a3, …,aN. Cần sắp xếp các số hạng để dãy A trở thành dãy không giảm (tức là số hạng trước không lớn hơn số hạng sau)

- Xác định bài toán:

• Input: Dãy A gồm N số nguyên
• Output: Dãy A được sắp xếp thành dãy không giảm.

Thuật toán sắp xếp bằng tráo đổi (Exchange Sort)

- Ý tưởng: Với 2 số liền kề, nếu số trước lớn hơn số sau ta đổi chổ cho nhau. Việc đó lặp lai, khi không còn sự đổi chổ nào nữa.

- Thuật toán
Cách liệt kê:

• B1: Nhập vào n và dãy số nguyên a1, . . . ,aN;
• B2: M \(\leftarrow\) N;
• B3: Nếu M<2 thì in dãy đã sắp xếp rồi kết thúc;
• B4. M \(\leftarrow\) M – 1; i \(\leftarrow\) 0;
• B5: i \(\leftarrow\) i + 1;
• B6: Nếu i > M thì quay lại bước 3;
• B7. Nếu ai > ai+1 thì tráo đổi cho nhau;
• B8: Quay lại bước 5; 

Ví dụ 3: Bài toán tìm kiếm

Cho dãy A gồm N số nguyên khác nhau: a1…aN. và một số nguyên k. Cần biết có hay không chỉ số i mà ai=k. Nếu có hãy cho biết chỉ số đó.
Thuật toán tìm kiếm tuần tự:
- Xác định bài toán

• Input: dãy A gồm N số nguyên khác nhau: a1…aN và số nguyên k.
• Output: chỉ số i mà ai=k hoặc thông báo không có số hạng nào của dãy A có giá trị là k.

- Ý tưởng: lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá cho đến khi hoặc gặp một số hạng bằng khoá hoặc dãy đã được xét hết và không có giá trị nào bằng khoá. Trong trường hợp thứ 2 dãy A không có số hạng nào bằng khoá...
- Thuật toán
Liệt kê:

• B1: Nhập vào N, các số hạng a1, . . . ,aN và khóa k;
• B2: i\(\leftarrow\)1;
• B3: Nếu ai=k thì thông báo chỉ số i rồi kết thúc;
• B4. i \(\leftarrow\)i+1;
• B5: Nếu i>N thì thông báo dãy A không có số hạng nào có giá trị bằng k rồi kết thúc;
• B6: Quay lại bước 3;

Dãy A có N = 7 khóa k = 10

Tìm chỉ số i để ai = k.

i	1	2	3	4	5	6	7
ai	7	12	4	6	11	10	8

Ghi chú: k = 10 → i = 6

Trong thuật toán trên, i là biến chỉ số và nhận giá trị nguyên lần lượt từ 1 đến N + 1