Để bắt đầu, ta tìm hiểu các vấn đề tính toán nói chung và các thuật toán cần thiết để giải quyết chúng, lấy bài toán sắp xếp làm ví dụ thực tiễn. Chương này cũng nêu một “mã giả” quen thuộc với những bạn đọc đã từng lập trình trên máy tính để nêu cách đặc tả các thuật toán. Sắp xếp chèn [insertion sort], một thuật toán sắp xếp đơn giản, được dùng làm ví dụ mở đầu. Ta sẽ phân tích thời gian thực hiện [running time] của tiến trình sắp xếp chèn, giới thiệu một hệ ký hiệu tập ưung vào cách thức mà thời gian đó tăng lên theo số lượng các mục được sắp xếp. Ta cũng sê tìm hiểu cách tiếp cận “chia để trị” đối với tiến trình thiết kế các thuật toán và dùng nó để phát triển một thuật toán có tên sắp xếp trộn [merge sort]. Phần cuối chương sẽ so sánh hai thuật toán sắp xếp.
Nôm na, thuật toán[algorithm] là m?t thủ tục tính toán được định nghĩa kỹ, sử dụng một giá trị, hoặc tập hợp các giá trị nào đó, làm đầu vào và cho ra một giá trị, hoặc tập hợp các giá trị nào đó, làm kết xuất, Do đó, một thuật toán là một trình tự các bước tính toán biến đổi đầu vào thành kết xuất.
Cũng có thể xem một thuật toán như một công cụ để giải quyết một bài toán thật cụ thể. Phát biểu của bài toán sê chỉ định tổng quát mốì quan hệ nhập/xuât cần thiêt. Thuật toán mô tá một thủ tục tính toán cụ thể để đạt được môi quan hệ nhập/xuât đó.
Để bắt đầu quá trình nghiên cứu các thuật toán, ta sử dụng bài toán sắp xếp một dãy các con số theo thứ tự không giảm [nondecreasing]. Bài toán này thường nảy sinh trong thực tế và cũng là mảnh đất màu mỡ
để giới thiệu nhiều kỹ thuật thiết kế và các công cụ phân tích chuẩn. Dưới đây là cách định nghĩa hình thức bài toán sắp xếp;
Đầu vào: Một dày nsố(a(, a2,..„ aj.
Kết xuất: Một phép hoấn vị (sắp xếp lại) (ax\ứ/,…, a’) của dãy đầu vào
sao cho a* <a* < … <a’.
i 2 ft
Cho một dày đầu vào như (31,41,59, 26, 41, 58), một thuật toán sắp xếp sẽ trả một dãy kết xuất là (26, 31,41, 41, 58, 59). Một dãy đầu vào như vậy được gọi là một minh dụ[instance] của hài toán sắp xếp. Nói chung, một minh dụ của một bài toán bao gồm tất cả mọi đẩu vào (thỏa mọi hạn chế đã đề ra trong phát hiểu của hài toán) cần thiết để tính toán một nghiệm’cho bài toán.
Sáp xếp là một phép toán căn bản trong khoa học máy tính (nhiều chương trình dùng nó như một hước trung gian), và kết quả là nhiều thuật toán sắp xếp tốt đã được phát triển. Thuật toán nào là tốt nhất đôi với một ứng dụng đã cho, điều này tùy thuộc vào số’ lưựng các mục sẽ được sắp xếp, chừng mực mà các mục đó đà được sắp xếp sấn, và loại thiết bị lưu trữ được dùng: hộ nhứ chính, các đĩa, hoặc hăng từ.
Một thuật toán được xem là đúng đắn nếu, với mọi minh dụ đầu vào, nó ngừng với kết xuất đúng. Ta nói rằng một thuật toán đúng giải quyết được hài toán đã cho. Một thuật toán sai có thể không ngưng gì cả trên vài minh dụ đầu vào, hoặc có thể ngưng với đáp án ngoài ý muốn. Trái với dự đoán, các thuật toán sai đôi lúc cũng hữu ích, nếu như có thể kiểm soát mức độ lỗi của chúng. Ta sẽ thây một ví dụ về điều này trong Chương 33 khi nghiên cứu các thuật toán để tìm các sô” nguyên tô” lớn. Tuy nhiên, hình thường ta chỉ quan tâm đến các thuật toán đúng,
Một thuật toán có thể được đặc tả bằng tiếng Anh, như một chương trình máy tính, hoặc thậm chí như một thiết kế phần cứng. Yêu cầu duy nhất đó là phần đặc tả phải mô tả chính xác thủ tục tính toán sẽ phải theo.
Tập sách này sẽ mô tả các thuật toán dưới dạng các chương trình được viết hằng mã giả rất giống vđi c, Pascal, hay Algol. Nếu đãquen với một trong số các ngôn ngữ này, hạn có thể dề dàng đọc các thuật toán ở đây. Sự khấc biệt giữa mã gia và mã “thật” đó là: trong mã giá, ta sử dụng mọi phương pháp hiểu đạt rố ràng và súc tích nhất để đặc tả một thuật toán nhất định. Thỉnh thoảng, phương pháp rỏ rệt nhất là liếng Anh, do đổkhông có gì ngạc nhien nếu hạn gặp một câu hay cụm từ tiếng Anh {mà trong trường hợp thuận tiện chúng tôi sẽ sử dụng tiếng Việt để quý hạn tiện theo doi ND) xen lẫn trong một
đoạn mã “thật”. Một khác biệt nữa giữa mã giả và mà thật đó lù: mà giả thường không dính dáng đên các vân đồ về thiêt kê kỹ thuật phần mềm. Các vân đề như trừu tượng hóa dữ liệu, tính môđun, và điều quản lỗi thường được bỏ qua để chuyển tái chính xác hơn nội dung cốt lõi của thuật toán