ĐỀ CƯƠNG ÔN TẬP
MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN
Lý thuyết:
Thuật toán là gì? Tính chất, cách biểu diễn, độ phức tạp?
Thuật toán là cách thức, quy trình để hoàn thành 1 công việc cụ thể xác định nào đó
Tính chất:
Tính đúng đắn: Thuật toán cần phải đảm bảo cho một kết quả đúng sau khi thực hiện đối với các bộ dữ liệu đầu vào.
Tính dừng: Thuật toán cần phải đảm bảo sẽ dừng sau 1 số bước hữu hạn bước.
Tính xác định: Các bước của thuật toán phải được hiểu rõ ràng, cụ thể, tránh gây nhập nhằng hoặc nhầm lẫn đối với người đọc và hiểu, cài đặt thuật toán.
Tính hiệu quả: thuật toán được xem là hiệu quả nếu như nó có khả năng giải quyets hiệu quả bài toán đặt ra trong thời gian hoặc các điều kiện cho phép trên thực tế đáp ứng được yêu cầu của người dùng
Tính phổ quát: thuật toán có thể giải quyết được 1 lớp các bài toán tương tự
Cách biểu diễn: có 2 cách biểu diễn thuật toán:
Mô tả các bước thực hiện của thuật toán.
Sử dụng sơ đồ giải thuật
Độ phức tạp:
Các tiêu chí đánh giá thuật toán:
Thuật toán đơn giản, dễ hiểu, dễ cài đặt.
Dựa vào thời gian thực hiện và tài nguyên mà thuật toán sử dụng để thực hiện trên các bộ dữ liệu.
Thế nào là bài toán tìm kiếm? (định nghĩa, đầu vào, đầu ra, mục đích, …)
Tìm kiếm là 1 trong những vấn đề thuộc lĩnh vực nghiên cứu của ngành khoa học máy tính và được ứng dụng rộng rãi trên thực tế.
Chúng ta quan tâm đến bài toán tìm kiếm trên 1 mảng, hoặc 1 danh sách các phần tử cùng kiểu
Kết quả tìm kiếm là vị trí của phần tử thỏa mãn điều kiện tìm kiếm: có trường khóa bằng với 1 giá trị khóa cho trước. Từ vị trí này chúng ta có thể truy cập tới các thông tin khác được chứa trong trường dữ liệu của phần tử tìm thấy. Nếu kết quả là không tìm thấy thì giá trị trả về sẽ được gán cho một giá trị đặc biệt nào đó tương đương với việc không tồn tại phần tử nào có vị trí đó: chẳng hạn – 1 với mảng và NULL với danh sách liên kết.
Có nhiều thuật toán tìm kiếm như: tìm kiếm vét cạn, tìm kiếm tuần tự, tìm kiếm nhị phân, v.v.v..v.
Trình bày thuật toán tìm kiếm tuyến tính (các bước, sơ đồ thuật toán, độ phức tạp, …)
Các bước:
Duyệt qua các phần tử của mảng
Nếu tìm thấy phần tử có khóa bằng khóa tìm kiếm thì trả về vị trí của phần tử đó. Ngược lại không tìm thấy thì trả về -1
Sơ đồ thuật toán:



Độ phức tạp thuật toán trong trường hợp trung bình và tồi nhất: O(n).
Trong trường hợp tốt nhất thuật toán có độ phức tạp O(1).
Bài toán sắp xếp là gì? (định nghĩa, đầu vào, đầu ra, mục đích, …)
Sắp xếp là 1 quá trình xếp đặt các bản ghi của 1 file theo một thứ tự nào đó. Việc xếp đặt này được gọi là khóa sắp xếp (key). Hầu hết các thuật toán sắp xếp được gòi là các thuật toán sắp xếp so sánh: chúng sử dụng 2 thao tác cơ bản là so sánh và đổi chỗ (swap) các phần tử cần sắp xếp.
Các bài toán sắp xếp đơn giản được chia thành: sắp xếp trong (dữ liệu cần sắp xếp được lưu đầy đủ rong bộ nhớ trong để thực hiện thuật toán sắp xếp), sắp xếp ngoài (Dữ liệu sắp xếp có kích thước quá lớn và không thể lưu vào bộ nhớ trong để sắp xếp, các thao tác truy cập dữ liệu cũng mất nhiều thời gian hơn), sắp xếp gián tiếp (khi kích thước các bản ghi lớn và việc hoán đổi các bản ghi là rất toán kém)
Trình bày thuật toán sắp xếp chọn trực tiếp (mô tả thuật toán, cài đặt, độ phức tạp, ví dụ)
Mô tả thuật toán: Tìm phần tử lớn nhất (nhỏ nhất), đặt nó vào đúng vị trí và sau đó sắp xếp phần còn lại của mảng.
Sơ đồ thuật toán:



Cài đặt bằng C:

Độ phức tạp thuật toán: O(n2)
Ví dụ:


Trình bày thuật toán sắp xếp chèn (mô tả thuật toán, cài đặt, độ phức tạp, ví dụ)
Thuật toán dựa vào thao tác chính là chèn mỗi khóa vào một dãy con đã được sắp xếp của dãy cần sắp xếp. Phương pháp này thường được sử dụng trong việc sắp xếp các cây bài trong quá trình chơi bài.
Sơ đồ thuật toán:




Cài đặt thuật toán bằng