1.1.1 Chuyển đổi cơ số
- Chuyển số nhị phân và hệ cơ số 16 thành số thập phân
- Chuyển các số nguyên thập phân thành các số nhị phân, 16
Để chuyển từ hệ thập phân sang nhị phân ta chia số đó cho 2 lấy phần dư.
Tương tự muốn chuyển từ hệ thập phân sang hệ 16 ta chia số đó cho 16 lấy phần dư.
Khi chuyển số hữu tỷ thập phân sang nhị phân ta dùng cách nhân số đó với 2 và lấy phần nguyên. Thuật toán kết thúc khi giá trị cuối bằng 1. Làm tương tự đối với hê cơ số 16.
- Chuyển đổi giữa hệ 16 và hệ nhị phân
Từ hệ nhị phân sang hệ 16, ta nhóm các bit từ phải qua trái, mỗi nhóm gồm 4 bit, nếu nhóm cuối cùng không đủ thì thêm số 0 và chuyển nhóm 4 bit đó sang hệ 16.
Từ hệ 16 sang hệ nhị phân thì ta chuyển từng chữ số sang hệ nhị phân
Ví dụ:
10110111100100 = (0010) (1101) (1110) (0100) = 2 D E 4
1.1.2 Các biểu diễn số
- Số thập phân được biểu diễn dạng gói đóng hoặc dạng vùng.
- Số nhị phân được biểu diễn dạng dấu phảy tĩnh hoặc dấu phảy động.
- Dạng gói đóng mỗi chữ số được biểu diễn bằng 8 bit và 4 bit cao nhất của chỉ giá trị của chữ số. Ví du: 12 --> 0011 0001 1100 0010 . Chú ý 1100 biểu diễn dấu dương hoặc lớn hơn bằng 0.
- Dạng vùng thì khác biệt dạng gói đóng là dấu của cả số chỉ được biểu diễn ở 4 bit cuối cùng. Ví dụ: -12 --> 0000 0001 0010 1101 . Chú ý vì máy tính sử dụng đơn vị byte nên cần bổ sung thêm 0000 vào đầu để đủ 2 byte.
- Dấu phảy tĩnh: Bit để biểu diễn dấu là bit đầu tiên 1: số âm, 0: số dương hoặc 0. Sử dụng phương pháp "bù 2" để biểu diễn số âm.
- Dấu phảy động: Được biểu diễn dưới dạng số mũ sử dụng số nhị phân có chiều dài cố định. Ví du: Bit đầu xác định dấu, 8 bit sau xác định số mũ e , 24 bit cuối định trị.
DỊCH SỐ HỌC
Một phép dịch số học dược sư dụng khi dữ lieuj là dữ liệu số có dấu dương hoặc âm. Phép dịch sử dụng phép toán dịch chuỗi bit, trừ bit dấu, dùng cho số dạng dấu phảy cố định.
- Phép dịch số học sang trái, giữ nguyên vị trí bit dấu và chèn 1 số "0" vào vị trí ngoài cùng bên phải (vị trí bị rỗng khi dịch chuyển). Tổng quát phép dịch số học sang trái n bit tăng số đó lên 2^n lần.
- Phép dịch số học sang phải, giữ nguyên bit dấu ở đầu và chèn bi dấu vào vị trí bị rỗng kh dịch chuyển. Tổng quát phép dịch số học sang phải n bit giảm số đó 2^n lần.
Dịch trái 1 bit: 11111010 --> 11110100
Dịch phải 1 bit: 11111010 --> 11111101
DỊCH LOGIC
Không giống như dịch số học, phép dịch logic không quan tâm dữ liệu là dạng số hay không, nó chỉ coi dữ liệu là 1 chuỗi bit. Nó dịch toàn bộ chuỗi bit dữ liệu và chèn 0 vào vị trí bị bỏ trống do dịch cho cả 2 trường hợp dịch trái và dịch phải.
Ví dụ:
Dịch trái 1 bit: 11110010 --> 11100100
Dịch phải 1 bit: 11110010 --> 01111001
SAI SỐ
Do máy tính không thể xử lý số thập phân vô hạn, các bit nhỏ hơn bit xác định độ dài chính xác đều bị cắt bỏ, làm tròn lên hoặc làm tròn xuống tới giá trị giới hạn của số chữ số có nghĩa.
Triệt tiêu các chữ số có nghĩa
Xảy ra khi 2 số xấp xỉ nhau trừ cho nhau.
Ví dụ:
356,3622 - 356,356,3579 = 0.0043
Khi giá trị làm tròn về 0 thì số chữ số có nghĩa suy giảm trầm trọng.
Mất các chữ số đuôi
Xảy ra khi số rất lớn cộng số rất nhỏ hoặc một số trừ đi một số khác.
Ví dụ:
356.3622 - 0.000015 = 356.3622
Do số trừ quá nhỏ nên khi làm tròn thì kết quả vẫn như trước.
CÂU HỎI NHANH
Câu 1: Dịch phải 3 bit số nhị phân 11001100 theo 2 cách số học và logic
Trả lời:
Số học: 111111001
Logic: 00011001
Câu 2: Giải thích khái niệm "triệt tiêu các chữ số có nghĩa" Và "mất các chữ số đuôi"
Trả lời:
Triệt tiêu các chữ số có nghĩa là hiện tượng xảy ra khi số chữ số có nghĩa giảm trầm trọng khi 1 số trừ đi 1 số khác gần bằng nó, hoặc khi cộng 1 số dương với 1 số âm có giá rtij tuyệt đối gần bằng.
Mất chữ số đuôi là hiện tượng khi phần thông tin trong những bit thấp, không được chứa trong vùng biểu diễn, có hể bị mất do giới hạn độ dài của số, khi 1 số rất lớn cộng một số rất nhỏ hoặc 1 số trừ đi một số khác.
1.2 Thông tin và logic
1.2.1 Các phép toán logic
- Nhân Logic (AND): A.B : Kết quả là 1 khi cả hai bit là 1
- Cộng Logic (OR): A+B: Kết quả là 1 khi ít nhất 1 bit là 1
- Phủ định Logic (NOT) : -A: Đảo bit từ 0 -> 1 và từ 1-> 0
- Loại trừ logic (XOR, EOR): A (+) B: Kết quả bằng 0 nếu 2 bit giống nhau và bằng 1 khi 2 bit khác nhau.
-(A.B) = -A + -B
-(A+B) = -A . -B
KÝ PHÁP BALAN NGƯỢC
Là phương pháp biểu diễn các công thức toán học được sử dụng hàng ngày sang dạng biểu diễn dễ xử lý hơn bởi máy tính.
Ví dụ: a+ b --> ab+
(a+b)*c -->
Đặt a+b--> ab+ --> R
R*c --> Rc* -->cR* -->cab+*
CÂU HỎI NHANH
Câu 1: Giải thích khái niệm "bộ cộng", "bộ bán cộng", "bộ cộng đầy đủ"
Trả lời:
Bộ cộng: các số nhị phân 1 bit gồm mạch AND OR NOT
Bộ bán cộng: Một bộ cộng mà không đưa vào kết quả số nhớ từ các bit thấp hơn Nó có 2 đầu vào và 2 đầu ra
Bộ cộng đầy đủ: Một bộ cộng mà đưa ra kết quả số nhớ từ các bit thấp hơn . Có 3 đầu vào và 2 đầu ra.
Câu 2: Chuyển công hức "(a+b) x (c-d)" sang dạng kí pháp Balan ngược
Trả lời:
a+b --> ab+ --> R
c-d --> cd- --> Q
RxQ --> RQx --> ab+cd-x
1.3 Cấu trúc dữ liệu
1.3.1 Các mảng (Array)
Mảng là một cấu trúc dữ liệu tạo bởi nhiều dữ liệu cùng kiểu, được truy cập qua chỉ số.
1.3.2 Danh sách (List)
Tương tự như mảng List dùng để lưu dữ liệu cùng kiểu, giống nhau hoặc tương tự nhau và được đặt cùng trên một hàng một cách tuyến tính. Đối với mảng thì các phần tử đặt kề nhau một cách vật lú còn trong list các phần tử có thể đặt ở những chỗ độc lập và có các con trỏ liên kết giữa chúng. Vì thế ưu điểm List rất dễ để thêm, bớt phần tử, tuy nhiên nhược điểm là việc truy xuất dữ liệu. Còn mảng thì việc thêm, xóa dữ liệu khá phức tạp nhưng vì là truy xuất dữ liệu bằng chỉ số nên nhanh hơn List rất nhiều.
1.3.3 Ngăn xếp
1.3.4 Hàng đợi
1.3.5 Cây
Cây bao gồm 1 gốc ở trên cùng và các nút được liên kết bằng cành. Nút ngay trên một nút gọi là cha, nút ngay dưới 1 nút khác gọi là con.
Cây nhị phân: là cây mà mỗi nút có không quá 2 con.
Cây nhị phân hoàn chỉnh: là cây có các lá có cùng đọ sâu hoặc 2 lá bất kì có độ sâu chênh lệch nhỏ hơn hoặc bằng một.
Cây nhị phân tìm kiếm: là cây nhị phân mà giá trị của 1 phần tử được gán cho mỗi nút thỏa mãn các ràng buộc: giá trị con trái < giá trị phần tử cha < giá trị con phải.
Đống: là cây nhị phân thỏa mãn điều kiện (giá trị cha > giá trị nút con, hoặc giá trị nút cha < giá trị nút con).
1.3.6. Băm (Hash)
1.4 Giải thuật
1.4.1 Các giải thuật tìm kiếm
- Tìm kiếm tuyến tính
- Tìm kiếm nhị phân
- Sắp xếp nổi bọt
5 4 3 2 1
Lần 1:
5 <=> 4 3 2 1 Đổi chỗ 5 và 4
4 5 <=> 3 2 1 Đổi chỗ 5 và 3
4 3 5 <=> 2 1 Đổi chỗ 5 và 2
4 3 2 5 <=> 1 Đổi chỗ 5 và 1
4 3 2 1 5 Giá trị lớn nhất nằm cuối
Lần 2:
4 <=> 3 2 1 | 5 Đổi chỗ 4 và 3
3 4 <=> 2 1 | 5 Đổi chỗ 4 và 2
3 2 4 <=> 1 | 5 Đổi chỗ 4 và 1
3 2 1 4 | 5 Giá trị lớn thứ 2 nằm thứ 2 từ bên phải
Lần 3:
3 <=> 2 1| 4 5 Đổi chỗ 3 và 2
2 3 <=> 1| 4 5 Đổi chỗ 3 và 1
2 1 3 4 5
Lần 4:
2 <=> 1| 3 4 5 Đổi chỗ 2 và 1
1 2 | 3 4 5
Trong sắp xếp nổi bọt, mỗi cặp phần tử liền nhau được so sánh tuần tự và đổi chỗ nếu cần thiết. Trong trường hợp sắp xếp theo thứ tự tăng dần, gía trị lớn nhất được đặt là phần tử cuối cùng của mảng. Tiếp theo, trở lại từ đầu, các giá trị được kiểm tra và thay thay đổi khi cần thiết. Tron lần chạy thứu hai, phần tử ở vị trí cuối cùng của mảng đặt ra ngoài khoảng sắp xếp. Tiếp tục quá trình này, khoảng sắp xếp nhỏ dần sau mỗi lần, và kết thúc sắp xếp khi phần tử đầu tiên và phần tử thứ hai được so sánh.
- Sắp xếp chọn:
- Sắp xếp chèn
- Sắp xếp nhanh
- Săp xếp trộn
- Sắp xếp Shell
- Sắp xếp vun đống
