Tìm hiểu mô hình mạng OSI

Mô hình OSI (OPEN SYSTEMS INTERCONNECTION REFERENCE MODEL, viết ngắn là OSI Model hoặc OSI Reference Model) – tạm dịch là Mô hình tham chiếu kết nối các hệ thống mở – là một thiết kế dựa vào nguyên lý tầng cấp, lý giải một cách trừu tượng kỹ thuật kết nối truyền thông giữa các máy vi tính và thiết kế giao thức mạng giữa chúng. Mô hình này được phát triển thành một phần trong kế hoạch Kết nối các hệ thống mở (Open Systems Interconnection) do ISO và IUT-T khởi xướng. Nó còn được gọi là Mô hình bảy tầng của OSI. (Theo wikipedia)

Chia Subnet kiểu VLSM

Cho sơ đồ mạng như hình vẽ và đĩa chỉ 192.168.10.0/24. Hay chia subnet theo sơ đồ bên dưới . 

PHƯƠNG PHÁP TÍNH SUBNET NHANH NHẤT

IP là gì thì các bạn có thể tìm hiểu tại đây. Mình sẽ không nhắc lại nữa, chỉ hướng đãn cho các bạn biết làm thế nào để chia ip một cách nhanh nhất :)

F  Một địa chỉ IP v.4 có 32 bit, tách thành 2 phần: Network ID và Host ID

-       Network ID: dãy bit dùng “định danh” cho mạng IP (như địa chỉ của 1 con hẻm / ngõ).

-       Host ID: dãy bit dùng “định danh” cho 1 host trong mạng đó (như số  nhà trong hẻm)

F  Trong một Network có n địa chỉ IP (từ 0 đến n-1):

-       Địa chỉ IP đầu tiên được dùng làm “định danh” cho mạng đó.

-       Địa chỉ IP cuối cùng được dùng làm địa chỉ broadcast cho toàn mạng đó.

Hướng dẫn chia địa chỉ mạng con theo phương pháp tối ưu VLSM

Qua quá trình giảng dạy các sinh viên, được biết một số bạn vẫn còn bỡ ngỡ với cách
chia địa chỉ mạng con theo VLSM, phương pháp này sẽ giúp chúng ta kiểm soát được số mạng mới sinh ra, số mạng đã dùng, số mạng dư thừa còn lại, sau đây tôi sẽ hướng dẫn các bạn thực hiện việc này một cách dễ dàng bằng ví dụ minh họa. Trước hết, chúng ta phải hiểu rõ cấu trúc của địa chỉ IP v4 và ý nghĩa của một số khái niệm: ví dụ các lớp địa chỉ IP v4, Net_id, host_id, Subnet Mask, giải địa chỉ khả dụng, địa chỉ mạng, …

Cây tổng quát

Đã rất nhiều lần mình tìm hiểu cách cài đặt và nhập, duyệt của cây tổng quát, tuy nhiên thì chỉ tìm được cách cài đặt theo một số phương pháp chứ chưa thấy code nhập và duyệt cây tổng quát cụ thể…
Có nhiều cách cài và duyệt cây, các bạn có thể tham khảo trên mạng. Bài này mình chỉ đề cập đến 1 phần nhỏ.

Dưới đây là code cài đặt, nhập, và duyệt cây tổng quát theo thứ tự trước, các phép toán khác các bạn tự phát triển hoặc trong một ngày đẹp trời nào đó mình lại viết tiếp 

Một số phép toán trên cây nhị phân tìm kiếm

Cây nhị phân tìm kiếm (CNPTK) là cây nhị phân trong đó tại mỗi nút, khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phải. Dưới đây là một ví dụ về cây nhị phân tìm kiếm:

Nhờ ràng buộc về khóa trên CNPTK, việc tìm kiếm trở nên có định hướng. Hơn nữa, do cấu trúc cây việc tìm kiếm trở nên nhanh đáng kể. Nếu số nút trên cây là N thì chi phí tìm kiếm trung bình chỉ khoảng log2N.

Cấu trúc cây:

1 2 3 4 5 6 7

typedef int item; //kieu item la kieu nguyen struct Node {      item key; //truong key cua du lieu      Node *Left, *Right; //con trai va con phai }; typedef Node *Tree;  //cay

Thuật toán Tìm đường đi ngắn nhất Dijkstra, Floyd

Trong bài viết này chỉ đề cập tới các thuật toán tìm đường đi ngắn nhất Dijkstra và Floyd, một số thuật ngử liên quan mình sẽ không giải thích hay định nghĩa, các bạn tự tìm hiểu trong sách hoặc trên mạng.

Bài toán đường đi ngắn nhất nguồn đơn là bài toán tìm một đường đi giữa hai đỉnh sao cho tổng các trọng số của các cạnh tạo nên đường đi đó là nhỏ nhất. Hay nói một cách toán học là:
Cho đơn đồ thị liên thông, có trọng số G=(V,E). Tìm khoảng cách d(a,b) từ một đỉnh a cho trước đến một đỉnh b bất kỳ của G và tìm đường đi ngắn nhất từ a đếnb.

Như tiêu đề bài viết, chúng ta sẽ tìm hiểu 2 thuật toán để giải quyết (chú ý ta xét trọng số của đồ thị là không âm):

Nguyên tắc để chuyển đổi giữa các hệ cơ số

Nguyên tắc 1 : chuyển từ hệ cơ số thập phân sang một hệ cơ số bất kỳ
Để chuyển từ hệ cơ số bất kỳ sang thập phân, nguyên tắc là cứ chia số đó lấy phần dư rồi tiếp tục chia phần nguyên lấy phần dư tiếp sau đó xếp thứ tự ngược từ dưới lên.

Lấy số 3295 (trong hệ thập phân) làm ví dụ:

3295 chia 2 = 1647.5 (1647 -> Dư 1)
1647 (phần nguyên) chia 2 = 823.5 -> Dư 1
823 chia 2 = 411.5 -> Dư 1
411 chia 2 = 205.5 -> Dư 1
205 chia 2 = 102.5 -> Dư 1
102 chia 2 = 51 -> Dư 0
51 chia 2 = 25.5 -> Dư 1
25 chia 2 = 12.5 -> Dư 1
12 chia 2 = 6 -> Dư 0
6 chia 2 = 3 -> Dư 0
3 chia 2 = 1.5 -> Dư 1
1 chia 2 = 0.5 -> Dư 1 (phần nguyên < 1 thì dừng)

Sắp xếp các số dư từ dưới lên trên ta được: 3295 (demical) = 110011011111 (binary).

Chương trình mô phỏng thuật toán đổi cơ số bằng hình vẽ

Về thuật toán đổi các cơ số các bạn có thể xem trên mạng, tuy nhiên chương trình sau sẽ thực hiện đổi số hệ 10 sang hệ 2, 8, 16 và in ra theo đúng dạng chúng ta vẫn làm.

Các hệ đếm thông dụng

1. Hệ thập phân
Hệ thập phân (hay hệ đếm cơ số 10) là một hệ đếm có 10 ký tự (0,1, 2, 3, 4, 5, 6, 7, 8, 9) dùng chỉ số lượng. Những con số này còn được dùng cùng với dấu phân cách thập phân – để định vị phần thập phân sau hàng đơn vị. Con số còn có thể được dẫn đầu bằng các ký hiệu “+” hay “-” để biểu đạt số dương và số âm.

2. Hệ nhị phân
Hệ nhị phân (hay hệ đếm cơ số 2) là một hệ đếm dùng hai ký tự để biểu đạt một giá trị số, hai ký tự đó là 0 và 1; chúng thường được dùng để biểu đạt hai giá trị hiệu điện thế tương ứng (có hiệu điện thế, hoặc hiệu điện thế cao là 1 và không có, hoặc thấp là 0). Do có ưu điểm tính toán đơn giản, dễ dàng thực hiện về mặt vật lý, chẳng hạn như trên các mạch điện tử, hệ nhị phân trở thành một phần kiến tạo căn bản trong các máy tính đương thời.

Hiển thị số hệ 2, hệ 8, hệ 16 của số thập phân

Để hiển thị số hệ 10 sang các hệ khác, thông thường chúng ta nghĩ đến cách đổi chúng ra các hệ kia bằng thuật toán. Nếu muốn vậy bạn có thể tìm thêm trên Google đã có nhiều bài viết về các thuật toán đó rồi, ở đây mình nêu một số cách mà chúng ta không cần dùng thuật toán mà có thể hiển thị ngay.

Chương trình mô phỏng thuật toán đổi cơ số bằng hình vẽ

Về thuật toán đổi các cơ số các bạn có thể xem trên mạng, tuy nhiên chương trình sau sẽ thực hiện đổi số hệ 10 sang hệ 2, 8, 16 và in ra theo đúng dạng chúng ta vẫn làm.

Thực hiện trên dev-C

Chuyển cây nhị phân sang cây nhị phân tìm kiếm

Cách làm của mình rất đơn giản. Chúng ta chỉ việc duyệt vào lưu lại các phần tử của cây nhị phân ban đầu vào mảng và cuối cùng là chèn các giá trị của mảng vào cây theo cách chèn 1 Node vào cây nhị phâ. Vậy là đã được 1 cây nhị phân tìm kiếm.

Thuật toán Ma phương – Magic square

Trong toán vui, một ma trận kì ảo bậc n (còn gọi là ma phương hay hình vuông ma thuật) là một cách sắp xếp n² số, thường là các số nguyên phân biệt, trong một bảng vuông sao cho tổng n số trên mỗi hàng, cột, và đường chéo đều bằng nha Ma trận kì ảo chuẩn chứa các số nguyên từ 1 đến n².

Tồn tại ma trận kì ảo chuẩn cho mọi bậc n ≥ 1 trừ n = 2. Ma trận kì ảo bậc 1 là trường hợp tầm thường, nó chứa duy nhất 1 ô với giá trị 1. Trường hợp không tầm thường có kích thước nhỏ nhất là ma trận kì ảo bậc 3.

Hằng số là tổng của mỗi hàng, cột, và đường chéo được gọi là hằng số kì ảo. Giá trị này của ma trận kì ảo chuẩn chỉ phụ thuộc vào n và có giá trị

[Thuật toán]Cách tính độ phức tạp thuật toán – Algorithm complexity(Phần 3)

V. GIẢI PHƯƠNG TRÌNH ĐỆ QUY
Phuơng pháp truy hồi:
Dùng đệ quy để thay thế bất kỳ T(m) với m<n vào vế phải của PT cho đến khi m=1.
VD: Giải phương trình đệ quy:

[Thuật toán]Cách tính độ phức tạp thuật toán – Algorithm complexity(Phần 2)

IV. CÁCH TÍNH ĐỘ PHỨC TẠP GIẢI THUẬT
Cách tính độ phức tạp của một giải thuật bất kỳ là một vấn đề không đơn giản. Tuy nhiên ta có thể tuân theo một số nguyên tắc sau:

Quy tắc bỏ hằng số
Nếu đoạn chương trình P có thời gian thực hiện T(n) = O(c1.f(n)) với c1 là một hằng số dương
thì có thể coi đoạn chương trình đó có độ phức tạp tính toán là O(f(n)).

[Thuật toán]Cách tính độ phức tạp thuật toán – Algorithm complexity(Phần 1)

I. SỰ CẦN THIẾT PHẢI PHÂN TÍCH THUẬT TOÁN

Trong khi giải một bài toán chúng ta có thể có một số giải thuật khác nhau, vấn đề là cần phải đánh giá các giải thuật đó để lựa chọn một giải thuật tốt (nhất). Thông thường thì ta sẽ căn cứ vào các tiêu chuẩn sau:

1. Giải thuật đúng đắn.
2. Giải thuật đơn giản.
3. Giải thuật thực hiện nhanh.

Đếm số chữ số 0,1,2,3,…,9 trong dãy số từ 1->n | MDIGITS

Đề bài: http://vn.spoj.com/problems/MDIGITS/

Cho hai số nguyên a, b. Viết tất cả các số nằm giữa a, b; tính cả 2 số này.
Tính xem mỗi chữ số 0, 1, .., 9 mỗi số xuất hiện bao nhiêu lần.
Ví dụ, nếu a = 1024 và b = 1032, dãy sẽ là
1024 1025 1026 1027 1028 1029 1030 1031 1032
và có 10 số 0, 10 số 1, 7 số 2, …

[Thuật toán - Java]Chia tiền lẻ sử dụng Quay lui

Đề bài yêu cầu liệt kê ra các trường hợp có thể khi chia số tiền N ra thành các đồng tiền mệnh giá a[i].

Tổng quan về Quy hoạch động

Phương pháp quy hoạch động dùng để giải bài toán tối ưu có tính chất đệ quy, tức là việc tìm phương án tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu của một số hữu hạn các bài toán con. Đối với nhiều thuật toán đệ quy, nguyên lý chia để trị (devide and conquer) thường đóng vai trò chủ đạo trong việc thiết kế thuật toán. Để giải quyết một bài toán lớn, ta chia nó thành nhiều bài toán con cùng dạng với nó để có thể giải quyết độc lập. Trong phương pháp quy hoạch động, nguyên lý này càng được thể hiện rõ: Khi không biết cần phải giải bài những toán con nào, ta sẽ đi giải quyết tất cả các bài toán con và lưu trữ những lời giải hay đáp số của chúng với mục đích sử dụng lại theo một sự phối hợp nào đó để giải quyết những bài toán tổng quát hơn. Đó chính là điểm khác nhau giữa Quy hoạch động và phép đệ quy và cũng là nội dung Phương pháp quy hoạch động.