[Java] Ví dụ Giải phương trình bậc 2 sử dụng Java G.U.I [Java GUI - Giao diện đồ họa trong Java]

Xây dựng Project Giải phương trình bậc 2 (ax^2 + bx +c =0) sử dụng GUI.

Thực hiện:
1. Xây dựng Project như hình vẽ

Trong đó:
 + class GPTB2_GUI: Chứa thiết kế giao diện và phương thức chính
 + class GPTB2: Giải và biện luận phương trình bậc 2

2. Thiết kế giao diện (code thiết kế trong class GPTB2_GUI)



3. Java Code
+ class GPTB2_GUI -----------------------------------------------------

package gptb2_gui;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.border.*;

public class GPTB2_GUI  extends JFrame {
private static final long serialVersionUID = 1L;

public GPTB2_GUI(String title)
{
    setTitle(title);
}
// Hiển thị
public void doShow()
{
    setSize(400, 300);
    setLocationRelativeTo(null);
    setDefaultCloseOperation(EXIT_ON_CLOSE);
    addControl();
    setResizable(false);
    setVisible(true);
}

// Thiết kế giao diện
public void addControl()
{
    JPanel pnBorder=new JPanel();
    pnBorder.setLayout(new BorderLayout());
    // tiêu đề
    JPanel pnNorth=new JPanel();
    JLabel lblTitle=new JLabel("Giải phương trình bậc 2");
    pnNorth.add(lblTitle);
    pnBorder.add(pnNorth,BorderLayout.NORTH);
    lblTitle.setForeground(Color.BLUE);
    Font ft=new Font("arial", Font.BOLD, 25);
    lblTitle.setFont(ft);
    // button
    JPanel pnSouth=new JPanel();
    JButton btnGiai=new JButton("Giải");
    JButton btnXoa=new JButton("Xóa");
    JButton btnThoat=new JButton("Thoát");
    pnSouth.add(btnGiai);
    pnSouth.add(btnXoa);
    pnSouth.add(btnThoat);
    pnBorder.add(pnSouth,BorderLayout.SOUTH);
    pnSouth.setBackground(Color.LIGHT_GRAY);
    Border  southborder=BorderFactory.createLineBorder(Color.RED);
    TitledBorder southTitleBorder=new TitledBorder(southborder, "Chọn tác vụ");
    pnSouth.setBorder(southTitleBorder);
    // panel nhap
    JPanel pnCenter=new JPanel();
    pnCenter.setLayout(new BoxLayout(pnCenter, BoxLayout.Y_AXIS));
    pnBorder.add(pnCenter,BorderLayout.CENTER);
    Border  centerborder=BorderFactory.createLineBorder(Color.RED);
    TitledBorder centerTitleBorder=new TitledBorder(centerborder, "Nhập hệ số a, b, c:");
    pnCenter.setBorder(centerTitleBorder);
    // hệ số a
    JPanel pna=new JPanel();
    JLabel lbla=new JLabel("Nhập a:");
    final JTextField txta=new  JTextField(15);
    pna.add(lbla);
    pna.add(txta);
    pnCenter.add(pna);
    // hệ số b
    JPanel pnb=new JPanel();
    JLabel lblb=new JLabel("Nhập b:");
    final JTextField txtb=new  JTextField(15);
    pnb.add(lblb);
    pnb.add(txtb);
    pnCenter.add(pnb);
    // hệ số c
    JPanel pnc=new JPanel();
    JLabel lblc=new JLabel("Nhập c:");
    final JTextField txtc=new  JTextField(15);
    pnc.add(lblc);
    pnc.add(txtc);
    pnCenter.add(pnc);
    // hệ số kq
    JPanel pnkq=new JPanel();
    JLabel lblkq=new JLabel("kết quả:");
    final JTextField txtkq=new  JTextField(15);
    pnkq.add(lblkq);
    pnkq.add(txtkq);
    pnCenter.add(pnkq);
    
    lbla.setPreferredSize(lblkq.getPreferredSize());
    lblb.setPreferredSize(lblkq.getPreferredSize());
    lblc.setPreferredSize(lblkq.getPreferredSize());
    
    // sự kiện thoát
    btnThoat.addActionListener(new ActionListener() {
        public void actionPerformed(ActionEvent arg0) {
            int ret=JOptionPane.showConfirmDialog(null, "Thoát khỏi chương trình ?", "Thoát", JOptionPane.YES_NO_OPTION);
            if(ret==JOptionPane.YES_OPTION)
                System.exit(0);
        }
    });
    // sự kiện xóa
    btnXoa.addActionListener(new ActionListener() {
        public void actionPerformed(ActionEvent arg0) {
            txta.setText("");
            txtb.setText("");
            txtc.setText("");
            txtkq.setText("");
            txta.requestFocus();
        }
    });
    // sự kiện giải
    btnGiai.addActionListener(new ActionListener() {
        public void actionPerformed(ActionEvent arg0) {
            String sa=txta.getText();
            float a=0,b=0,c=0;
            try
                {
                    a=Float.parseFloat(sa);;
                }
            catch(Exception ex)
                {
                    JOptionPane.showMessageDialog(null, "Nhập sai định dạng!");
                    txta.selectAll();
                    txta.requestFocus();
                    return;
                }
            String sb=txtb.getText();
            try
            {
                b=Float.parseFloat(sb);
            }
            catch(Exception ex)
            {
                JOptionPane.showMessageDialog(null, "Nhập sai định dạng!");
                txtb.selectAll();
                txtb.requestFocus();
                return;
             }
            String sc=txtc.getText();
            try
            {
                c=Float.parseFloat(sc);
            }
            catch(Exception ex)
            {
                JOptionPane.showMessageDialog(null, "Nhập sai định dạng!");
                txtc.selectAll();
                txtc.requestFocus();
                return;
            }
            String kq="";
            PTB2 t=new PTB2(a,b,c);
            kq=t.GiaiPT();
            txtkq.setText(kq);
        }
    });
    Container con=getContentPane();
    con.add(pnBorder);
}

// main method
public static void main(String[] args) {
        GPTB2_GUI ui=new GPTB2_GUI("Phuong trinh bac 2");
        ui.doShow();
 }
}

+ class GPTB2 -----------------------------------------------------------

package gptb2_gui;
public class PTB2 {
    float a,b,c;
    public PTB2(float a, float b, float c){
        this.a=a;
        this.b=b;
        this.c=c;
    }
    String GiaiPT(){
        String kq="";
        if(a==0)
            if(b==0)
                if(c==0)
                    kq="Phương trình vô số nghiệm";
                else
                    kq="Phương trình vô nghiệm";
            else
                kq="Phương trình có 1 nghiệm x= "+(-c/b);
        else
        {
            float d=b*b-4*a*c;
            if(d<0)
               kq="Phương trình vô nghiệm";
            if (d==0)
               kq="Phương trình có nghiệm kép x1=x2= "+(-b/(2*a)); 
            if(d>0)
            { 
                float x1=((-b-(float)Math.sqrt(d))/(2*a)), 
                      x2=((-b+(float)Math.sqrt(d))/(2*a));
                kq="x1= "+x1+"; x2= "+x2; 
            }
        }
        return kq;
    }
}

//-----------------------------------------------------------------------------------


Đoc thêm các bài khác

Bài 1: Chương trình JAVA đầu tiên
Bài 2: Các kiểu dữ liệu và toán tử trong
Bài 3: Các cấu trúc điều khiển trong Java
Bài 4 : Mảng và chuỗi trong Java
Bài 5: Lớp (class) và đối tượng (object) trong Java
Bài 6:Thừa kế (Inheritance) và đa hình (Polymorphism)
Ví dụ lập trình giao diện đồ họa với Java (GUI)
Ví dụ lập trình kết nối dữ liệu với Java (JDBC)
Ví dụ về lập trình Android 

[Algorithms] Phân tích độ phức tạp về thời gian của thuật toán [Thời gian thực hiện thuật toán]

Thông thường khi tính toán độ phức tạp của một thuật giải thì thời gian thực hiện là khía cạnh quan trọng của một giải thuật. Việc chọn một giải thuật đưa đến kết quả nhanh nhất là một đòi hỏi thực tế. Thời gian thực hiện giải thuật bằng chương trình máy tính phụ thuộc vào rất nhiều yếu tố. Bài viết này sẽ giúp các bạn biết một số khái niệm các các phân tích, đánh giá độ phức tạp của một thuật toán.

1. Giới thiệu (Introduction)

- Như chúng ta được biết thì thời gian thực hiện của giải thuật phụ thuộc vào rất nhiều yếu tố. Trong đó yếu tố cần chú ý nhất là kích thước của dữ liệu đưa vào. Dữ liệu càng lớn thì thời gian xử lý càng chậm. Chẳng hạn như thời gian sắp xếp một dãy số phải chịu ảnh hưởng của các số thuộc dãy số đó. Nếu gọi n là kích thước dữ liệu đưa vào thì thời gian thực hiện của giải thuật có thể biểu diễn một cách tương đối như một hàm của n: T(n).




- Phần cứng máy tính, ngôn ngữ viết chương trình và chương trình dịch ngôn ngữ ấy đều ảnh hưởng tới thời gian thực hiện. Những yếu tố này không giống nhau trên các loại máy vì vậy không thể dựa vào chúng khi xác định T(n) => T(n) không thể biểu diễn bằng đơn vị thời gian (giờ, phút, giây..).

- Nếu thời gian thực hiện một giải thuật là T1(n) = n^2 (n mũ 2) và thời gian thực hiện của một giải thuật khác là T2(n) = 100n thì khi n đủ lớn thời gian thực hiện của giải thuật T2 rõ ràng nhanh hơn T1. Khi đó, nếu nói rằng thời gian thực hiện giải thật tỉ lệ thuận với n hay tỉ lệ thuận với n2 cũng cho ta một cách đánh giá tương đối về tốc độ thực hiện của giải thuật đó khi n khá lớn.

- Cách đánh giá thời gian thực hiện của giải thuật độc lập với máy tính và các yếu tố liên quan tới máy tính như vậy sẽ dẫn tới khái niệm gọi là độ phức tạp của giải thuật.

2. Các ký pháp để đánh giá độ phức tạp tính toán.

Cho một giải thuật thực hiện trên dữ liệu với kích thước n. Giả sử T(n) là thời gian thực hiện một giải thuật đó, g(n) là một hàm xác định dương với mọi n. Khi đó ta nói độ phức tạp tính toán của giải thuật là:

- O(g(n)) nếu tồn tại các hằng số dương c và n0 sao cho T(n) ≤ c.g(n) với mọi n ≥ n0 . Ký pháp này được gọi là ký pháp chữ O lớn (big-oh notation). Trong ký pháp chữ O lớn, hàm g(.) được gọi là giới hạn trên (asymptotic upper bound) của hàm T(.).

- Ω(g(n)) nếu tồn tại các hằng số dương c và n0 sao cho c.g(n) ≤ T(n) với mọi n ≥ n0. Ký hiệu này gọi là ký pháp Ω lớn (big-omega notation). Trong ký pháp Ω lớn, hàm g(.) được gọi là giới hạn dưới (asymptotically lower bound) của hàm T(.).

- Θ(g(n) nếu tồn tại các hằng số dương c1, c2 và n0 sao cho c1.g(n) ≤ f(n) ≤ c2.g(n) với mọi n ≥ n0 . Ký pháp này được gọi là ký pháp Θ lớn (big-theta notation). Trong ký pháp Θ lớn, hàm g(.) được gọi là giới hạn chặt (asymptotically tight bound) của hàm T(.).


Hình dưới đây: biểu diễn đồ thị của ký pháp Θ lớn, Ο lớn và Ω lớn. Dễ thấy rằng T(n) = Θ(g(n)) nếu và chỉ nếu T(n) = O(g(n)) và T(n) = Ω(g(n))



- Ta nói độ phức tạp tính toán của giải thuật là:
o(g(n)) nếu với mọi hằng số dương c, tồn tại một hằng số dương n0 sao cho T(n) ≤ c.g(n) với mọi n ≥ n0. Ký pháp này gọi là ký pháp chữ o nhỏ (little-oh notation).
ω(g(n)) nếu với mọi hằng số dương c, tồn tại một hằng số dương n0 sao cho c.g(n) ≤ T(n) với mọi n ≥ n0 . Ký pháp này gọi là ký pháp ω nhỏ (little-omega notation).

- Ví dụ: Nếu T(n) = n2 + 1, thì:
T(n) = O(n2 ). Thật vậy, chọn c = 2 và n0 = 1. Rõ ràng với mọi n ≥ 1, ta có: T(n) = n2 + 1 ≤ 2.n2 = 2.g(n).
T(n) ≠ o(n2). Thật vậy, chọn c = 1. Rõ ràng không tồn tại n để: n2 + 1 ≤ n2 , tức là không tồn tại n0 thoả mãn định nghĩa của ký pháp chữ o nhỏ.

- Lưu ý rằng không có ký pháp θ nhỏ.

Một vài tính chất

- Tính bắt cầu (transitivity): Tất cả các ký pháp nêu trên đều có tính bắt cầu.
Nếu f(n) = Θ(g(n)) và g(n) = Θ(h(n)) thì f(n) = Θ(h(n)).
Nếu f(n) = O(g(n)) và g(n) = O(h(n)) thì f(n) = O(h(n)).
Nếu f(n) = Ω(g(n)) và g(n) = Ω(h(n)) thì f(n) = Ω(h(n)).
Nếu f(n) = o(g(n)) và g(n) = o(h(n)) thì f(n) = o(h(n)).
Nếu f(n) = ω(g(n)) và g(n) = ω(h(n)) thì f(n) = ω(h(n)).

- Tính phản xạ (reflectivity): Các ký pháp “lớn” mới có tính phản xạ.
f(n) = Θ(f(n)).
f(n) = O(f(n)).
f(n) = Ω(f(n)).

- Tính đối xứng (symmetry): chỉ có ký pháp Θ mới có tính đối xứng.
f(n) = Θ(g(n)) nếu và chỉ nếu g(n) = Θ(f(n)).

- Tính chuyển vị đối xứng (transpose symmetry):
f(n) = O(g(n)) nếu và chỉ nếu g(n) = Ω(f(n)).
f(n) = o(g(n)) nếu và chỉ nếu g(n) = ω(f(n)).

Để dễ nhớ ta coi các ký pháp Ο, Ω, Θ, ο, ω lần lượt tương ứng với các phép so sánh ≤, ≥, =, <, >. Từ đó suy ra các tính chất trên.

3. Xác định độ phức tạp tính toán của giải thuật

Việc xác định độ phức tạp tính toán của một giải thuật bất kỳ có thể rất phức tạp. Tuy nhiên, độ phức tạp tính toán của một số giải thuật trong thực tế có thể tính bằng một số quy tắc đơn giản.

3.1 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)).

Chứng minh:

T(n) = O(c1.f(n)) nên ∃ c0 > 0 và ∃ n0 > 0 để T(n) ≤ c0.c1 .f(n) với ∀n ≥ n0 . Đặt C = c0.c1 và dùng định nghĩa, ta có T(n) = O(f(n)).

Qui tắc này cũng đúng với các ký pháp Ω, Θ, ο và ω.

3.2 Quy tắc lấy MAX

Nếu đoạn chương trình P có thời gian thực hiện T(n) = O(f(n) + g(n)) thì có thể coi đoạn chương trình đó có độ phức tạp tính toán O(max ( f(n) , g(n) )).

Chứng minh:

T(n) = O(f(n) + g(n)) nên ∃C > 0 và ∃ n0 > 0 để T(n) ≤ C.f(n) + C.g(n), ∀n ≥ n0 .

Vậy T(n) ≤ C.f(n) + C.g(n) ≤ 2C.max(f(n), g(n)) (∀n ≥ n0 ).

Từ định nghĩa suy ra T(n) = O(max( f(n), g(n) )).

Qui tắc này cũng đúng với các ký pháp Ω, Θ, ο và ω.

3.3 Quy tắc cộng

Nếu đoạn chương trình P1 có thời gian thực hiện T1(n) = O(f(n)) và đoạn chương trình P2 có thời gian thực hiện là T2(n) = O( g(n)) thì thời gian thực hiện P1 rồi đến P2 tiếp theo sẽ là:

T1(n) + T2(n) = O(f(n) + g(n))

Chứng minh:
T1(n) = O(f(n)) nên ∃ n1 > 0 và c1 > 0 để T1(n) ≤ c1.f(n) với ∀ n ≥ n1.
T2(n) = O(g(n)) nên ∃ n2 > 0 và c2 > 0 để T2(n) ≤ c2.g(n) với ∀ n ≥ n2.

Chọn n0 = max(n1, n2) và c = max(c1, c2) ta có:

Với ∀ n ≥ n0 :
T1(n) + T2(n) ≤ c1.f(n) + c2.g(n) ≤ c.f(n) + c.g(n) ≤ c.(f(n) + g(n))

Vậy T1(n) + T2(n) = O(f(n) + g(n)).

- Quy tắc cộng cũng đúng với các ký pháp Ω, Θ, ο và ω.

3.4 Quy tắc nhân

Nếu đoạn chương trình P có thời gian thực hiện là T(n) = O( f(n)). Khi đó, nếu thực hiện k(n) lần đoạn chương trình P với k(n) = O( g(n)) thì độ phức tạp tính toán sẽ là O( g(n). f(n))

Chứng minh

Thời gian thực hiện k(n) lần đoạn chương trình P sẽ là k(n)T(n). Theo định nghĩa.
∃ ck ≥ 0 và nk> 0 để k(n) ≤ ck(g(n)) với ∀ n ≥ nk
∃ cT ≥ 0 và nT > 0 để T(n) ≤ cT (f(n)) với ∀ n ≥ nT

Vậy với ∀ n ≥ max(nT , nk ) ta có k(n).T(n) ≤ cT.ck(g(n).f(n))

- Quy tắc nhân cũng đúng với các ký pháp Ω, Θ, ο và ω.

3.5 Định lý Master (Master Theorem)

Cho a ≥ 1 và b >1 là hai hằng số, f(n) là một hàm với đối số n, T(n) là một hàm xác định trên tập các số tự nhiên được định nghĩa như sau:

T(n) = a.T(n/b) + f(n)

Ở đây n/b có thể hiểu là [n/b]. Khi đó:



- Định lý Master là một định lý quan trọng việc phân tích độ phức tạp tính toán của các giải thuật lặp hay đệ quy. Tuy nhiên việc chứng minh định lý khá dài dòng nằm ngoài phạm vi bài viết này.

3.6 Một số tính chất

- Ta quan tâm chủ yếu đến các ký pháp “lớn”. Rõ ràng ký pháp Θ là “chặt” hơn ký pháp O và Ω theo nghĩa: nếu độ phức tạp tính toán của giải thuật có thể viết là Θ( f(n)) thì cũng có thể viết là O( f(n)) cũng như Ω( f(n)). Dưới đây là một số cách biểu diễn độ phức tạp tính toán qua ký pháp Θ.
Nếu một thuật toán có thời gian thực hiện là P(n), trong đó P(n) là một đa thức bậc k thì độ phức tạp tính toán đó có thể viết là Θ(nk ).
Nếu một thuật toán có thời gian thực hiện là logaf(n). Với b là một số dương, ta nhận thấy logaf(n) = logab.logb f(n). Tức là: Θ(loga f(n)) = Θ(logb f(n)). Vậy ta có thể nói rằng độ phức tạp tính toán của thuật toán đó là Θ(log (f(n))) mà không cần ghi cơ số của logarit.
Nếu một thuật toán có độ phức tạp là hằng số, tức là thời gian thực hiện không phụ thuộc vào kích thước dữ liệu vào thì ta ký hiệu độ phức tạp tính toán của thuật toán đó là Θ(1).

- Dưới đây là một số hàm số hay dùng để ký hiệu độ phức tạp tính toán và bảng giá trị chúng để tiện theo dõi sự tăng của hàm theo đối số n.



- Ví dụ: Thuật toán tính tổng các số từ 1 đến n.

+ Nếu viết theo sơ đồ sau:



Đoạn chương trình ở các dòng 1, 2 và 4 có độ phức tạp tính toán là Θ(1). Vòng lặp ở dòng 3 lặp n lần phép gán S := S + i , nên thời gian tính toán tỉ lệ thuận với n. Tức là độ phức tạp tính toán là Θ(n). Dùng quy tắc cộng và quy tắc lấy max ta suy ra độ phức tạp tính toán của giải thuật trên là Θ(n).

+ Còn nếu viết theo sơ đồ sau:



Độ phức tạp tính toán trong trường hợp này là Θ(1), thời gian tính toán không phụ thuộc vào n.

3.7 Phép toán tích cực

- Dựa vào những nhận xét đã nêu ở trên về các quy tắc khi đánh giá thời gian thực hiện giải thuật, ta chú ý đặc biệt đến một phép toán mà ta gọi là phép toán tích cực trong một đoạn chương trình. Đó là một phép toán trong một đoạn chương trình mà số lần thực hiện không ít hơn các phép toán khác.

- Xét 2 đoạn chương trình tính ex bằng công thức gần đúng:



4. Độ phức tạp tính toán với tình trạng dữ liệu vào

Có nhiều trường hợp, thời gian thực hiện giải thuật không phải chỉ phụ thuộc vào kích thước dữ liệu mà còn phụ thuộc vào tình trạng của dữ liệu đó nữa. Chẳng hạn thời gian sắp xếp một dãy số theo thứ tự tăng dần mà dãy đưa vào chưa có thứ tự sẽ khác với thời gian sắp xếp một dãy số đã sắp xếp rồi hoặc đã sắp xếp theo thứ tự ngược lại. Lúc này, khi phân tích thời gian thực hiện giải thuật ta sẽ xét trường hợp tốt nhất, trường hợp trung bình và trường hợp xấu nhất.

- Phân tích thời gian thực hiện giải thuật trong trường hợp xấu nhất (worst-case analysis): với một kích thước dữ liệu n, tìm T(n) là thời gian lớn nhất khi thực hiện giải thuật trên mọi bộ dữ liệu kích thước n và phân tích thời gian thực hiện giải thuật dựa trên hàm T(n).

- Phân tích thời gian thực hiện giải thuật trong trường hợp tốt nhất (best-case analysis): với một kích thước dữ liệu n, tìm T(n) là thời gian ít nhất khi thực hiện giải thuật trên mọi bộ dữ liệu kích thước n và phân tích thời gian thực hiện dựa trên hàm T(n).

- Phân tích thời gian trung bình thực hiện giải thuật (average-case analysis): giả sử rằng dữ liệu vào tuân theo một phân phối xác suất nào đó (chẳng hạn phân bố đều nghĩa là khả năng chọn mỗi bộ dữ liệu vào là như nhau) và tính toán giá trị kỳ vọng (trung bình) của thời gian chạy cho mỗi kích thước dữ liệu n (T(n)), sau đó phân tích thời gian thực hiện giải thuật dựa trên hàm T(n).

Khi khó khăn trong việc độ phức tạp tính toán trung bình (bởi việc xác định T(n) trung bình thường phải dùng tới những công cụ tính toán phức tạp), người ta thường chỉ đánh giá độ phức tạp tính toán trong trường hợp xấu nhất.

Không nên lẫn lộn các cách phân tích trong trường hợp xấu nhất, trung bình, và giá tốt nhất với các ký pháp biểu diễn độ phức tạp tính toán, đây là 2 khái niệm hoàn toàn phần biệt.

Trên phương diện lý thuyết, đánh giá bằng ký pháp Θ(.) là tốt nhất, tuy vậy việc đánh giá bằng ký pháp Θ(.) đòi hỏi phải đánh giá bằng cả ký pháp O(.) lẫn Ω(.). Dẫn tới việc phân tích thuật toán khá phức tạp, gần như phải biểu diễn chính xác thời gian thực hiện giải thuật qua các hàm giải tích. Vì vậy trong những thuật toán người ta thường dùng ký pháp T(n) = O( f(n)).

5. Chi phí thực hiện thuật toán.

- Khái niệm độ phức tạp thuật toán đặt ra không chỉ dùng để đánh giá chi phí thực hiện một giải thuật về mặt thời gian mà là để đánh giá chi phí thực hiện giải thuật nói chung, bao gồm cả chi phí về thời gian ( lượng bộ nhớ cần sử dụng).

- Thông thường:
Nếu ta đánh giá được độ phức tạp tính toán của một giải thuật qua ký pháp Θ, có thể coi phép đánh giá này là chủ chặt và không cần đánh giá qua các ký pháp khác nữa.
Nếu không:

+ Để nhấn mạnh tính “tốt” của một giải thuật, các ký pháp O, o thường được sử dụng. Nếu đánh giá được qua O thì không cần đánh giá qua o. Ý nói: chi phí thực hiện thuật toán tối đa là …, ít hơn….

+ Đề cập đến tính toán “tồi” của một giải thuật, các ký pháp Ω, ω thường được sử dụng. Nếu đánh giá được qua Ω thì không cần đánh giá qua ω. Ý nói chi phí thực hiện thuật toán tối thiểu là…, cao hơn…

(Theo A.K.A DSAP Textbox)

[Ngôn ngữ lập trình] 8 ngôn ngữ lập trình được chú ý đặc biệt

Thế giới của các ngôn ngữ lập trình (NNLT) đa dạng và có chiều sâu, mỗi NNLT có ưu thế ở từng mảng như Pascal, C, C++, Java, C#, ... về lập trình hệ thống, PHP, .Net dành cho Web, SQL, Oracle dành cho cơ sở dữ liệu… Đôi khi, các lập trình viên sẽ hướng đến ngôn ngữ C++ hay các ngôn ngữ thông dụng khác để lập trình các trò chơi đòi hỏi tác vụ hiệu suất cao.

- Sự nở rộ của các nền tảng và ứng dụng mới chuyển từ máy tính để bàn sang thiết bị di động và ứng dụng đám mây hay Web. Nhiều NNLT mới đã thúc đẩy sự xuất hiện của Python, Ruby, CUDA… để giúp lập trình viên (LTV) dễ dàng hơn trong việc phát triển ứng dụng. Dần dần, các ngôn ngữ mới đã có nhiều cải thiện đáng kể khi các hàm, dòng lệnh… đến gần với ngôn ngữ tự nhiên của con người hơn. Vì vậy, để có thể bắt kịp với xu hướng phát triển phần mềm, các lập trình viên phải tìm hiểu NNLT mới vừa theo đuổi niềm đam mê vừa có được vị trí công việc tốt hơn cho tương lai. Bên cạnh đó, các công ty phần mềm cũng phải chọn lựa hướng tiếp cận ngôn ngữ để cho ra đời những sản phẩm có thể mang tính cạnh tranh cao, phù hợp với nhu cầu thị trường.

- Dưới đây là 8 ngôn ngữ lập trình đang có chiều hướng thích ứng nhanh trong các tổ chức, doanh nghiệp. 8 NNLT được đề cập không có ngôn ngữ nào vượt trội hẳn, đa số chúng kế thừa những ngôn ngữ đi trước.

1. Python

- Có 2 nhóm người yêu thích Python, đó là những người không thích sử dụng cặp ngoặc nhọn { } được dùng để bao bọc một khối lệnh và nhóm còn lại là các nhà khoa học. Ví dụ, trong C/C++ dùng cặp { } để bao một khối lệnh trong lúc Python sẽ thụt các câu lệnh vào trong khối sâu hơn (về bên phải) so với các câu lệnh gốc chứa nó.

// Đoạn chương trình viết bằng C\C++
#include <math.h> 
 //... 
 delta = b * b – 4 * a * c; 
 if (delta > 0) { 
  // Khối lệnh mới bắt đầu 
   x1 = (- b + sqrt(delta)) / (2 * a); 
   x2 = (- b - sqrt(delta)) / (2 * a); 
   printf("Phuong trinh co hai nghiem phan biet:\n"); 
   printf("x1 = %f; x2 = %f", x1, x2); 
//...
Đoạn mã trên viết lại bằng Python: 

import math 
 #... 
 delta = b * b – 4 * a * c 
 if delta > 0: 
   # Khối lệnh mới, thụt vào đầu dòng 
   x1 = (- b + math.sqrt(delta)) / (2 * a) 
   x2 = (- b – math.sqrt(delta)) / (2 * a) 
   print "Phuong trinh co hai nghiem phan biet:" 
   print "x1 = ", x1, "; ", "x2 = ", x2

- Trong vài năm trở lại đây, Python là ngôn ngữ đầu tiên có mặt trên ứng dụng App Engine của Google – một dấu hiệu cho thấy Python là loại cấu trúc có tính linh hoạt trên điện toán đám mây. App Engine là một dịch vụ cho phép bạn triển khai ứng dụng web của mình trên kiến trúc của Google. Hiện nay App Engine đang hỗ trợ các ứng dụng web viết bằng Python và Java. Người dùng có thể viết ứng dụng bằng ngôn ngữ Python theo các giao diện lập trình ứng dụng (API) mà Google cung cấp.

- Python còn khá phổ biến trong các phòng thí nghiệm khoa học, theo người sáng lập ra Python là Guido von Rossum, các nhà khoa học luôn cần sáng tạo không ngừng khi cố gắng đưa ra kết quả, vì vậy họ cần tìm kiếm một ngôn ngữ động có thể đưa ra kết quả nhanh chóng và gần như thấy kết quả tức thời.


- Một lợi thế của Python là cung cấp khá nhiều thư viện nên được các nhà khoa học ưa chuộng. NumPy và SciPy chỉ là 2 trong số những thư viện đáng chú ý được phát triển trong dự án nguồn mở phù hợp với các tính toán khoa học.

- SciPy là một thư viện mã nguồn mở của các công cụ khoa học dành cho Python. SciPy được xây dựng trên thư viện NumPy, được đóng gói từ nhiều mô-đun khoa học và kĩ thuật cấp cao. SciPy cung cấp các mô-đun về thống kê, tối ưu hóa, tích phân, đại số tuyến tính, xử lý tín hiệu, xử lý hình ảnh, thuật toán di truyền, các hàm đặc biệt… SciPy được phát triển đồng thời trên cả Linux và Windows. Ngoài ra, SciPy cũng được biên dịch và chạy thành công trên Mac, Solaris, FreeBSD và hầu hết các nền tảng khác có cài đặt Python.

- Không chỉ lĩnh vực nghiên cứu khoa học dùng ngôn ngữ Python mà các công ty dược phẩm cũng như nhiều công ty ở phố tài chính Wall Street cũng khai thác Python. Các công ty ở phố Wall Street chủ yếu dựa vào thuật toán Python để phân tích các con số toán học và họ cũng thuê những nhà khoa học ở trường đại học để phân tích các con số qua dòng lệnh trên Python.

2. Ruby

- Ruby là NNLT mã nguồn mở thích hợp cho các ứng dụng truy xuất cơ sở dữ liệu, còn Rubyon Rails là 1 khung làm việc (framework) cho ứng dụng viết bằng ngôn ngữ Ruby, nó cung cấp các thư viện cơ bản, hỗ trợ cho ứng dụng Ruby.

- Ruby giúp dẫn lối cho doanh nghiệp khai thác sức mạnh của Web 2.0. Một ý tưởng mới của Ruby là dùng quy tắc “convention over configuration” nghĩa là thay vì phải thiết lập môi trường hay những loại tương tự như thế, tất cả những gì bạn cần làm là gọi đúng tên (việc đặt tên cho các biến sẽ tương ứng với tên biến có trong cột của cơ sở dữ liệu một cách tự động), ví dụ có một class gọi là User thì tập tin của class này sẽ có tên /models/user.rb (người dùng có thể thay đổi tên khác), và controller của model này sẽ được mặc định là /controllers/user_controller.rb và helper của model này sẽ là /helpers/user_helper.rb, các view của model sẽ được đặt trong thư mục/views/users, và bảng trong cơ sở dữ liệu sẽ được hiểu là ‘user’.

- Ruby on Rails xử lý các định dạng trong các bảng của cơ sở dữ liệu cũng như các quyết định về thông tin gì sẽ hiển thị. Sử dụng theo quy ước đặt tên của Ruby on Rails, sẽ giúp mã lệnh được phác thảo một cách dễ dàng và hạn chế sự trùng lắp.

- Nhiều trang web viết bằng ngôn ngữ Ruby chạy trên nền JRuby, đó là một phiên bản viết bằng Java dựa trên máy ảo Java (Java Virtual Machine – JVM). Người dùng sử dụng JRuby có thể tận dụng tất cả thế mạnh của JVM và có thể triển khai tùy theo cấp độ cho nhiều người dùng đồng thời.

3. MATLAB

- MATLAB được xây dựng trên cơ sở toán học để giải quyết các hệ thống của phương trình tuyến tính, là ngôn ngữ nhận được nhiều quan tâm của những cơ quan có khối lượng dữ liệu đồ sộ cần phân tích. Nhiều kỹ thuật thống kê có tính phức tạp cao, như các dữ liệu thu thập từ quảng cáo, danh mục bài hát hay trang web đòi hỏi nhiều các thuật toán thì MATLAB sẽ là sự lựa chọn phù hợp.

- MATLAB sẽ góp mặt trong những số liệu tính toán thống kê mang tính khổng lồ, chẳng hạn liệt kê các trang web có số người xem nhiều nhất hay thống kê con số để biết mọi người có khuynh hướng mua sắm nhiều vào đầu tuần hay ngày thứ Sáu?

- MathWorks là công ty phát triển MATLAB, cung cấp khá đa dạng các bài nghiên cứu được đúc kết từ kinh nghiệm của các nhà lập trình trong các câu trả lời về thống kê. Cụ thể, Toyota Racing có kế hoạch phân tích thử nghiệm các ống thổi khí động học hay Viện Biodiagnostics của Canada đang tìm kiếm cách điều trị mang tính khả thi nhất cho bệnh bỏng.

- Ngoài MATLAB, còn có một số lựa chọn mã nguồn mở khác gồm Octave, Scilab, Sage và PySci. Tất cả các công cụ này sẽ trợ giúp cho việc phân tích thống kê có độ phức tạp cao mà hiện được nhiều công ty quan tâm – các công ty muốn hiểu nhiều hơn về nhu cầu của khách hàng và biết họ cần gì trong tương lai.

4. JavaScript

- JavaScript là một NNLT kịch bản dựa trên đối tượng, được dùng rộng rãi cho web. Về cú pháp, Javascript cũng tương tự như C, Perl và Java… ví dụ mệnh đề lặp if, while, for.

- JavaScript được sử dụng nhằm bổ sung tính tương tác cho các trang HTML. JavaScript có thể đáp ứng các sự kiện như tải hay loại bỏ các form, do đó khả năng này cho phép JavaScript trở thành một ngôn ngữ script động. Ngoài ra, Javascript có thể được dùng để xác nhận dữ liệu người dùng nhập vào trước khi được chuyển đến máy chủ (server) và giúp trang web của bạn tương tác với người dùng uyển chuyển hơn.

- Khá nhiều lập trình viên dùng JavaScript để thiết kế trang web động và một số hiệu ứng hình ảnh thông qua DOM (Document Object Model). JavaScript được dùng để thực hiện một số tác vụ không thể thực hiện được trên HTML như kiểm tra thông tin nhập vào, tự động thay đổi hình ảnh… Ví dụ, công ty AppJet sử dụng phiên bản Java hỗ trợ JavaScript bằng cách sử dụng Rhino để đơn giản hóa mã lệnh phía máy chủ. Nhưng năm 2009, Google đã tiếp quản AppJet.

- Ngoài ra, vẫn còn nhiều ứng dụng mới dùng JavaScript, chẳng hạn CouchDB là thư viện nguồn mở do công ty Couch.io hậu thuẫn, sử dụng 2 chức năng JavaScript: Map và Reduce, không sử dụng các truy vấn SQL.

5. R

- R là NNLT dành cho tính toán và phân tích thống kê, có tên gọi ban đầu là S. Ngôn ngữ này lấy cảm hứng từ Scheme với những tính năng mới bổ sung dành cho đồ họa thống kê. R chứa nhiều kỹ thuật thống kê: mô hình hóa tuyến tính, phân tích chuỗi thời gian, phân loại, phân nhóm, đồ họa… Nhiều hệ thống trong R được viết bằng chính ngôn ngữ của nó, giúp cho người dùng dễ theo dõi các giải thuật. Để thực hiện công việc chuyên về tính toán, R có thể liên kết được với ngôn ngữ C, C++ để có thể được gọi trong khi chạy.

- Do được thừa hưởng từ S, R có nền tảng lập trình hướng đối tượng khá mạnh so với các ngôn ngữ tính toán thống kê khác. Một điểm mạnh khác của R là nền tảng đồ họa của nó, có thể tạo ra những đồ thị chất lượng cao cùng các biểu tượng toán học. Chẳng hạn, sử dụng ngôn ngữ R để phân tích các mô hình thời tiết nhằm tìm kiếm những nơi tốt nhất để xây dựng trạm máy phát điện chạy bằng sức gió.

6. Erlang

- Erlang là NNLT nguồn mở được phát triển bởi các nhà khoa học tại phòng thí nghiệm máy tính Ericsson.

- Điểm khác biệt của Erlang so với các ngôn ngữ khác là dành để thiết kế các ứng dụng chạytrên máy tính có nhiều lõi. Ưu thế của Erlang là khả năng chạy ứng dụng song song, nghĩa là nếu máy tính có càng nhiều lõi thì tốc độ chương trình càng nhanh. Tuy nhiên, cần phân biệt giữa quá trình chạy ứng dụng song song trên nhiều lõi với chạy song song dựa trên sự phân chia xử lý theo thời gian CPU máy tính. Erlang tạo ra các ứng dụng chạy song song trên nhiều lõi còn các ngôn ngữ khác (như Java, C, …) lại tạo ra các ứng dụng chạy song song theo kiểu phân chia theo thời gian.



- Ngôn ngữ này kết hợp lập trình chức năng với máy ảo (có thể biên dịch xuống mã máy). Cấu trúc của NNLT Erlang giúp lập trình viên xây dựng ứng dụng dễ dàng hơn để phân phối trên nhiều lõi và nhiều máy. Ví dụ, Erlang được triển khai thực tế trên các máy chủ và CouchDB và được dùng trong các ứng dụng công nghiệp và thương mại.

7. Cobol

- Grace Murray Hopper, là người nổi tiếng trong việc phát hiện lỗi trên những chiếc máy tính lớn (mainframe) đầu tiên, đã phát triển ngôn ngữ Cobol thuộc dạng lâu đời nhất, có từ năm 1959, ngôn ngữ này đã trải qua hàng trăm lần cải tiến kể từ đó. Mục đích của Cobol là hướng đến thương mại, tài chính và các hệ quản lý của các doanh nghiệp cũng như chính phủ.

- Cobol có nhiều chức năng xử lý tập tin, nhất là theo cách xử lý hàng loạt (batch processing), hỗ trợ lập trình hướng đối tượng và các tính năng lập trình hiện đại khác. Đây cũng là ngôn ngữ chạy nhiều nhất trên các máy tính lớn của doanh nghiệp.

- Những lập trình viên thích Cobol vì cú pháp của nó có khuynh hướng gần giống ngôn ngữ tự nhiên với những danh từ và động từ để có thể hình thành ra một mệnh đề và câu – một kỹ thuật có thể gợi nhớ đến ngôn ngữ Ruby. Mới đây, IBM đã giới thiệu bản phát hành mới nhất là Enterprise Cobol 4.2.

- Thực tế, ngôn ngữ Cobol rất ít được giảng dạy trong nhà trường, nhưng nhiều tập đoàn vẫn chú trọng đầu tư. Một nghiên cứu gần đây của Dice.com cho thấy 580 việc làm liên quan đến ngôn ngữ Cobol và 1070 dành cho Ruby.

8. CUDA

- CUDA là kiến trúc tính toán song song giúp các LTV có thể khai thác sức mạnh của các nhân xử lý tính toán đồ họa mà trước đây do CPU giữ vai trò then chốt. Các lập trình viên có thể giao tiếp với CUDA thông qua khá nhiều NNLT khác nhau, trong đó có C, C++, Fortran, Java… Kết quả là ngày càng nhiều ứng dụng có thể sử dụng CUDA để xử lý độc lập mà không cần phải tiêu tốn nhiều tài nguyên CPU như trước đây. Nhờ sức mạnh tính toán này, thị trường card đồ họa được mở rộng không chỉ dành riêng cho các game thủ hay những chuyên gia đồ họa.

- Thực chất, CUDA không phải là một ngôn ngữ mà chỉ là phần mở rộng của ngôn ngữ C. Tuy nhiên, một số lập trình viên đang bắt đầu khám phá các kiến trúc song song bên trong của CUDA để đưa vào các trò chơi trên máy tính.

- CUDA có thể được dùng mô phỏng và tính toán thống kê ở quy mô lớn, hỗ trợ tính toán trong các chip xử lý đồ họa (GPU – Graphics Processing Unit) của NVIDIA thông qua các NNLT phổ biến. Ngoài ra, CUDA cũng được sử dụng trong tính toán sinh học, xử lý khối lượng dữ liệu lớn và nhiều lĩnh vực khác.

(Tham khảo pcworld.com.vn)

[Java] Ví dụ về lớp trừu tượng và phương thức trừu tượng (abstract) - Tính chu vi, diện tích các hình cơ bản [Lập trình hướng đối tượng - OOP]

Xây dựng Project theo mô hình kế thừa sau:

[NetBean]
1. Xây dựng Project như sau:

2. Code:
//-------------------------------------------
//abstract class HinhHoc
//-------------------------------------------
package vd_abstract_150114;
public abstract class HinhHoc {
    String tenHinh;
    // Constructor
    public HinhHoc(String tenHinh){
        this.tenHinh=tenHinh;
    }
    // Tinh chu vi
    abstract float ChuVi();
    // Tinh dien tich
    abstract float DienTich();
    // In ket qua
    void InKQ(){
        System.out.print("\n + Ten hinh: "+ tenHinh);
        System.out.print("\n  - Chu vi: "+ ChuVi());
        System.out.print("\n  - Dien tich: "+ DienTich());
    }
}

//-------------------------------------------
// class HinhVuong
//-------------------------------------------

package vd_abstract_150114;
public class HinhVuong extends HinhHoc{
    float a;
    // constructor
    public HinhVuong(String tenHinh,float a){
        super(tenHinh);
        this.a=a;
    }
    // Chu vi
    float ChuVi(){
        return 4*a;
    }
    float DienTich(){
        return a*a;
    }
}

//-------------------------------------------
// class HinhChuNhat
//-------------------------------------------

package vd_abstract_150114;
public class HinhChuNhat extends HinhVuong {
    float b;
    // constructor
    public HinhChuNhat(String tenHinh,float a,float b){
        super(tenHinh,a);
        this.b=b;
    }
    // Chu vi
    float ChuVi(){
        return 2*(a+b);
    }
    // Dien tich
    float DienTich(){
        return a*b;
    }
}


//-------------------------------------------
// class HinhTamGiac
//-------------------------------------------

package vd_abstract_150114;
public class HinhTamGiac extends HinhChuNhat {
    float c;
    // constructor
    public HinhTamGiac(String tenHinh,float a,float b,float c){
        super(tenHinh,a,b);
        this.c=c;
    }
    // chu vi
    float ChuVi(){
        return (a+b+c);
    }
    // dien tich
    float DienTich(){
        float p=ChuVi()/2;
        return (float)Math.sqrt(p*(p-a)*(p-b)*(p-c));
    }
}


//-------------------------------------------
// class HinhTron
//-------------------------------------------

package vd_abstract_150114;
public class HinhTron extends HinhHoc {
    float r;
    final float PI=3.14f;
    // constructor
    public HinhTron(String tenHinh,float r){
        super(tenHinh);
        this.r=r;
    }
    // chu vi
    float ChuVi(){
        return 2*PI*r;
    }
    // dien tich
    float DienTich(){
        return PI*r*r;
    }
}


//-------------------------------------------
// class VD_abstract_150114

/* http://www.laptirnhmaytinh.net  */

package vd_abstract_150114;

import java.util.Scanner;

public class Vd_abstract_150114 {
    public static void main(String[] args) {
        float a,b,c,r;
        Scanner inp=new Scanner(System.in);
        HinhHoc hv,hcn,tg,ht;
        // Hinh vuong
        try{
            do{
                System.out.print("\n + Nhap canh hinh vuong: ");
                a=inp.nextFloat();
                if(a<=0)
                    System.out.println("\n >> Nhap lai !");
            }while(a<=0);
            // khoi tao doi tuong
            hv=new HinhVuong("Hinh vuong",a);
            hv.InKQ();
        }catch(Exception e){
            System.out.println("\n * Co loi xay ra ! Ma loi: "+e.toString());
        }
        // Hinh chu nhat
        try{
            do{
                System.out.print("\n + Nhap canh hinh chu nhat (a,b): ");
                a=inp.nextFloat();
                b=inp.nextFloat();
                if (a<=0||b<=0)
                    System.out.println("\n >> Nhap lai !");
            }while(a<=0||b<=0);
            // khoi tao doi tuong
            hcn=new HinhChuNhat("Hinh chu nhat",a,b);
            hcn.InKQ();
        }catch(Exception e){
            System.out.println("\n * Co loi xay ra ! Ma loi: "+e.toString());
        }
        // Hinh tam giac
        try{
            do{
                System.out.print("\n + Nhap canh hinh tam giac (a,b,c): ");
                a=inp.nextFloat();
                b=inp.nextFloat();
                c=inp.nextFloat();
                if (a<=0||b<=0||c<=0||a+b<=c||a+c<=b||b+c<=a)
                     System.out.println("\n >> Nhap lai !");
            }while(a<=0||b<=0||c<=0||a+b<=c||a+c<=b||b+c<=a);
            // khoi tao doi tuong
            tg=new HinhTamGiac("Hinh tam giac",a,b,c);
            tg.InKQ();
        }catch(Exception e){
            System.out.println("\n * Co loi xay ra ! Ma loi: "+e.toString());
        }
        // Hinh tron
        try{
            do{
                System.out.print("\n + Nhap ban kinh hinh tron: ");
                r=inp.nextFloat();
                if(r<=0)
                   System.out.println("\n >> Nhap lai !");
            }while(r<=0);
            // khoi tao doi tuong
            ht=new HinhTron("Hinh tron",r);
            ht.InKQ();
        }catch(Exception e){
            System.out.println("\n * Co loi xay ra ! Ma loi: "+e.toString());
        }
    }        
}



Danh mục bài viết