Giới thiệu tổng quan về cấu trúc dữ liệu (Advanced data structure)

Trong phần giới thiệu này sẽ trình bày ba vấn đề:

  1. Thuật toán và các vấn đề liên quan (Algorithms and related issues).
  2. Giới thiệu về phân tích và thiết kết thuật toán. (Algorithms: analysis & disign).
  3. Ước lượng độ phức tạp của thuật toán (Estimations for complexity).

———————————————————————————————————————–

1. Thuật toán và các vấn đề liên quan:

a. Định Nghĩa:

Thuật toán (algorithms), còn gọi là giải thuật, là một tập hợp các phương cách được định nghĩa rõ ràng cho việc hoàn tất một số việc từ một trạng thái ban đầu cho trước, khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như dự đoán.

Nói cách khác, thuật toán là một bộ quy tắc hay quy trình cụ thể nhằm giải quyết vấn đề trong một số bước hữu hạn, hoặc cung cấp một kết quả từ một dữ kiện đưa vào.

Giai thuat

Trong nghiên cứu, thuật toán đôi khi còn được gọi là Algorithmics. Algorithmmics đã được công nhận là nền tản của  Khoa học máy tính.

Algorithmics is more than a branch of computer science . It is the core of computer science, and, in all fairness, can be said relevant to most of science, business, and technology ”.

[ Algorithmics: the Spirit of Computing.David Harel 1992]

b. Một số vấn đề nổi tiếng liên quan đến giải thuật:

        • Sắp xếp (sorting).
        • Tìm kiếm (searching).
        • Tìm đường đi ngắn nhất trên đồ thị (sortest path in a graph).
        • Tìm cây khung nhỏ nhất (mininum spanning tree).
        • Kiểm tra tính nguyên tố (primality testing).
        • Bài toán người bán hàng (traveling salesman prob).
        • Knapsack problem.
        • Đánh Cờ  (Chess).
        • Bài toán tháp Hà Nội (Tower of Hanoi).
        • Program termination.

C. Các vấn đề cơ bản liên quan đến thuật toán:

–  Làm Thế nào để thiết kế thuật toán (How to design algorithms).

–  Làm thế nào để thuật toán nhanh, chính xác (How to express algorithms).

–  Kiểm tra tính đúng đắn (Proving correctness).

–  Tính hiệu quả (Efficiency):

+  Phân tích lý thuyết (Theoretical analysis).

+  Phân tích dựa trên kinh nghiệm (Empirical analysis).

–  Tối ưu (Optimality).

D. Sau khi học xong phần này phải làm được các bài tập dưới đây:

1.  Viết một chương trình tìm ước chung lớn nhất của 2 số nguyên. (Gợi ý sử dụng giải thuật Euclic)

2.  Viết một chương trình in ra dãy số nguyên tố tới n (với n là số nguyên cho trước).

3. Viết chương trình kiểm tra xem n điểm nhập vào có nằm trên cùng một đường tròn.

4. Thiết kế một thuật toán đơn cho vấn đề trùng khớp chuỗi (string matching).


2. Thuật toán: Phân Tích & Thiết Kế:

a. Chiến lược thiết kế thuật toán:

Một kỹ chiến lược (kỹ thuật, mô hình) thiết kế thuật toán là một cách tiếp cận chung để giải quyết vấn đề thuật toán được áp dụng đối với một loạt các vấn đề từ các vùng khác nhau của máy tính.

Một số kỹ thuật thiết kế các thuật toán kinh điển như:

–  Kỹ thuật cưỡng chế (Brute Force).

–  Kỹ thuật chia để trị (Devide and conquer).

–  Kỹ thuật chuyển đổi để trị (Transform and conquer).

–  Phương pháp quy hoạch động (Dynamic programming).

–  Phương pháp tham lam (Greedy approach).

–  Phương pháp nhánh lân cận (Bracktracking and branch and bound).

–  Phương pháp cân bằng không gian và thời gian (Space and time tradeoffs).

b. Làm việc với thuật toán như thế nào.

–  Tính dừng (Finiteness): chấm dứt sau một số hữu hạn các bước.

–  Tính xác định (Definiteness): chặt chẽ và quy định rõ ràng.

–  Đầu vào (input): đầu vào hợp lệ được quy đỉnh rõ ràng.

–  Đầu ra (output): có thể tạo đầu ra chính xác cho một đầu vào hợp lệ.

–  Tính hiệu quả (Effectiveness): các bước được triển khai đầy đủ và đơn giản.

C. Nguyên tắc cơ bản của thuật toán để giải quyết các vấn đề:

–  Phải hiểu rõ vấn đề.

–  Chứng thực khả năng của các thiết bị tính toán.

–  Lựa chọn chính xác giữa các vấn đề mang tính gần đúng.

–  Quyết định cấu trúc dữ liệu phù hợp.

–  Kỹ năng thiết kế thuật toán cần có.

–  Xác định phương thức của thuật toán.

–  Chứng minh tính chính xác của thuật toán.

–  Phân tích thuật toán.

–  Mã hóa thuật toán (coding an algorithm).

D. Các định nghĩa:

–  List:  array (mảng), linked list (danh sách liên kết), string (chuỗi).

–  Stack graph.

– Queue tree.

– Priority queue (hàng đợi ưu tiên).

– Set and Dictionary.



 

 

 

 

 

 

 

 

 

Advertisements

About thanhcuong1990

Handsome and talent!! ^^
This entry was posted in Data structure and Algorithms and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s