Khái niệm độ phức tạp, thông tin và entropy

03:51' CH - Chủ nhật, 04/05/2003

Khái niệm độ phức tạp gắn với khái niệm thông tin.

Ban đầu khái niệm thông tin do Shanon đưa ra năm 1948 dựa trên cơ sở xác suất thống kê, khái niệm thông tin tuyệt đối do Kolmogorov đưa ra năm 1973 dựa trên cơ sở thuật toán. Thông tin được hiểu như một đại lượng căn bản định nghĩa một cách nghiêm ngặt có thể đo lường được của sự vật giống như năng lượng. Thông tin tuyệt đối chứa trong một đối tượng hữu hạn chính là độ phức tạp Kolmogorov (Kolmogorov complexity) của đối tượng đó. Độ phức tạp của một đối tượng hữu hạn x là độ dài ngắn nhất của mô tả hữu hiệu của x, hay độ dài ngắn nhất của chương trình (và số liệu ban đầu), tính bằng x chẳng hạn, sinh ra x. Cho trước x và nếu tìm ra mô hình hay chương trình mô tả x có độ dài bằng độ phức tạp Kolmogorov của x thì đó chính là mô tả ngắn nhất không thể gọn hơn. Ta có sự nén dữ liệu hoàn hảo nhất, nén quá mức đó là không thể. Cái mà không còn có thể nén được nữa là cái hoàn toàn ngẫu nhiên. Như vậy tính ngẫu nhiên của sự vật cũng có thể định nghĩa nghiêm ngặt (thoả mãn các phép thử Martin-LÁ¶f). Thông tin, tính ngẫu nhiên, nén dữ liệu là những khái niệm quá quen thuộc với chúng ta.

Cái làm cho một hệ thống xuất hiện tính trồi (không thể suy ra từ tính chất của các thành phần) với những mẫu hình mới (pattern), các tính chất mới, tạo nên sự tổ chức, sự đa dạng, phức tạp và sự sống là do kết hợp mang tính phi tuyến của các hệ thống con thành phần.

Khái niệm và thuật ngữ thông tin được dùng trong giao tiếp giữa các hệ thống máy tự động, sinh vật, môi trường... Thông tin có được qua tương tác vật chất lý-hoá qua vỏ vật chất của vật mang tin.

Khái niệm lượng thông tin được Shannon (nhà toán học, vật lý) đưa ra năm 1948 thông qua khái niệm trung gian là “độ bất định” trong dự đoán khả năng xảy ra trước khi nhận được thông tin. Sau khi nhận được thông tin, nếu độ bất định đó giảm đi thì có thể coi lượng thông tin nhận được là bằng mức độ giảm đi của độ bất định. Nếu dự đoán càng nhiều tình huống có thể xảy ra thì độ bất định trong dự báo càng lớn. Nếu N là số lượng tình huống có thể xảy ra thì độ bất định là logNN. Đơn vị đo độ bất định là N=2; gọi là bit.

Năm 1948, Shannon đưa ra công thức tính độ bất định có tính khái quát hơn. Trong N tình huống dự đoán có thể xảy ra, không nhất thiết tất cả N tình huống đó đều có khả năng xảy ra như nhau. Do vậy có tính tới các xác suất khác nhau của dự báo.

Công thức đo lượng thông tin hay độ bất định trước khi nhận được thông tin của Shannon trùng hoàn toàn với công thức đo entropi trong nhiệt động học do nhà toán học Boltzmann người Áo đưa ra.
Theo nguyên lý thứ 2 nhiệt động học thì hệ đóng kín, không có trao đổi năng lượng bên ngoài tất yếu sẽ chuyển động đến trạng thái cân bằng tới khi các bộ phận cấu thành của hệ thống đó giống nhau, đồng nhất và mất đi cấu trúc hay là tan vỡ trật tự và trở nên hỗn độn. Entropi là đại lượng đo trạng thái mất cấu trúc, mất trật tự của hệ thống gọi là entropi.

Như vậy có thể hiểu entropi chính là độ đo sự bất định trong cấu trúc của hệ thống, và sự bất định trong cấu trúc đó càng nhiều thì sự bất định trong tình huống có thể xảy ra như trong định nghĩa của Shanon.Vì thế người ta đã đưa ra khái niệm Thông tin cấu trúc là để chỉ lượng thông tin chứa trong 1 hệ thống bất kỳ: entropi của hệ thống đó càng lớn thì độ bất định của nó cũng càng lớn và như vậy lượng thông tin cấu trúc mà hệ thống đó chứa đựng sẽ càng lớn và ngược lại. Để dễ phân biệt gọi lượng thông tin theo Shannon là Thông tin tương đối vì lượng thông tin này là sự bất định tương đối của nơi nhận khi dự báo về khả năng của nơi gửi. Lượng thông tin cấu trúc có thể đo bằng nghịch đảo của entropi.

Tính biến đổi một chiều của entropi
Bất kỳ một hệ thống vật chất nào, nếu không tiếp thu được năng lượng từ môi trường thì chiều biến đổi của nó là tăng liên tục entropi (tức là thông tin cấu trúc giảm dần) cho đến khi trình độ tổ chức, cấu trúc tổ chức của nó suy giảm và tiến tới mất cấu trúc và thành một thứ đồng nhất (homogene) và vô định hình (amorphe), không còn hoặc có rất ít biến đổi, vận động. (có thể tăng không đồng nhất ở tất cả mọi bộ phận con).

Một cơ thể sống là hệ thống vật chất có khả năng tự lấy năng lượng từ bên ngoài để chống lại xu thế tăng entropi của bản thân. Năng lượng lấy thêm vào được các nhà khoa học gọi là negentropi.

Nếu giảm entropi thì tăng cấu trúc tăng sự vận động tức là phát triển đi lên, là tiến bộ trong biến đổi.

Khái niệm độ phức tạp, thông tin và entropy
ChúngTa.com @ Facebook
Thống kê truy cập
Số lượt truy cập: .
Tổng số người truy cập: .
Số người đang trực tuyến: .
.
Sponsor links (Provided by VIEPortal.net - The web cloud services for enterprises)
Thiết kế web, Thiết kế website, Thiết kế website công ty, Dịch vụ thiết kế website, Dịch vụ thiết kế web tối ưu, Giải pháp portal cổng thông tin, Xây dựng website doanh nghiệp, Dịch vụ web bán hàng trực tuyến, Giải pháp thương mại điện tử, Phần mềm dịch vụ web, Phần mềm quản trị tác nghiệp nội bộ công ty,