Thuật toán - Tổng quan

Thuật toán là khái niệm cơ sở của Toán học và Tin học.
Thuật toán là tập hợp hữu hạn các bước để giải bài toán, phương pháp để thể hiện lời giải của vấn đề.

Các đặc trưng của thuật toán

• Tính xác định: Các thao tác của thuật toán phải xác định, không được nhập nhằng, mơ hồ để có thể dễ dàng cài đặt trên máy tính.
• Tính dừng: Thuật toán phải dừng sau một số hữu hạn các bước.
• Tính đúng đắn: Thuật toán phải cho kết quả dúng theo yêu cầu của bài toán đặt ra.
• Tính phổ dụng: Thuật toán có thể được ử dụng lại để giải một lớp bài toán tương tự.
• Tính hiệu quả: Thuật toán cần tối ưu về sử dụng bộ nhớ và đáp ứng yêu cầu của bài toán trong khoảng thời gian  ngắn nhất có thể. Thực tế rất khó để được 2 yêu cầu này trong cùng một thuật toán.

Các công cụ biễu diễn thuật toán

Ngôn ngữ tự nhiên

Là ngôn ngữ liệt kê các bước, mô tả thuật toán theo ngôn ngữ tự nhiên của con người.

Ví dụ: Thuật toán xác định số lớn nhất trong 3 số nguyên

• Bước 1: Gọi a, b, c là ba biến lưu trữ các giá trị nguyên cho trước (nhập từ bàn phím).
• Bước 2: Gọi Max là biến lưu giá trị lớn nhất trong 3 số nguyên và giả sử cho a giá trị lớn nhất.
• Bước 3: Lần lượt so sánh giá trị của Max với 2 biến còn lại. Nếu giá trị của Max nhỏ hơn bất kỳ biến nào thì gán giá trị đó cho biến Max.
• Bước 4: Xuất kết quả giá trị biến Max ra màn hình.

Lưu đồ thuật toán

Lưu đồ thuật toán còn gọi là sơ đồ khối: là công cụ cho phép biểu diễn một cách trực quan. Thường chỉ dùng công cụ lưu đồ cho thuật toán tương đối ngắn, có thể biểu diễn tỏng một trang giấy.
Các hình cơ bản sử dụng trong lưu đồ:

Hình oval để biểu diễn điểm xuất phát và kết thúc.

Hình chữ nhật mô tả một hay nhiều chỉ thị máy cần thực hiện.

Hình bình hành mô tả thao tác nhập / xuất dữ liệu.

Hình thoi mô tả sự rẻ nhánh, lựa chọn, phép kiểm tra điều kiện.

 Mũi tên chỉ hướng lưu chuyển của các thao tác.

Mã giả (Pseudo code) gần giống như ngôn ngữ tự nhiên, nhưng có sử dụng các cấu trúc chuẩn hóa (khai báo biến, chú thích, cấu trúc, điều khiển, ...) do người thiết kế quy định.

Ngôn ngữ lập trình

Ngôn ngữ lập trình (Programming language) là hệ thống các ký  hiệu cho phép mô tả các quy trình tính toán dưới dạng văn bản.