Divide and Conquer (Kĩ thuật chia để trị)

<Type to Remember>

<Theo “Kỹ thuật thiết kế giải thuật – Nguyễn Văn Linh”>

Chia để trị (divede and conquer) có thể nói là kĩ thuật quan trọng nhất, được áp dụng rộng rãi nhất để thiết kế các giải thuật có hiệu quả.

Nội dung kĩ thuật:

Để giải một bài toán kích thước n, ta chia bài toán đã cho thành một số bài toán con với kích thước nhỏ hơn. Giải các bài toán con này rồi tổng hợp lại kết quả để được lời giải của bài toán ban đầu.

Đối với các bài toán con, chúng ta lại sử dụng chia để trị để có được những bài toán có kích thước nhỏ hơn nữa. Quá trình trên sẽ dẫn đến những bài toán mà chúng ta dễ dàng thực hiện hoặc lời giải của nó là hiển nhiên, các bài toán này là các bài toán cơ sở.

Tóm lại, kĩ thuật chia để trị bao gồm 2 quá trình: Phân tích bài toán đã cho thành các bài toán cơ sở và tổng hợp kết quả của bài toán cơ sở để có được lời giải của các bài toán ban đầu. Tuy nhiên đối với một số bài toán, thì quá trình phân tích đã chứa đựng việc tổng hợp kết quả do đó nếu chúng ta đã giải xong các bài toán cơ sở thì bài toán ban đầu cũng được giải quyết. Ngược lại có những bài toán mà quá trình phân tích thì đơn giản nhưng việc tổng hợp lại kết quả rất khó khăn.

Kĩ thuật này sẽ cho ta một giải thuật đệ quy, mà việc xác định độ phức tạp của nó sẽ phải giải một phương trình đệ quy.

Các bài toán vi dụ: Các bạn tìm xem thêm về các bài toán như: “Bài toán xếp lịch thi đấu thể thao”, “Bài toán nhân 2 số nguyên lớn”, “Bài toán cân bằng”..

Advertisements

Binomial Heap – Heap nhị thức (P2)

Trong phần tiếp theo này chúng ta sẽ tìm hiểu cách cài đặt Binomial Heap và các thao tác xử lí trên nó, gồm có: Trộn 2 heap, Chèn,  tìm key nhỏ nhất, xóa key nhỏ nhất, giảm key, xóa heap.

Bởi vì không có hoạt động nào yêu cầu truy nhập ngẫu nhiên các nút gốc trên cây nhị thức , nên ta lưu trữ các nút gốc trên một danh sách liên kết, sắp xếp theo thứ tự tăng dần của cây.

Các thuật toán tạo Heap mới, lấy phần tử nhỏ nhất của heap, Heap-Union… :

Make-Binomial-Heap()
head[H] = NIL
return H


Binomial-Heap-Minimum(H)
y := NIL
x := head[H]
min := infinity
while x <> NIL
      do if key[x] < min             then min := key[x]
                 y := x          x := sibling[x]
return y Binomial-Link(y,z) p[y] := z sibling[y] := child[z]
child[z] := y degree[z] := degree[z] + 1





Binomial-HeapMerge(H1,H2)
a = head[H1]
b = head[H2]
head[H1] = Min-Degree(a, b)
if head[H1] = NIL
    return if head[H1] = b    then b = a a = head[H1]
while b <> NIL
    do if sibling[a] = NIL
          then sibling[a] = b                return           else if degree[sibling[a]] < degree[b]
                  then a = sibling[a]
                  else c = sibling[b]
                       sibling[b] = sibling[a]
                       sibling[a] = b                        a = sibling[a]
                       b = 




Binomial-Heap-Union(H1,H2)
H := Make-Binomial-Heap()
head[H] := Binomial-Heap-Merge(H1,H2)
free the objects H1 and H2 but not the lists they point to
if head[H] = NIL
   then return H prev-x := NIL
x := head[H]
next-x := sibling[x]
while next-x <> NIL
      do if (degree[x] <> degree[next-x]) or
                (sibling[next-x] <> NIL
                and degree[sibling[next-x]] = degree[x])
            then prev-x := x                  x := next-x             else if key[x] <= key[next-x]
                 then sibling[x] := sibling[next-x]
                      Binomial-Link(next-x,x)
                 else if prev-x = NIL
                         then head[H] = next-x                          else sibling[prev-x] := next-x                       Binomial-Link(x,next-x)
                      x := next-x          next-x := sibling[x]
return 




Binomial-Heap-Insert(H,x)
H' := Make-Binomial-Heap()
p[x] := NIL
child[x] := NIL
sibling[x] := NIL
degree[x] := 0
head[H'] := x H := Binomial-Heap-Union(H,H')





Binomial-Heap-Extract-Min(H)
find the root x with the minimum key in the root list of H,
         and remove x from the root list of H H' := Make-Binomial-Heap()
reverse the order of the linked list of x's children
        and set head[H'] to point to the head of the resulting list
H := Binomial-Heap-Union(H,H')
return 






Binomial-Heap-Decrease-Key(H,x,k)
if k > key[x]
   then error "hew key is greater than current key"
key[x] := k y := x z := p[y]
while z <> NIL and key[y] < key[z]
    do exchange key[y] and key[z]
       if y and z have satellite fields, exchange them, too.
       y := z        z := p[y]



Binomial-Heap-Delete(H,x) 
Binomial-Heap-Decrease-Key(H,x,-infinity)
Binomial-Heap-Extract-Min(H)


Binomial Heap – Heap nhị thức

Hôm nay ta sẽ tìm hiểu về cấu trúc dữ liệu mới là Binomial Heap (Heap nhị thức).

Phần 1: Khái niệm

Trong khoa học máy tính, một Binomial heap là một heap tương tự như binary heap nhưng được hỗ trợ việc trộn 2 heap lại với nhau một cách nhanh chóng. Điều này đạt được bằng cách sử dụng một cấu trúc cây đặc biệt, là cây nhị thức (Binomial Tree)

1. Cây nhị thức:(Binomial Tree)

1.1 Định nghĩa

Một heap nhị thức được tạo nên từ một collection các cây nhị thức. Cây nhị thức được định nghĩa đệ quy như sau:

– cây nhị thức bậc 0 là một node đơn

– cây nhị thức bậc K có một node gốc mà con của nó là những gốc của các cây nhị thức có bậc k-1, k-2, …, 2,1,0.

Ví dụ trên cây bậc 3 sẽ có nút gốc và các con của nó là các cây bậc 2, 1 và 0.

1.2 Tính chất

Cây nhị thức Bk (Binomial  Heap) thỏa mãn các tính chất sau đây:

  1.  Có  2^k nodes
  2.  Chiều cao của cây là Height=k;
  3.  Có chính xác C(k,i) nodes ở độ sâu i, với  i = 0,1,…k-1,k
  4.  Node gốc có bậc k và lớn hơn bất cứ node nào trong cây.
Bởi vì tính độc đáo trong cấu trúc của nó, một cây nhị thức mức k có thể được xây dựng từ 2 cây ở mức k-1 bằng cách gắn một trong 2 cây là cây con ngoài cùng bên trái của node gốc của cây còn lại. Đặc điểm này cũng chính là hành động cơ bản trong việc trộn heap.
2. Heap nhị thức (Binomial heap)
Một heap nhị thức H là một tập hợp các cây nhị thức thỏa mãn các tính chất của binomial heap sau đây:
1. Mỗi cây nhị thức trong H là những cây đã được sắp xếp thứ tự:  khóa của một node phải lớn hơn hoặc bằng khóa của cho nó trong cây.
2. có nhiều nhất chỉ là một cây nhị thức trong H mà có bậc cho trước.
Thuộc tính đầu tiên đảm bảo rằng gốc của mỗi cây trong heap chưa khóa nhỏ nhất trong cây đó.
Thuộc tính thứ hai chỉ ra rằng một heap nhị thức với n nodes bao gồm nhiều nhất log n + 1 cây nhị thức.
Thật ra số lượng và bậc của mỗi cây nhị thức trong heap nhị thức được xác định một cách duy nhất bởi số lượng node n : mỗi cây nhị thức tương ứng với một chữ số trong biểu diễn nhị phân của số n.
Ví dụ, số 13 là 1101 trong hệ nhị phân, 23 + 22 + 20, và vì vậy một binomial heap với 13 nodes sẽ bao gồm 3 cây nhị thức có bậc 0, 2 và 3.
Minh họa:
                                 

Giải thuật A*

Thuật giải A*, tìm đường đi cực tiểu trong đồ thị.

1. Về bài toán tìm đường đi ngắn nhất

Ta đã biết trong lí thuyết đồ thị bài toán tìm đường đi ngắn nhất nguồn đơn là bài toán tìm đường đi ngắn nhất  giữa 2 đỉnh sao cho tổng trọng số các cạnh tạo nên đường đi đó là nhỏ nhất.

Định nghĩa một cách hình thức, cho trước một đồ thị có trọng số (nghĩa là một tập đỉnh V, một tập cạnh E, và một hàm trọng số có giá trị thực f : E → R), cho trước một đỉnh v thuộc V, tìm một đường đi P từ v tới mỗi đỉnh v’ thuộc V sao cho

\sum_{p\in P} f(p)

là nhỏ nhất trong tất cả các đường nối từ v tới v’ .     <Wikipedia>

Có nhiều thuật toán để giải quyết bài toán này:

  • Thuật toán Dijkstra — giải bài toán nguồn đơn nếu tất cả các trọng số đều không âm. Thuật toán này có thể tính toán tất cả các đường đi ngắn nhất từ một đỉnh xuất phát cho trước s tới mọi đỉnh khác mà không làm tăng thời gian chạy.
  • Thuật toán Bellman-Ford — giải bài toán nguồn đơn trong trường hợp trọng số có thể có giá trị âm.
  • Giải thuật tìm kiếm A* giải bài toán nguồn đơn sử dụng heuristics để tăng tốc độ tìm kiếm
  • Thuật toán Floyd-Warshall — giải bài toán đường đi ngắn nhất cho mọi cặp đỉnh.
  • Thuật toán Johnson — giải bài toán đường đi ngắn nhất cho mọi cặp đỉnh, có thể nhanh hơn thuật toán Floyd-Warshall trên các đồ thị thưa.
  • Lý thuyết nhiễu (Perturbation theory); tìm đường đi ngắn nhất địa phương (trong trường hợp xấu nhất)    <Wikipedia>
Trong bài này ta sẽ quan tâm đến thuật toán tìm đường đi ngắn nhất A* (được cải tiến từ thuật toán Dijkstra)
2. Giải thuật tìm kiếm A*
A* là một thuật toán tìm kiếm trong đồ thị, tìm đường đi từ một nút khởi đầu đến một nút đích cho trước sử dụng một hàm heuristic ước lượng khoảng cách từ nút hiện tại đến nút đích (trạng thái đích), và nó sẽ duyệt đồ thị theo thứ tự ước lượng Heuristic này.
Ý tường:
Xét bài toán tìm đường, A* sẽ xây dựng tăng dần các tuyến đường từ đỉnh xuất phát đến khi nó tìm thấy đường đi chạm đến đích. Để xác định khả năng dẫn đến đích, A* sử dụng một đánh giá heuristic về khoảng cách từ một điểm bất kì cho trước đến đích. Trong ví dụ về bài toán tìm đường đi giao thông  này thì đánh giá heuristic là khoảng cách đường chim bay từ điểm cho trước đến điểm đích.
A* đảm bảo tính đầy đủ và tối ưu, nó luôn tìm thấy đường đi ngắn nhất nếu tồn tại một đường đi như thế. Đầy đủ và tối ưu hơn các thuật toán tìm đường đi khác ở chỗ nó không chỉ ước lượng khoảng cách còn lại (nhờ đánh giá heuristic) mà còn tính khoảng cách đã đi qua để tìm được đường đi ngắn nhất.
Mô tả thuật toán:

A* lưu giữ một tập các đường đi qua đồ thị, bắt đầu từ nút xuất phát. Tập lời giải này được lưu trong một hàng đợi ưu tiên (priority queue). Thứ tự ưu tiên gán cho một đường đi x được quyết định bởi hàm f(x) = g(x) + h(x).

Trong đó, g(x) là chi phí của đường đi cho đến thời điểm hiện tại, nghĩa là tổng trọng số của các cạnh đã đi qua. h(x) là hàm đánh giá heuristic về chi phí nhỏ nhất để đến đích từ x. Ví dụ, nếu “chi phí” được tính là khoảng cách đã đi qua, khoảng cách đường chim bay giữa hai điểm trên một bản đồ là một đánh giá heuristic cho khoảng cách còn phải đi tiếp.

f(x) có giá trị càng thấp thì độ ưu tiên của x càng cao, ta sử dụng f(x) này để xác định nút tiếp theo.

Ta có thể tham khảo mã giả cho thuật giải A* dưới đây: (nguồn)

function A*(start,goal)
     closedset := the empty set    // The set of nodes already evaluated.
     openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
     came_from := the empty map    // The map of navigated nodes.

     g_score[start] := 0    // Cost from start along best known path.
     h_score[start] := heuristic_cost_estimate(start, goal)
     f_score[start] := g_score[start] + h_score[start]    // Estimated total cost from start to goal through y.

     while openset is not empty
         x := the node in openset having the lowest f_score[] value
         if x = goal
             return reconstruct_path(came_from, came_from[goal])

         remove x from openset
         add x to closedset
         foreach y in neighbor_nodes(x)
             if y in closedset
                 continue
             tentative_g_score := g_score[x] + dist_between(x,y)

             if y not in openset
                 add y to openset
                 tentative_is_better := true
             else if tentative_g_score < g_score[y]
                 tentative_is_better := true
             else
                 tentative_is_better := false

             if tentative_is_better = true
                 came_from[y] := x
                 g_score[y] := tentative_g_score
                 h_score[y] := heuristic_cost_estimate(y, goal)
                 f_score[y] := g_score[y] + h_score[y]

     return failure

 function reconstruct_path(came_from, current_node)
     if came_from[current_node] is set
         p = reconstruct_path(came_from, came_from[current_node])
         return (p + current_node)
     else
         return current_node
Ví dụ:
AstarExample

nguồn ví dụ: wikipedia

 ví dụ ở bên
Nút màu green là nút bắt đầu, nút màu blue là nút đích.
Các nút đã duyệt qua màu orange.

[Wikipedia] Độ phức tạp của thuật toán

Nguồn bài viết: Độ phức tạp thuật toán

Đặt vấn đề

Thời gian mà máy tính khi thực hiện một thuật toán không chỉ phụ thuộc vào bản thân thuật toán đó, ngoài ra còn tùy thuộc từng máy tính. Để đánh giá hiệu quả của một thuật toán, có thể xét số các phép tính phải thực hiện khi thực hiện thuật toán này. Thông thường số các phép tính được thực hiện phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Vì thế độ phức tạp thuật toán là một hàm phụ thuộc đầu vào. Tuy nhiên trong những ứng dụng thực tiễn, chúng ta không cần biết chính xác hàm này mà chỉ cần biết một ước lượng đủ tốt của chúng.

Để ước lượng độ phức tạp của một thuật toán ta thường dùng khái niệm bậc O-lớn và bậc Θ (bậc Theta).

Bậc O-lớn

Gọi n là độ lớn đầu vào. Tùy thuộc từng bài toán mà n có thể nhận những giá trị khác nhau. Chẳng hạn, bài toán tính giai thừa thì n chính là số cần tính giai thừa. Nhiều bài toán số trị, chẳng hạn tính sai phân thì n là số chữ số có nghĩa cần đạt được. Trong các phép tính đối với ma trận thì n là số hàng hoặc cột của ma trận.

Độ phức tạp của bài toán phụ thuộc vào n. Ở đây ta không chỉ đặc trưng độ phức tạp bởi số lượng phép tính, mà dùng một đại lượng tổng quát là tài nguyên cần dùng R(n). Đó có thể là số lượng phép tính (có thể tính cả số lần truy nhập bộ nhớ, hoặc ghi vào bộ nhớ); nhưng cũng có thể là thời gian thực hiện chương trình (độ phức tạp về thời gian) hoặc dung lượng bộ nhớ cần phải cấp để chạy chương trình (độ phức tạp về không gian).

Xét quan hệ giữa tài nguyên và độ lớn đầu vào, nếu như tìm được hằng số C > 0, C không phụ thuộc vào n, sao cho với n đủ lớn, các hàm R(n),g(n) đều dương và

R(n)\leq C.g(n)

thì ta nói thuật toán có độ phức tạp cỡ O(g(n)).

Diễn giải

Độ phức tạp không phải là độ đo chính xác lượng tài nguyên máy cần dùng, mà đặc trưng cho động thái của hệ thống khi kích thước đầu vào tăng lên. Chẳng hạn với thuật toán có độ phức tạp tuyến tính O(n) (xem phần dưới), nếu kích thước đầu vào tăng gấp đôi thì có thể ước tính rằng tài nguyên cần dùng cũng tăng khoảng gấp đôi. Nhưng với thuật toán có độ phức tạp bình phương O(n2) thì tài nguyên sẽ tăng gấp bốn. Mặt khác, với thuật toán có độ phức tạp hàm mũ O(2n) thì chỉ cần công thêm 2 đơn vị vào độ lớn đầu vào cũng đã làm tài nguyên tăng gấp 4 lần (tức là theo cấp số nhân) rồi.

Các độ phức tạp thường gặp đối với các thuật toán thông thường gồm có:

  • Độ phức tạp hằng số, O(1). Số phép tính/thời gian chạy/dung lượng bộ nhớ không phụ thuộc vào độ lớn đầu vào. Chẳng hạn như các thao tác hệ thống: đóng, mở file.
  • Độ phức tạp tuyến tính, O(n). Số phép tính/thời gian chạy/dung lượng bộ nhớ có xu hướng tỉ lệ thuận với độ lớn đầu vào. Chẳng hạn như tính tổng các phần tử của một mảng một chiều.
  • Độ phức tạp đa thức, O(P(n)), với P là đa thức bậc cao (từ 2 trở lên). Chẳng hạn như các thao tác tính toán với mảng nhiều chiều (tính định thức ma trận).
  • Độ phức tạp logarit, O(logn) (chú ý: bậc của nó thấp hơn so với O(n)) . Chẳng hạn thuật toán Euclid để tìm ước số chung lớn nhất.
  • Độ phức tạp hàm mũ, O(2n). Trường hợp này bất lợi nhất và sẽ rất phi thực tế nếu thực hiện thuật toán với độ phức tạp này.

Lưu ý

Định nghĩa trên mang tính “an toàn” theo nghĩa nó chỉ xét sự tiêu tốn tài nguyên không vượt quá một ngưỡng g(n) nào đó, chứ không nhất thiết đúng bằng g(n) (chú ý dấu bất đẳng thức). Theo đó, một thuật toán có độ phức tạp cỡ n thì đồng thời sẽ có độ phức tạp cỡ n2; với hàm ý rằng thuật toán này không bao giờ có động thái phức tạp hóa vượt qua ngưỡng đa thức bậc hai.

Bậc Ω và Θ

Tương tự như với bậc O-lớn, nếu như tìm được các hằng số C,k1,k2 đều dương và không phụ thuộc vào n, sao cho với n đủ lớn, các hàm R(n),f(n) và h(n) đều dương và

R(n)\geq C \cdot f(n)
k_1\cdot h(n) \leq R(n) \leq k_2\cdot h(n)

thì ta nói thuật toán có độ phức tạp cỡ lớn hơn Ω(n), và đúng bằng cỡ Θ(h(n)).

Như vậy nếu xét một cách chặt chẽ, kí hiệu Θ mới biểu thị độ phức tạp của thuật toán một cách chặt chẽ. Tuy nhiên qua một thời gian dài kí hiệu O(n) cũng đã được dùng phổ biến, chẳng hạn [1].

Các Ngôn ngữ lập trình

Trích bài viết Ngôn ngữ lập trình nào

Đây là danh sách các NNLT, từ những NN đã có cách đây hàng chục năm đến những NN mới xuất hiện gần đây, chủ yếu là các NN tổng quát. Các NN được nhóm theo các tính năng tương đồng. Vì giá trị lịch sử, có một số NN “chết” hay ít được sử dụng hiện diện trong danh sách. Danh sách này có thể chưa đầy đủ.
NGÔN NGỮ MÁY dùng các số 0 và 1 để “ra lệnh” cho bộ xử lý. Tập lệnh chỉ tương thích trong cùng họ CPU và rất khó lập trình.

NGÔN NGỮ ASSEMBLY gần giống như NN máy nhưng có ưu điểm là tập lệnh dễ đọc . Nói chung mỗi lệnh trong Assembly (như MOV A,B) tương ứng với một lệnh mã máy (như 11001001). Chương trình Assembly được biên dịch trước khi thực thi. Nếu cần tốc độ và kích thước chương trình thật nhỏ, Assembly là giải pháp.

C đạt được sự thỏa hiệp giữa việc viết code hiệu quả của Assembly và sự tiện lợi và khả năng chạy trên nhiền nền tảng của NNLT cấp cao có cấu trúc. NN hơn 20 năm tuổi này hiện vẫn được tin dùng trong lĩnh vực lập trình hệ thống. Có các công cụ thương mại và miễn phí cho gần như mọi HĐH.

C++ là NN được dùng nhiều nhất hiện nay, đa số phần mềm thương mại được viết bằng C++. Tên của NN có lý do: C++ bao gồm tất cả ưu điểm của C và bổ sung thêm các tính năng hướng đối tượng. Có các công cụ thương mại và miễn phí cho gần như mọi HĐH.

C# [phát âm ‘C sharp“] là lời đáp của Microsoft đối với Java. Do không đạt được thỏa thuận với Sun về vấn đề bản quyền, Microsoft đã tạo ra NN với các tính năng tương tự nhưng chỉ chạy trên nền Windows.

JAVA là phiên bản C++ được thiết kế lại hợp lý hơn, có khả năng chạy trên nhiều nền tảng; tuy nhiên tốc độ không nhanh bằng C++. Có các công cụ miễn phí và thương mại hỗ trợ cho hầu hết các HĐH hiện nay. Tuy Microsoft đã gỡ bỏ hỗ trợ Java khỏi cài đặt mặc định của các phiên bản Windows mới, nhưng việc bổ sung rất dễ dàng.

PASCAL được thiết kế chủ yếu dùng để dạy lập trình, tuy nhiên nó đã trở nên phổ biến bên ngoài lớp học. Pascal yêu cầu tính cấu trúc khá nghiêm ngặt. Có các công cụ thương mại và miễn phí cho DOS, Windows, Mac, OS/2 và các HĐH họ Unix. Trình soạn thảo website BBEdit được viết bằng Pascal.

DELPHI là phiên bản hướng đối tượng của Pascal được hãng Borland phát triển cho công cụ phát triển ứng dụng nhanh có cùng tên. Môi trường Delphi được thiết kế để cạnh tranh với Visual Basic của Microsoft, hỗ trợ xây dựng giao diện nhanh bằng cách kéo thả các đối tượng và gắn các hàm chức năng. Khả năng thao tác CSDL là một ưu điểm khác của NN. Borland, có các công cụ thương mại cho Windows và Linux.

BASIC [‘Beginner’s All-purpose Symbolic Instruction Code“] là NNLT đầu tiên dùng cho máy vi tính thời kỳ đầu. Các phiên bản hiện đại của BASIC có tính cấu trúc hơn. Có các công cụ thương mại và miễn phí cho DOS, Windows, Mac và các HĐH họ Unix.

VISUAL BASIC [phiên bản của Basic cho môi trường đồ hoạ] là NN đa năng của Microsoft. Nó bao gồm BASIC, NN macro của Microsoft Office (VBA – Visual Basic for Application), và công cụ phát triển ứng dụng nhanh. Tiếc là ứng dụng VB chỉ có thể chạy trên Windows và bạn bị lệ thuộc vào những chính sách thay đổi của Microsoft. (Chương trình viết bằng VB 6 hay các phiên bản trước sẽ không hoàn toàn tương thích với VB.NET)

ADA phần lớn dựa trên Pascal, đây là một dự án của Bộ Quốc Phòng Mỹ. ADA có nhiều điểm mạnh, như cơ chế kiểm soát lỗi, dễ bảo trì và sửa đổi chương trình. Phiên bản hiện thời có cả các tính năng hướng đối tượng.

ICON là NN thủ tục cấp cao. Xử lý văn bản là một trong những điểm mạnh của nó. Có các phiên bản cho Windows, HĐH họ Unix và các môi trường Java; các phiên bản cũ hơn hỗ trợ các HĐH khác.

SMALLTALK môi trường phát triển hướng đối tượng và đồ hoạ của Smalltalk chính là nguồn cảm hứng cho Steve Jobs và Bill Gates ‘phát minh“ giao diện Mac OS và Windows.

RUBY hợp một số tính năng tốt nhất của nhiều NN khác. Đây là NN hướng đối tượng thuần túy như Smalltalk, nhưng có cú pháp trong sáng hơn. Nó có khả năng xử lý văn bản mạnh tương tự như Perl nhưng có tính cấu trúc hơn và ổn định hơn.

PERL thường được xem đồng nghĩa với “CGI Scripting”. Thực tế, Perl “lớn tuổi” hơn web. Nó ‘dính“ vào công việc lập trình web do khả năng xử lý văn bản mạnh, rất linh động, khả năng chạy trên nhiều nền tảng và miễn phí.

TCL (phát âm ‘tickle“) có thể tương tác tốt với các công cụ dùng văn bản như trình soạn thảo, trình biên dịch… dùng trên các HĐH họ Unix, và với phần mở rộng TK nó có thể truy cập tới các giao diện đồ hoạ như Windows, Mac OS và X-Windows, đóng vai trò kết dính các thành phần lại với nhau để hoàn thành các công việc phức tạp. Phương pháp mô-đun này là nền tảng của Unix

PYTHON là NN nguồn mở, hướng đối tượng, tương tác và miễn phí. Ban đầu được phát triển cho Unix, sau đó ‘bành trướng“ sang mọi HĐH từ DOS đến Mac OS, OS/2, Windows và các HĐH họ Unix. Trong danh sách người dùng của nó có NASA và RedHat Linux.

PIKE cũng là NN nguồn mở, miễn phí được phát triển cho nhu cầu cá nhân, và hiện được công ty Roxen Internet Software của Thuỵ Điển phát triển dùng cho máy chủ web trên nền Roxen. Đây là NN hướng đối tượng đầy đủ, có cú pháp tương tự C, và có thể mở rộng để tận dụng các mô-đun và thư viện C đã biên dịch để tăng tốc độ. Nó có thể dùng cho các HĐH họ Unix và Windows.

PHP (Hypertext Pre-Processor) là NN mới nổi lên được cộng đồng nguồn mở ưa chuộng và là mô-đun phổ biến nhất trên các hệ thống Apache (web server). Giống như CFML, mã lệnh nằm ngay trong trang web. Nó có thể dễ dàng truy cập tới các tài nguyên hệ thống và nhiều CSDL. Nó miễn phí và tính khả chuyển đối với các HĐH họ Unix và Windows.

MACROMEDIA COLDFUSION có mã lệnh CFML (Cold Fusion Markup Language) được nhúng trong trang web rất giống với thẻ lệnh HTML chuẩn. Rất mạnh, có các công cụ để truy cập nhiều CSDL và rất dễ học. Hạn chế chính của nó là giá cả, tuy nhiên có phiên bản rút gọn miễn phí. Chạy trên Windows và các HĐH họ Unix.

ACTIVE SERVER PAGES (ASP) được hỗ trợ miễn phí với máy chủ web của Microsoft (IIS). Thực sự nó không là NNLT, mà được gọi, theo Microsoft, là ‘môi trường lập kịch bản phía máy chủ“.Nó dùng VBScript hay JScript để lập trình. Chỉ chạy trên Windows NT/2K. Microsoft đã thay NN này bằng ASP.NET, tuy có tên tương tự nhưng không phải là bản nâng cấp.

JAVASERVER PAGES (JSP) là NN đầy hứa hẹn. Nó dùng Java, có phần mềm máy chủ nguồn mở và miễn phí (Tomcat). Có thể chạy trên hầu hết các máy chủ web, gồm Apache, iPlanet và cả Microsoft IIS.

LISP [‘LISt Processing“] là NNLT ‘có thể lập trình“, được xây dựng dựa trên khái niệm đệ quy và có khả năng thích ứng cao với các đặc tả không tường minh. Nó có khả năng giải quyết những vấn đề mà các NN khác không thể, đó là lý do NN hơn 40 năm tuổi này vẫn tồn tại. Yahoo Store dùng Lisp.

PROLOG [“PROgramming in Logic”] được thiết kế cho các bài toán luận lý, ví dụ như “A bao hàm B, A đúng, suy ra B đúng” – một công việc khá khó khăn đối với một NN thủ tục.

COBOL [“Common Business-Oriented Language”] có tuổi đời bằng với điện toán thương mại, bị buộc tội không đúng về vụ Y2K, và dù thường được dự đoán đến hồi cáo chung nhưng nó vẫn tồn tại nhờ tính hữu dụng trong các ứng dụng xử lý dữ liệu và lập báo cáo kinh doanh truyền thống. Hiện có phiên bản với các tính năng hướng đối tượng và môi trường phát triển tích hợp cho Linux và Windows.

FORTRAN [“FORmula TRANslation”] là NN xưa nhất vẫn còn dùng. Nó xuất sắc trong công việc

đầu tiên mà máy tính được tin cậy: xử lý các con số. Theo đúng nghĩa đen, đây là NN đưa con người lên mặt trăng (dùng trong các dự án không gian), một số tính năng của NN đã được các NN khác hiện đại hơn “mượn”.

dBase [“DataBASE”] là NN lệnh cho chương trình quản lý CSDL mang tính đột phá của Ashton-Tate. Khi chương trình phát triển, NN cũng phát triển và nó trở thành công cụ phát triển. Tới thời kỳ xuất hiện nhiều công cụ và trình biên dịch cạnh tranh, nó chuyển thành chuẩn.

Foxpro là một nhánh phát triển của dBase dưới sự “bảo hộ” của Microsoft. Thực ra nó là công cụ phát triển hơn là NN. Tuy có lời đồn đại về sự cáo chung, nhưng NN vẫn phát triển. Hiện Foxpro có tính đối tượng đầy đủ và có công cụ phát triển mạnh (Visual Foxpro).

Erlang [“Ericsson LNAGuage”] thoạt đầu được hãng điện tử Ericsson phát triển để dùng riêng nhưng sau đó đưa ra bên ngoài như là phần mềm nguồn mở. Là NN cấp thấp xét theo việc nó cho phép lập trình điều khiển những thứ mà thường do HĐH kiểm soát, như quản lý bộ nhớ, xử lý đồng thời, nạp những thay đổi vào chương trình khi đang chạy… rất hữu ích trong việc lập trình các thiết bị di động. Erlang được dùng trong nhiều hệ thống viễn thông lớn của Ericsson.

HASKELL là NN chức năng, nó được dùng để mô tả vấn đề cần tính toán chứ không phải cách thức tính toán.

 

nguồn: http://my.opera.com/levanduyet/blog/2011/05/29/ng