Trang chủ > OOP - JAVA > Thuật toán và các ngôn ngữ lập trình (p2)

Thuật toán và các ngôn ngữ lập trình (p2)

1.	Hỏi người sử dụng giá của CPU
2.	Hỏi người sử dụng giá của bảng mạch chủ
…
n-1. 	Tính tổng các giá trị đó
n. 	Hiển thị kết quả cho người sử dụng

Hai trường hợp còn lại dẫn tới các thuật toán phức tạp hơn rất nhiều.

Cần nhớ rằng thuật toán đơn giản trên có một biểu thức khá chung chung. Việc dịch nó sang một ngôn ngữ lập trình cụ thể yêu cầu phải đưa ra rất nhiều quyết định, ví dụ như:
•    Tương tác với người sử dụng nên diễn ra như thế nào: dữ liệu đầu vào được cung cấp như thế nào và kết quả cần được hiển thị ra sao?
•    Thực hiện việc tính tổng như thế nào: giá cả của các thành phần được lưu giữ riêng biệt hay được thêm tăng dần vào kết quả tổng?
•    Xử lý với các dữ liệu đầu vào không đúng như thế nào?
Những quyết định này liên quan đến cái gọi là giao diện giữa người sử dụng và các chương trình ứng dụng (cách mà chương trình giao tiếp với người sử dụng) và cũng liên quan tới cấu trúc của thuật toán về khả năng chịu lỗi và dễ dàng sửa đổi. Ví dụ, thuật toán trên phải kiểm tra xem dữ liệu đầu vào có phải thực sự là các con số hay không. Lập trình viên cũng cần cân nhắc lưu giữ giá của các thành phần phòng trường hợp được yêu cầu liên quan đến dữ liệu đầu ra sau này: bên cạnh tổng số tiền, “báo cáo tính toán” chi tiết được yêu cầu (thể hiện giá của các thành phần hay thậm chí số phần trăm trong tổng giá trị của máy tính).
Phản ứng nhỏ nhất với các dữ liệu đầu vào sai cũng làm thay đổi trật tự các bước trong thuật toán. Bên cạnh trật tự giản đơn của các bước, giải pháp cho bất cứ một vấn đề nào thường yêu cầu một số điều sau:
•    Kiểm tra một điều kiện và dựa trên việc đưa ra quyết định kèm theo có liên quan đến các bước tiếp theo của thuật toán
•    Việc thực hiện lặp đi lặp lại các chỉ dẫn cụ thể (theo số lần cho sẵn hoặc cho đến khi điều kiện đó được hoàn thành).
Sau khi đã tính đến khả năng lỗi trong dữ liệu đầu vào và yêu cầu phải lưu giữ các giá thành phần, thuật toán để tính giá trị một chiếc máy vi tính có dạng như sau:

1. Hỏi người sử dụng giá của CPU.
2. Nếu giá trị đưa ra không phải một con số, báo cho người sử dụng biết lỗi và quay lại bước 1.
3. Lưu giá của CPU đã đưa ra (cho việc sử dụng sau này)
4. Hỏi người sử dụng giá của bảng mạch chủ.
5. Nếu giá đưa ra không phải một con số, báo cho nguời sử dụng biết về lỗi và quay lại bước 4.
6. Lưu giá của bảng mạch chủ đã đưa ra (để có thể sử dụng sau này)
…  những thành phần khác
…  những thành phần khác
n-1. Tính tổng giá của các thành phần khác
n.   Hiển thị kết quả

Trong biểu đồ, các quyết định được biểu diễn bằng hình thoi.

Ví dụ: biểu đồ phát triển của thuật toán tính thuế.
Thuat toan - Tinh thue

Các thuật toán thường được viết ở dạng giải mã – xét ở góc độ nào đó, là dạng được nghi thức hóa của ngôn ngữ thông thường, không phụ thuộc vào bất cứ ngôn ngữ lập trình nào. Giải mã gần giống với ngôn ngữ lập trình hơn ngôn ngữ thông thường và dễ dàng đưa vào chương tình được viết bằng môt ngôn ngữ lập trình hạn định. Vô số sách hướng dẫn về lập trình đưa ra các dạng khác nhau của giải mã. Người ta có thể dễ dàng đưa ra bản giải mã của riêng mình.
Giải mã sử dụng các biến số – cách thể hiện bằng ký hiệu của dữ liệu (Bài tiếp theo sẽ giải thích thêm về biến thể; hiện tại cứ xem chúng như các biến thể trong công thức toán học).
Thao tác trên các biến thể được mã hoá với sự trợ giúp của các toán tử – các ký hiệu của thao tác toán học: cộng, trừ, nhân, chia…(bài tiếp theo sẽ trình bày nhiều hơn về vấn đề này). Giải mã cũng sử dụng các từ và biểu thức một cách chính xác để định nghĩa các đoạn của thuật toán (hành động, chỉ dẫn). Ví dụ: đưa ra quyết định có thể được viết như sau:

if (điều kiện) then …

 

hoặc

if (điều kiện) then …
else …


Và các vòng lặp (nói cách khác là thực hiện lặp đi lặp lại của các đoạn của thuật toán)

execute until (điều kiện) …

 

execute modifying value of the variable i from p to l


Trong khi đó dữ liệu đầu vào và đầu ra có thể được biểu diễn bằng từ như: read và write.

Chúng ta có thể sử dụng các ký hiệu +, -, * để thể hiện các thao tác của việc thêm, bớt, nhân; dấu ngoặc đơn để thể hiện thao tác nhóm và các từ đặc biệt để thể hiện hành động và quyết định. Thuật toán để tính thuế có thể được viết như sau:

read income
if (income > 74048) then  tax = 17048.44 + 0.4 * (income - 74048)
else if (income > 37024) then
       tax = 6541.24 + 0.3 * (income - 37024)
else  tax = 0.19 * income - 493.32
write tax


Những khái niệm trong thuật toán này đã thể hiện được hai vấn đề:

Một, lỗi trong dữ liệu đầu vào thay đổi trật tự các bước tiến hành bởi thuật toán và đưa trở về đọc lại chỉ dẫn dữ liệu đầu vào. Trong giải mã hành động đó được mô tả là đi đến một đoạn cụ thể nào đó trong thuật toán (lệnh go to…), thể hiện bằng một nhãn (nhãn là các từ kết thúc bằng dấu ‘:’). Dấu giải mã là {, }, dùng để nhóm các hành động. Ví dụ:

if (điều kiện) then {
hành động 1
hành động 2
}

Nếu điều kiện được thoả mãn, thì hành động trong dấu ngoặc được thực hiện.

dataInput1:
  write "Give the price of the CPU"
  read CPUprice
  if (CPUprice is not a number) then {
      write "Wrong data"
      go to dataInput1
  }
dataInput2:
  write "Give the price of the motherboard"
  read MBprice
  if (MBprice  is not a number) then {
      write "Wrong data"
      go to dataInput2
  }
...
result = sum of prices
write result 


Tuy nhiên những thuật toán như thế (và chương trình) rất khó đọc, logic phức tạp và dễ mắc lỗi.
Đó là lý do tại sao hầu hết các ngôn ngữ lập trình không sử dụng lệnh go to nữa. Thay vào đó người ta sử dụng các vòng lặp. Thuật toán tính giá trị của máy vi tính cần được thể hiện ở một dạng khác. Vòng lặp được sử dụng và giới thiệu biến kiểu boolean được gọi là dataRequired (dữ liệu yêu cầu) với hai giá trị có thể xảy ra: có, yes và không, no.

dataRequired = yes
  execute until (dataRequired) {
     write "Give the price of the CPU"
     read CPUprice
     if (CPUprice is not a number) then write "Wrong data"
     else dataRequired = no
  }
  
dataRequired = yes
  execute until (dataRequired) {
     write "Give the price of the motherboard"
     read MBprice
     if (MBprice is not a number) then write "Wrong data"
     else dataRequired = no
  }
...
result = sum of prices
write result


Ngay từ đầu, giá trị của các biến thể dữ liệu yêu cầu là có và điều kiện là thực hiện cho đến khi hoàn thành. Do đó bắt đầu thực hiện các chỉ lệnh đã được nhóm lại giữa các dấu ngoặc móc. Nếu dữ liệu đọc (giá CPU) không phải là một số thì tín hiệu “dữ liệu sai” được hiển thị. Giá trị của các dữ liệu yêu cầu biến thế không thay đổi sau đó và những hành động được nhóm lại giữa các dấu ngoặc móc lại được thực hiện (bởi vì điều kiện là thực hiện cho đến khi hoàn thành xong). Ngược lại, nếu giá của CPU là một con số, thì dữ liệu yêu cầu biến thế sẽ có giá trị là không. Trong trường hợp đó điều kiện thực hiện cho đến khi không được hoàn thành nữa và hành động trong các dấu ngoặc móc không được thực hiện. Thuật toán sẽ tiếp tục thực hiện những chỉ dẫn từ sau dấu ngoặc “}” – đọc giá của motherboard.

Một vấn đề khác chúng ta gặp phải ở đây là thuật toán lặp đi lặp lại các hành động giống nhau (gần như là một). Xem xét trường hợp đọc giá của CPU, motherboard và các thành phần khác – tất cả các thao tác này giống hệt nhau. Vì vậy chúng ta có thể cô lập các hành động này và viết chung ở dạng gọi là quy trình/thủ tục hay chức năng/hàm. Khi đã viết như vậy chúng có thể được thực hiện lặp đi lặp lại cho vô số các bộ phận khác của một máy vi tính.

Điều này có nghĩa là vấn đề tính toán giá của một chiếc máy tính được chia nhỏ ra thành hai vấn đề:
•    dữ liệu vào và xác minh dữ liệu
•    tính toán thực sự

Mỗi vấn đề được giải quyết một cách riêng rẽ, tập trung vào điểm đặc trưng của mỗi môi trường. Cách lập trình này đuợc gọi là lập trình cấu trúc.

Tóm lại:
•    các chương trình được tạo ra để giải quyết các vấn đề và thực hiện một số nhiệm vụ.
•    truớc khi viết một chương trình để giải quyết một nhiệm vụ nào đó, cần phải tìm ra một thuật toán để giải quyết vấn đề.
•    thuật toán là một công thức, một loạt các câu lệnh thực hiện trên dữ liệu, bản mô tả việc chuyển dữ liệu đầu vào thành dữ liệu đầu ra.
•    một chương trình là bản ghi lại các thuật toán và dữ liệu trong một ngôn ngữ lập trình nhất định.
•    để một chương trình được thực hiện, sự biểu diễn của nó trong ngôn ngữ lập trình phải đuợc dịch sang ngôn ngữ máy tính mà CPU có thể hiểu được. Công việc này do các chương trình chuyên dụng được gọi là translator (máy dịch), compiler (trình biên dịch) hay interpreter (thông dịch) thực hiện.

Cần nhớ rằng các chương trình không chỉ phản ánh các bước (câu lệnh, hành động) của thuật toán mà còn thể hiện dữ liệu xử lý. Những dữ liệu này có thể là các bản sao tách biệt hay nhóm lại thành từng bộ (có liên kết và theo một trật tự nào đó). Trong những trường hợp như vậy chúng ta có thể về cấu trúc dữ liệu.

Do đó, có thể nêu ra một định nghĩa khác của chương trình (tác giả là N. Wirth).

CHƯƠNG TRÌNH là một công thức cụ thể của một thuật toán trừu tượng dựa trên sự biểu diễn cụ thể của cấu trúc dữ liệu.

Hai định nghĩa không trái ngược nhau. Định nghĩa đầu tiên, trích dẫn ngay từ đầu bài nhấn mạnh các hành động thực hiện bởi một chương trình còn định nghĩa thứ hai nhấn mạnh việc tạo ra một chương trình.

Chương trình (mã nguồn) được viết bằng ngôn ngữ lập trình. Mỗi ngôn ngữ lập trình có bảng chữ cái của nó – đó là một loạt các ký tự (chữ cái và con số) từ đó xây dựng nên các ký hiệu của ngôn ngữ (chuỗi các ký tự). Các quy tắc cú pháp xác định tiêu chuẩn cho phép xây dựng ký hiệu và các trật tự xuất hiện trong chương trình. Ngữ nghĩa xác định ý nghĩa của ký hiệu.

Ví dụ như trong ngôn ngữ lập trình có bảng chữ cái được xây dựng từ các chữ cái, con số và các ký tự đặc biệt, thì tên của các biến thể được xây dựng từ chữ cái và các con số. Một số chuỗi kỹ tự thể hiện chỉ lệnh ngôn ngữ được đặt trong dấu ngoặc và đứng sau “if”. Cách kết hợp các ký hiệu được định rõ (ví dụ công thức “nếu(a==b) a = 0;” đúng về mặt cú pháp trong khi công thức “nếu a = b a = 0” lại sai) và nghĩa của chuỗi ký hiệu đó cũng được xác định (ví dụ công thức “a = 3” nghĩa là gắn cho biến thể “a” giá trị là 3).

Có rất nhiều ngôn ngữ lập trình và chúng được phân loại theo nhiều tiêu chuẩn khác nhau.
Chắc chắn quan trọng nhất đó là tiêu chí về cấu trúc logic của ngôn ngữ và cách thức tạo ra các chương trình sử dụng nó.
Ngôn ngữ mệnh lệnh yêu cầu chi tiết về trật tự các bước thực hiện một nhiệm vụ nào đó trong khi ngôn ngữ trần thuật miêu tả mối quan hệ giữa các dữ liệu về mặt chức năng (ngôn ngữ chức năng/hàm) hay về mặt quy tắc (ngôn ngữ liên hệ, ngôn ngữ lập trình logic) và về kết quả của việc thực hiện một chương trình thu được bằng cách áp dụng các thuật toán “xây dựng trong ngôn ngữ” đặc biệt vào các mỗi quan hệ cụ thể.

Lập trình hướng đối tượng chính là kết hợp dữ liệu với các thao tác trên các dữ liệu, tạo cơ hội để tạo ra và sử dụng các loại dữ liệu mới trong chương trình, phản hồi tốt hơn về vùng của vấn đề đặt ra. Lập trình thủ tục (đôi khi có liên quan với lập trình mệnh lệnh) tách riêng dữ liệu và các chức năng, không cung cấp một cách đơn giản và đầy dủ cách phản chiếu vùng của vấn đề trong cấu trúc dữ liệu mà nó sử dụng.

Rysunek - jezyki

Các ví dụ về ngôn ngữ lập trình thủ tục như ALGOL, FORTRAN, PL/I, C.O. Ngôn ngữ hướng đối tượng như Smalltalk, Java, C++ và C#. Ngôn ngữ chức năng có tiếng nhất là Haskell, và ngôn ngữ lập trình logic là Prolog.
Các kiểu phân loại khác có liên quan đến phương thức mà mã nguồn của chương trình được chuyển thành chỉ lệnh của CPU.
Có thể phân biệt hai loại ngôn ngữ ở đây đó là: ngôn ngữ biên dịch và ngôn ngữ thông dịch.
Một chương trình biên dịch dịch ngôn ngữ mã nguồn chương trình sang thành các chỉ lệnh của CPU, nó kiểm tra tính xác thực và thông báo lỗi. Do đó việc biên dịch thực chất là là thông dịch ngôn ngữ và kiểm tra cú pháp.
Trong ngôn ngữ biên dịch, văn bản chương trình (mã nguồn) được dịch sang mã nhị phân (trung gian) bằng một chương trình chuyên dụng gọi là chương trình biên dịch. Một chương trình khác – thường được gọi là linker (kết nối) tạo ra một chương trình thực hiện từ mã nhị phân trung gian (đã sẵn sàng để chạy) và lưu chương trình đó trên ổ cứng ở dạng một file chạy (ví dụ với đuôi mở rộng “exe” hay miền thuộc tính chạy). Đây là cách mà ngôn ngữ “C” hay “C++” vận hành. Trong những trường hợp khác chương trình biên dịch tạo ra mã ký hiệu, mã này được thực hiện bởi trình thông dịch. Ngôn ngữ Java cũng hoạt động tương tự như thế.

Trình thông dịch thực hiện mã nguồn trực tiếp. Nhờ đó công việc xác minh cú pháp được thực hiện trong khi chương trình đang chạy. Một số ngôn ngữ biên dịch sang mã trung gian cho phép công việc kiểm tra này xảy ra trước khi chương trình chạy. Mã nguồn hay mã trung gian của ngôn ngữ thông dịch được đọc và thực hiện bởi chương trình thông dịch, chương trình này tạo ra chỉ lệnh của CPU tương ứng với chỉ lệnh tìm thấy trong nguồn.
Các ví dụ về ngôn ngữ thông dịch như: REXX, Objechương trìnhREXX, Perl, PHP.

Tóm lại: toàn bộ quá trình lập trình có thể được mô tả qua thuật toán sau:

Rysunek - programowanie

  1. HƯNG
    Tháng Mười Hai 1, 2009 lúc 1:07 sáng

    tốt lắm xin cảm ơn có gì thì gửi thư cho tôi. tôi muốn cần tài liệu bài tập ngôn ngữ lập trình c (ok) thông điệp tìm người giúp đỡ

  1. No trackbacks yet.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: