Giáo trình Cấu trúc dữ liệu và Giải thuật - Ngành Tin học ứng dụng

Giáo trình về cấu trúc dữ liệu và giải thuật nghề tin học ứng dụng trình độ cao đẳng, biên soạn theo chương trình đào tạo chuẩn, hệ thống hóa kiến thức từ cơ bản đến nâng cao.

• Trường học: Trường Cao Đẳng Nghề Tin Học Ứng Dụng
• Chuyên ngành: Cấu Trúc Dữ Liệu Và Giải Thuật
• Đề tài: Giáo Trình Cấu Trúc Dữ Liệu Và Giải Thuật Nghề Tin Học Ứng Dụng Trình Độ Cao Đẳng
• Loại tài liệu: Giáo Trình

Mục lục chi tiết

• LỜI NÓI ĐẦU
• 1. CHƯƠNG 1: GIẢI THUẬT
• 1.1. Giới thiệu về môn học
• 1.2. Ngôn ngữ diễn đạt
• 1.2.1. Quy tắc về cấu trúc chương trình
• 1.2.2. Ký tự và biểu thức
• 1.2.3. Các câu lệnh (hay các chỉ thị)
• 1.2.4. Chương trình con
• 1.3. Thiết kế giải thuật
• 1.4. Đánh giá giải thuật
• 1.5. Giải thuật đệ quy
• 1.5.1. Định nghĩa
• 1.5.2. Ví dụ về thủ tục đệ quy
• 1.5.2.1. Hàm tính n!
• 1.5.2.2. Dãy số Fibonacci
• 1.5.2.3. Bài toán tháp Hà Nội
• 1.5.3. Chú ý
• 2. CHƯƠNG 2: CẤU TRÚC MẢNG
• 2.1. Định nghĩa
• 2.2. Cấu trúc lưu trữ mảng
• 2.2.1. Khái quát về cách lưu trữ
• 2.2.2. Lưu trữ kế tiếp đối với mảng
• 2.3. Sắp xếp trên cấu trúc mảng
• 2.3.1. Sắp xếp lựa chọn
• 2.3.2. Sắp xếp theo kiểu thêm dần
• 2.3.3. Sắp xếp kiểu đổi chỗ (Giải thuật sắp xếp kiểu nổi bọt)
• 2.4. Tìm kiếm trên cấu trúc mảng
• 2.4.1. Tìm kiếm tuần tự
• 3. CHƯƠNG 3: DANH SÁCH
• 3.1. Lưu trữ móc nối đối với danh sách
• 3.1.1. Giới thiệu phương pháp
• 3.1.2. Một số phép toán trên danh sách móc nối
• 3.1.3. Một số dạng khác trong danh sách móc nối
• 4. CHƯƠNG 4: NGĂN XẾP (STACK) VÀ HÀNG ĐỢI (QUEUE)
• 4.1. Biểu thức số học Ba Lan
• 5. CHƯƠNG 5: CẤU TRÚC CÂY (TREE)
• 5.1. Định nghĩa và một số khái niệm
• 5.2. Biểu diễn trong máy của cây nhị phân
• 5.3. Phép duyệt cây nhị phân
• 5.4. Biểu diễn cây tổng quát bằng cây nhị phân
• 5.5. Cấu trúc cây trong sắp xếp
• 5.6. Cấu trúc cây trong tìm kiếm
• 6. CHƯƠNG 6: ĐỒ THỊ (GRAPH)
• 6.1. Định nghĩa và một số khái niệm
• 6.2. Biểu diễn trong máy tính của đồ thị
• 6.2.1. Biểu diễn bằng ma trận lân cận
• 6.2.2. Biểu diễn ma trận bằng danh sách lân cận
• 6.3. Áp dụng
• 6.3.1. Bài toán tìm đường đi

Tóm tắt

I. Hướng dẫn tổng quan giáo trình cấu trúc dữ liệu và giải thuật

Giáo trình cấu trúc dữ liệu và giải thuật là một trong những môn học nền tảng và cốt lõi nhất đối với sinh viên ngành Tin học ứng dụng trình độ cao đẳng. Môn học này cung cấp những kiến thức cơ bản nhưng vô cùng quan trọng, là chìa khóa để tiếp cận lập trình chuyên nghiệp và xây dựng các phần mềm hiệu quả. Mối quan hệ khăng khít giữa cấu trúc dữ liệu và giải thuật được thể hiện qua công thức kinh điển: Chương trình phần mềm = Cấu trúc dữ liệu + Giải thuật. Một cấu trúc dữ liệu được lựa chọn hợp lý sẽ là nền tảng để xây dựng một giải thuật tối ưu, và ngược lại, một giải thuật hiệu quả cần một phương pháp lưu trữ dữ liệu phù hợp để phát huy hết sức mạnh. Việc nắm vững các khái niệm từ cơ bản như mảng, danh sách, đến phức tạp hơn như cây, đồ thị, cùng với các thuật toán xử lý tương ứng, sẽ giúp sinh viên có khảd năng tư duy logic, giải quyết vấn đề một cách có hệ thống và hiệu quả. Giáo trình này được biên soạn không chỉ để đáp ứng chuẩn mực của sách giáo khoa mà còn hướng tới giá trị thực tiễn, tăng cường khả năng tự học và tự nghiên cứu cho người học.

1.1. Vai trò nền tảng của cấu trúc dữ liệu và giải thuật

Cấu trúc dữ liệu có thể được định nghĩa là một phương pháp lưu trữ, tổ chức dữ liệu trong máy tính nhằm mục đích sử dụng chúng một cách hiệu quả. Việc lựa chọn đúng cấu trúc dữ liệu không chỉ ảnh hưởng đến khả năng truy cập, xử lý mà còn tác động trực tiếp đến hiệu suất của toàn bộ chương trình. Trong khi đó, giải thuật (hay thuật toán) là một tập hợp hữu hạn các chỉ thị hoặc quy tắc được xác định rõ ràng, không mập mờ, nhằm giải quyết một lớp bài toán cụ thể. Mối quan hệ này là không thể tách rời; một giải thuật có thể thay đổi hoàn toàn khi cấu trúc dữ liệu lưu trữ đầu vào thay đổi. Theo tài liệu gốc, "Cấu trúc dữ liệu và các giải thuật được xem như là yếu tố quan trọng nhất trong lập trình". Điều này khẳng định rằng, để trở thành một lập trình viên giỏi, việc hiểu sâu sắc cách dữ liệu được tổ chức và cách xây dựng các thuật toán để thao tác trên dữ liệu đó là yêu cầu bắt buộc. Đây là kỹ năng cốt lõi giúp phân biệt giữa một người chỉ biết viết mã và một kỹ sư phần mềm thực thụ.

1.2. Mục tiêu của giáo trình cho sinh viên Tin học ứng dụng

Mục tiêu chính của giáo trình cấu trúc dữ liệu và giải thuật dành cho trình độ cao đẳng là trang bị cho sinh viên một nền tảng kiến thức vững chắc và tư duy thuật toán sắc bén. Sinh viên cần hiểu và phân biệt được các loại cấu trúc dữ liệu cơ bản như mảng (array), danh sách liên kết (linked list), ngăn xếp (stack), hàng đợi (queue), cây (tree) và đồ thị (graph). Bên cạnh đó, giáo trình tập trung vào việc hướng dẫn sinh viên cách thiết kế, cài đặt và phân tích các giải thuật phổ biến liên quan đến tìm kiếm, sắp xếp và duyệt dữ liệu. Một mục tiêu quan trọng khác là rèn luyện khả năng lựa chọn cấu trúc dữ liệu và giải thuật phù hợp nhất cho từng bài toán cụ thể, dựa trên việc phân tích các yếu tố về thời gian thực thi và không gian bộ nhớ. Khả năng sử dụng "ngôn ngữ giả" (pseudo-code) để diễn đạt ý tưởng thuật toán một cách rõ ràng, không phụ thuộc vào một ngôn ngữ lập trình cụ thể, cũng là một kỹ năng được chú trọng, giúp sinh viên tập trung vào logic cốt lõi của vấn đề.

II. Những thách thức khi học cấu trúc dữ liệu và giải thuật

Việc tiếp cận môn học cấu trúc dữ liệu và giải thuật thường đi kèm với nhiều thách thức, đặc biệt đối với sinh viên mới bắt đầu. Khó khăn lớn nhất nằm ở tính trừu tượng của các khái niệm. Không giống như việc học một ngôn ngữ lập trình với cú pháp rõ ràng, môn học này đòi hỏi khả năng tư duy logic và hình dung các mô hình dữ liệu phi tuyến tính như cây hay đồ thị. Một thách thức khác là việc phân tích và đánh giá giải thuật. Sinh viên thường gặp khó khăn trong việc hiểu và tính toán độ phức tạp thời gian (Time Complexity) và không gian (Space Complexity), những yếu tố quyết định hiệu suất của một thuật toán khi xử lý dữ liệu lớn. Tài liệu gốc nhấn mạnh: "Nếu Thời gian thực hiện giải thuật càng nhanh thì không gian nhớ cần thiết cho cấu trúc lưu trữ dữ liệu càng lớn". Sự đánh đổi này là một khái niệm khó nắm bắt. Thêm vào đó, việc chuyển từ ý tưởng thuật toán trên giấy (sử dụng ngôn ngữ giả) sang mã nguồn chạy được bằng một ngôn ngữ lập trình cụ thể cũng đòi hỏi kỹ năng và sự tỉ mỉ, dễ gây ra lỗi logic khó phát hiện.

2.1. Khó khăn trong việc thiết kế giải thuật theo Top down

Phương pháp thiết kế Top-down, hay còn gọi là "chia để trị", là một chiến lược nền tảng trong việc giải quyết các bài toán phức tạp. Nguyên tắc của phương pháp này là tách một bài toán lớn thành các bài toán con nhỏ hơn, dễ quản lý hơn. Quá trình này được lặp lại cho đến khi các bài toán con đủ đơn giản để có thể giải quyết trực tiếp. Tuy nhiên, thách thức đối với sinh viên là làm thế nào để "chia" bài toán một cách hợp lý. Việc xác định các module con, đầu vào (input) và đầu ra (output) cho mỗi module đòi hỏi kinh nghiệm và một cái nhìn tổng thể về bài toán. Ví dụ được đưa ra trong giáo trình về sắp xếp một dãy số minh họa rõ cách tiếp cận này: chia bài toán sắp xếp thành hai công việc lặp đi lặp lại là "chọn số bé nhất" và "đặt nó vào vị trí đúng". Việc hình dung được luồng xử lý và cách tổng hợp kết quả từ các bài toán con là một kỹ năng cần nhiều thời gian để rèn luyện.

2.2. Vấn đề trừu tượng của các giải thuật đệ quy

Giải thuật đệ quy là một khái niệm mạnh mẽ nhưng cũng là một trong những chủ đề gây khó hiểu nhất. Một đối tượng được gọi là đệ quy nếu nó được định nghĩa thông qua chính nó. Ví dụ kinh điển là hàm tính giai thừa n! = n * (n-1)! hay dãy số Fibonacci Fib(n) = Fib(n-1) + Fib(n-2). Thách thức lớn nhất khi làm việc với đệ quy là theo dõi luồng thực thi của chương trình và ngăn chặn lỗi lặp vô hạn bằng cách xác định chính xác "điều kiện dừng" (base case). Bài toán Tháp Hà Nội được phân tích trong tài liệu là một minh chứng xuất sắc về sức mạnh của tư duy đệ quy để giải quyết một vấn đề phức tạp một cách thanh lịch. Tuy nhiên, tài liệu cũng cảnh báo: "Giải thuật đệ quy thường ngắn gọn và cách viết khá đơn giản [...] Tuy nhiên điều đó không có nghĩa là chúng ta thực hiện nhanh". Việc hiểu khi nào nên và không nên sử dụng đệ quy, cũng như cách máy tính xử lý các lời gọi hàm đệ quy thông qua ngăn xếp (stack), là một rào cản cần vượt qua.

III. Phương pháp tối ưu dữ liệu với cấu trúc tuyến tính

Các cấu trúc dữ liệu tuyến tính là điểm khởi đầu trong mọi giáo trình cấu trúc dữ liệu và giải thuật. Chúng tổ chức dữ liệu theo một trình tự tuần tự, nơi mỗi phần tử được kết nối với phần tử trước và sau nó. Nhóm này bao gồm cấu trúc mảng, danh sách, ngăn xếp (stack) và hàng đợi (queue). Mảng là cấu trúc cơ bản nhất, cung cấp khả năng truy cập trực tiếp và nhanh chóng vào các phần tử thông qua chỉ số, nhưng có kích thước cố định. Danh sách, đặc biệt là danh sách liên kết, mang lại sự linh hoạt trong việc thêm, xóa phần tử nhưng phải đánh đổi bằng tốc độ truy cập tuần tự. Ngăn xếp và Hàng đợi là các cấu trúc dữ liệu trừu tượng, hoạt động dựa trên các nguyên tắc truy cập đặc biệt (LIFO và FIFO), được ứng dụng rộng rãi trong quản lý tiến trình, thực thi lời gọi hàm, và các thuật toán duyệt đồ thị. Việc nắm vững cách cài đặt, các phép toán cơ bản và ưu nhược điểm của từng loại cấu trúc tuyến tính là nền tảng vững chắc để tiếp cận các cấu trúc phức tạp hơn.

3.1. Kỹ thuật sắp xếp và tìm kiếm trên cấu trúc mảng

Cấu trúc mảng là tập hợp các phần tử cùng kiểu, được lưu trữ kế tiếp trong bộ nhớ. Do tính chất này, việc sắp xếp và tìm kiếm trên mảng là hai trong số các bài toán kinh điển nhất. Giáo trình giới thiệu ba phương pháp sắp xếp cơ bản: Sắp xếp lựa chọn (Selection Sort), hoạt động bằng cách lặp đi lặp lại việc tìm phần tử nhỏ nhất và đổi chỗ về đầu dãy; Sắp xếp chèn (Insertion Sort), mô phỏng cách sắp xếp các lá bài, chèn từng phần tử vào đúng vị trí trong dãy con đã được sắp xếp; và Sắp xếp nổi bọt (Bubble Sort), liên tục so sánh và đổi chỗ các cặp phần tử liền kề bị ngược thứ tự. Về tìm kiếm, phương pháp tìm kiếm tuần tự là cách tiếp cận đơn giản nhất, duyệt qua từng phần tử cho đến khi tìm thấy hoặc hết mảng. Mặc dù các thuật toán này đơn giản, chúng là cơ sở để hiểu các khái niệm phức tạp hơn như chia để trị trong Quick Sort hay Merge Sort sau này.

3.2. Lưu trữ linh hoạt với danh sách liên kết móc nối

Để khắc phục nhược điểm kích thước cố định của mảng, danh sách liên kết (được gọi là "lưu trữ móc nối" trong tài liệu) ra đời. Mỗi phần tử trong danh sách, gọi là một "nút" (node), bao gồm hai thành phần chính: trường INFO chứa dữ liệu và trường LINK (con trỏ) chứa địa chỉ của nút tiếp theo. Phương pháp này cho phép cấp phát bộ nhớ động, giúp danh sách có thể thay đổi kích thước một cách linh hoạt trong quá trình chạy chương trình. Các phép toán cơ bản trên danh sách liên kết bao gồm duyệt danh sách, thêm một nút (vào đầu, cuối hoặc vị trí bất kỳ) và xóa một nút. Giáo trình cũng giới thiệu các biến thể như danh sách nối vòng (nút cuối cùng trỏ về nút đầu tiên) và danh sách nối kép (mỗi nút có hai con trỏ, trỏ tới nút trước và nút sau), mang lại thêm khả năng duyệt theo hai chiều nhưng phức tạp hơn trong cài đặt.

IV. Cách tiếp cận các cấu trúc dữ liệu phi tuyến hiệu quả

Khi các mối quan hệ dữ liệu không còn tuần tự, các cấu trúc dữ liệu phi tuyến như cấu trúc cây và đồ thị trở nên cần thiết. Các cấu trúc này mô hình hóa các mối quan hệ phân cấp hoặc mạng lưới phức tạp, không thể biểu diễn hiệu quả bằng mảng hay danh sách. Cây là một cấu trúc phân cấp, với một nút gốc và các nút con, mô phỏng các cấu trúc như hệ thống file, sơ đồ tổ chức. Đồ thị là cấu trúc tổng quát hơn, bao gồm một tập các đỉnh và các cạnh nối chúng, có khả năng biểu diễn mạng xã hội, bản đồ giao thông, hay mạng máy tính. Việc học các cấu trúc phi tuyến đòi hỏi sự thay đổi trong tư duy, từ tuần tự sang đa chiều. Sinh viên cần nắm vững các khái niệm như nút cha, nút con, bậc, mức, chiều cao của cây, cũng như các phương pháp biểu diễn và duyệt trên các cấu trúc này. Đây là phần kiến thức nâng cao nhưng cực kỳ quan trọng trong giáo trình cấu trúc dữ liệu và giải thuật.

4.1. Khám phá cấu trúc cây và ứng dụng cây nhị phân

Cấu trúc cây là một tập hợp hữu hạn các nút với một nút đặc biệt gọi là gốc và các nút còn lại được chia thành các tập con không giao nhau, mỗi tập con lại là một cây. Một dạng cây đặc biệt và quan trọng là cây nhị phân, trong đó mỗi nút có tối đa hai cây con, được phân biệt là cây con trái và cây con phải. Cây nhị phân có nhiều ứng dụng quan trọng, ví dụ như biểu diễn các biểu thức số học, nơi toán tử là nút gốc và toán hạng là các cây con. Giáo trình mô tả chi tiết hai cách biểu diễn cây nhị phân trong máy tính: lưu trữ kế tiếp (dùng mảng) và lưu trữ móc nối (dùng con trỏ). Lưu trữ kế tiếp hiệu quả cho cây nhị phân đầy đủ nhưng lãng phí bộ nhớ với các cây thưa thớt, trong khi lưu trữ móc nối linh hoạt hơn. Việc hiểu rõ các phương pháp biểu diễn này là tiền đề để cài đặt các thuật toán trên cây.

4.2. Các phương pháp duyệt cây và cây nhị phân tìm kiếm

Duyệt cây là quá trình "thăm" tất cả các nút trong cây, mỗi nút đúng một lần. Có ba phương pháp duyệt cây nhị phân chính: duyệt theo thứ tự trước (Pre-order: Gốc -> Trái -> Phải), thứ tự giữa (In-order: Trái -> Gốc -> Phải), và thứ tự sau (Post-order: Trái -> Phải -> Gốc). Mỗi cách duyệt có một ứng dụng riêng; ví dụ, duyệt theo thứ tự giữa trên một cây nhị phân tìm kiếm sẽ cho ra một dãy các phần tử đã được sắp xếp. Cây nhị phân tìm kiếm là một ứng dụng mạnh mẽ, nơi giá trị của mọi nút trong cây con trái đều nhỏ hơn nút gốc, và mọi nút trong cây con phải đều lớn hơn nút gốc. Tính chất này cho phép thực hiện các thao tác tìm kiếm, thêm, xóa phần tử với hiệu suất rất cao, thường là O(log n), nhanh hơn nhiều so với tìm kiếm tuần tự O(n) trên mảng hoặc danh sách.

V. Top ứng dụng thực tiễn của cấu trúc dữ liệu và giải thuật

Lý thuyết về cấu trúc dữ liệu và giải thuật sẽ trở nên vô nghĩa nếu không được áp dụng vào giải quyết các bài toán thực tế. Giáo trình đã minh họa nhiều ứng dụng quan trọng, giúp sinh viên ngành Tin học ứng dụng thấy được giá trị của môn học. Từ những ứng dụng đơn giản như việc sử dụng ngăn xếp (stack) để chuyển đổi cơ số hay tính giá trị biểu thức hậu tố Ba Lan, cho đến các ứng dụng phức tạp hơn như dùng cấu trúc đống (heap) để triển khai thuật toán sắp xếp hiệu quả (Heap Sort), hay dùng cây nhị phân tìm kiếm để quản lý dữ liệu trong cơ sở dữ liệu và từ điển. Các thuật toán duyệt đồ thị như BFS và DFS là nền tảng cho việc tìm đường đi ngắn nhất trong các ứng dụng bản đồ (Google Maps), phân tích mạng xã hội, hay tìm kiếm trong không gian trạng thái của trí tuệ nhân tạo. Việc hiểu rõ các ứng dụng này không chỉ củng cố kiến thức mà còn tạo động lực học tập, giúp sinh viên kết nối lý thuyết với thực tiễn nghề nghiệp sau này.

5.1. Ứng dụng của ngăn xếp trong biểu thức số học Ba Lan

Một trong những ứng dụng kinh điển của ngăn xếp (stack) là xử lý các biểu thức số học. Các biểu thức thông thường (dạng trung tố) như A + B * C yêu cầu quy tắc ưu tiên toán tử và dấu ngoặc, gây khó khăn cho việc tính toán của máy tính. Nhà toán học Ba Lan đã giới thiệu ký pháp hậu tố (Postfix) và tiền tố (Prefix), loại bỏ hoàn toàn dấu ngoặc. Ví dụ, A + B * C chuyển thành dạng hậu tố là A B C * +. Để tính giá trị biểu thức hậu tố, stack là một công cụ hoàn hảo. Thuật toán hoạt động bằng cách duyệt biểu thức từ trái sang phải: nếu gặp toán hạng thì đẩy vào stack; nếu gặp toán tử thì lấy hai toán hạng từ đỉnh stack ra, thực hiện phép tính rồi đẩy kết quả trở lại. Quá trình này được minh họa chi tiết trong tài liệu, cho thấy cách stack giúp đơn giản hóa một bài toán phức tạp, là nền tảng cho hoạt động của nhiều trình biên dịch và máy tính khoa học.

5.2. Giải pháp sắp xếp và tìm kiếm hiệu quả với cây

Cấu trúc cây cung cấp nhiều giải pháp hiệu quả cho các bài toán sắp xếp và tìm kiếm. Cấu trúc đống (heap), một dạng cây nhị phân gần hoàn chỉnh, là nền tảng của thuật toán Heap Sort. Bằng cách duy trì tính chất đống (nút cha luôn lớn hơn hoặc bằng các nút con), ta có thể dễ dàng lấy ra phần tử lớn nhất (ở gốc), sau đó hiệu chỉnh lại cây, lặp lại quá trình này sẽ cho một dãy được sắp xếp. Một ứng dụng khác là cây nhị phân tìm kiếm (BST). Như đã đề cập, BST cho phép tìm kiếm một phần tử trong thời gian trung bình là O(log n), một sự cải thiện vượt bậc so với O(n) của tìm kiếm tuần tự. Các biến thể cân bằng của BST như cây AVL hay cây Đỏ-Đen còn đảm bảo hiệu suất O(log n) ngay cả trong trường hợp xấu nhất, khiến chúng trở thành lựa chọn hàng đầu cho việc cài đặt các cấu trúc dữ liệu như map hay set trong nhiều thư viện lập trình chuẩn.

Nội dung chính

Tổng quan về giáo trình (250-300 từ)

Giáo trình Cấu trúc dữ liệu và Giải thuật (Mã tài liệu: THUD - MH15) là tài liệu học tập chính quy được ban hành theo Quyết định số 498/QĐ-CĐGTVTTWI-ĐT ngày 25/03/2019 của Hiệu trưởng Trường Cao đẳng Giao thông Vận tải Trung ương I. Môn học giữ vị trí kiến thức cơ sở ngành then chốt trong chương trình đào tạo trình độ Cao đẳng ngành Tin học ứng dụng, đóng vai trò nền tảng cho việc tiếp cận kỹ thuật lập trình và xây dựng phần mềm ứng dụng.

Mục tiêu đào tạo của giáo trình tập trung vào việc trang bị cho sinh viên hệ thống kiến thức nền tảng về mối quan hệ giữa cấu trúc lưu trữ dữ liệu và các thuật toán xử lý tương ứng trên máy tính, dựa trên nguyên lý cơ sở: Chương trình phần mềm = Cấu trúc + Giải thuật. Sinh viên được rèn luyện phương pháp tư duy thiết kế giải thuật theo hướng có cấu trúc, nắm vững các kỹ thuật biểu diễn dữ liệu tuyến tính và phi tuyến, đồng thời đánh giá được hiệu năng của giải thuật qua thời gian thực hiện và không gian bộ nhớ.

Về cấu trúc và cách tiếp cận, giáo trình được thiết kế gồm 6 chương theo trình tự từ cơ bản đến chuyên sâu: Giải thuật, Cấu trúc mảng, Danh sách, Ngăn xếp và Hàng đợi, Cấu trúc cây, và Đồ thị. Điểm đặc thù trong cách tiếp cận của giáo trình là việc sử dụng ngôn ngữ diễn giải tựa Pascal chuẩn tắc để mô tả thuật toán. Phương pháp này giúp người học tập trung hoàn toàn vào bản chất logic của giải thuật và cấu trúc tổ chức bộ nhớ vật lý, không bị ràng buộc bởi các quy tắc cú pháp phức tạp hay các cấu trúc dữ liệu tiền định của một ngôn ngữ lập trình bậc cao cụ thể.

---

Nội dung kiến thức cốt lõi (500-600 từ)

Các chương/chủ đề chính

• Chương 1: Giải thuật: Trình bày định nghĩa giải thuật là tập hữu hạn các phép toán cơ sở thực hiện trong thời gian hằng số; hệ thống cú pháp của ngôn ngữ diễn giải tựa Pascal (cấu trúc chương trình Program, các câu lệnh gán, lệnh ghép Begin...End, lệnh rẽ nhánh If...Then, Case...Of, vòng lặp For, While, Repeat...Until, thủ tục Procedure, hàm Function); phương pháp thiết kế giải thuật kiểu Top-down (chia để trị); phương pháp đánh giá thời gian thực hiện $T(n)$ và không gian lưu trữ; khái niệm giải thuật đệ quy qua các bài toán tính giai thừa $n!$, dãy số Fibonacci và bài toán Tháp Hà Nội với số lần chuyển đĩa $C_n = 2^n - 1$.
• Chương 2: Cấu trúc mảng: Định nghĩa mảng $N$ phần tử, véc-tơ (mảng một chiều), ma trận (mảng hai chiều); cơ chế phân bổ bộ nhớ kế tiếp và công thức xác định địa chỉ ô nhớ $LOC(A[i]) = L_0 + w \cdot (i-1)$, $LOC(B[i,j]) = L_0 + [(i-1) \cdot n + (j-1)] \cdot w$ (ưu tiên hàng) và $LOC(B[i,j]) = L_0 + [(j-1) \cdot m + (i-1)] \cdot w$ (ưu tiên cột); các thuật toán sắp xếp cơ bản gồm sắp xếp lựa chọn (Selection Sort), sắp xếp chèn/thêm dần (Insertion Sort với lính canh $A[0] = -\infty$), sắp xếp đổi chỗ/nổi bọt (Bubble Sort); các thuật toán tìm kiếm tuần tự (Sequential Search với phần tử giả $A[n+1] = X$) và tìm kiếm nhị phân.
• Chương 3: Danh sách: Khái niệm danh sách tuyến tính biến động; so sánh lưu trữ kế tiếp và lưu trữ móc nối đơn (cấu trúc nút gồm trường INFO và LINK); các phép toán trên danh sách móc nối gồm duyệt (travers), bổ sung nút đầu danh sách (Insert), loại bỏ nút cuối danh sách, ghép hai danh sách móc nối (IN-LIST); các cấu trúc mở rộng gồm danh sách nối vòng và danh sách nối kép với hai con trỏ LPTR và RPTR.
• Chương 4: Ngăn xếp (Stack) và Hàng đợi (Queue): Định nghĩa ngăn xếp theo cơ chế vào sau ra trước (LIFO); biểu diễn ngăn xếp bằng véc-tơ lưu trữ với con trỏ đỉnh $T$; xử lý điều kiện tràn ($T = n$) và cạn ($T = 0$) qua các thủ tục PUSH và POP; ứng dụng của ngăn xếp trong bài toán chuyển đổi cơ số từ thập phân sang nhị phân và xử lý ký pháp Ba Lan (tiền tố, trung tố, hậu tố); định nghĩa hàng đợi theo cơ chế vào trước ra trước (FIFO).
• Chương 5: Cấu trúc Cây (Tree): Khái niệm cây phi tuyến, quan hệ cha - con, nút gốc, nút lá, nút nhánh, cấp của nút, mức và chiều cao của cây; cấu trúc cây nhị phân và các tính chất (số nút tối đa ở mức $L$ là $2^{L-1}$, số nút tối đa của cây chiều cao $h$ là $2^h - 1$); biểu diễn cây nhị phân bằng véc-tơ kế tiếp (quan hệ chỉ số $i$, $2i$, $2i+1$) và cấu trúc móc nối; các phép duyệt cây nhị phân (tiền thứ tự, trung thứ tự, hậu thứ tự); ứng dụng cấu trúc Đống (Heap) trong sắp xếp và Cây nhị phân tìm kiếm (BST).
• Chương 6: Đồ thị (Graph): Khái niệm và định nghĩa đồ thị; các phương pháp biểu diễn đồ thị trong máy tính bằng ma trận lân cận và danh sách lân cận; áp dụng đồ thị vào bài toán tìm đường đi.

Kiến thức nền tảng được xây dựng

• Lý thuyết trừu tượng hóa dữ liệu: Phân tách rõ ràng giữa cấu trúc logic của dữ liệu (mảng, danh sách, ngăn xếp, hàng đợi, cây, đồ thị) và phương thức cài đặt vật lý tương ứng trong bộ nhớ máy tính (địa chỉ tính toán kế tiếp so với địa chỉ móc nối con trỏ).
• Nguyên lý thiết kế giải thuật: Nền tảng tư duy phân rã bài toán theo mô hình Top-down, nguyên lý đệ quy và cơ chế khử đệ quy của các trình biên dịch ngôn ngữ lập trình.
• Nguyên lý tối ưu hóa và đánh giá hiệu năng: Phương pháp so sánh sự tăng trưởng thời gian thực thi của các thuật toán khi kích thước dữ liệu đầu vào $n$ tăng dần.

Kỹ năng phát triển

• Kỹ năng kỹ thuật (Technical skills): Thành thạo thao tác cấp phát và thu hồi bộ nhớ động thông qua các thủ tục mẫu Call new(p) và Call dispose(p); thiết lập và điều khiển các con trỏ liên kết đơn và liên kết kép; tính toán chính xác chỉ số và địa chỉ ô nhớ vật lý của mảng nhiều chiều.
• Kỹ năng phân tích (Analytical skills): Phân tích cú pháp biểu thức toán học sang dạng tiền tố và hậu tố; phân tích quá trình truy vết (tracing) trạng thái dữ liệu qua từng bước lặp của các thuật toán sắp xếp và tìm kiếm; xây dựng cây nhị phân tìm kiếm từ tập dữ liệu cho trước.
• Kỹ năng thực hành (Practical competencies): Viết giả mã giải thuật mạch lạc, kiểm soát chặt chẽ các điều kiện biên trong xử lý dữ liệu như kiểm tra danh sách rỗng (L = Null), tràn ngăn xếp, cạn ngăn xếp, và kỹ thuật chèn phần tử giả (lính canh).

---

Phương pháp giảng dạy và học tập (300-350 từ)

Giáo trình áp dụng phương pháp tiếp cận sư phạm kết hợp chặt chẽ giữa lý thuyết giải tích và mô hình hóa trực quan. Nội dung mỗi chủ đề được tổ chức theo quy trình chuẩn: xuất phát từ định nghĩa hình thức và các tính chất toán học, chuyển sang mô hình biểu diễn ô nhớ vật lý trong máy tính, tiếp tục thiết kế giải thuật dưới dạng giả mã có chú giải, và kết thúc bằng việc phân tích từng bước thực thi thông qua bảng truy vết số liệu cụ thể.

Hệ thống bài tập và nghiên cứu tình huống (case studies) trong giáo trình gắn liền với các bài toán kinh điển của khoa học máy tính:

• Mô phỏng đệ quy thông qua bài toán Tháp Hà Nội với sơ đồ chuyển đĩa chi tiết cho các trường hợp $N=2$ và $N=3$.
• Ứng dụng cấu trúc ngăn xếp trong bài toán chuyển đổi cơ số thập phân $N=39$ sang hệ nhị phân và bài toán tính giá trị biểu thức hậu tố ABCD+* với các giá trị gán cụ thể $A=2, B=9, C=4, D=3$.
• Bảng minh họa diễn tiến từng bước sắp xếp dãy số cụ thể (32, 51, 27, 83, 66, 11, 45, 75) đối với các thuật toán Selection Sort, Insertion Sort và Bubble Sort.

Phương pháp đánh giá kết quả học tập tập trung vào hai tiêu chí: khả năng hiểu đúng cơ chế vận hành của cấu trúc dữ liệu trong bộ nhớ máy tính (thể hiện qua việc tính toán địa chỉ $LOC$, vẽ sơ đồ liên kết con trỏ) và khả năng viết đúng logic các hàm/thủ tục giải thuật theo chuẩn cú pháp tựa Pascal.

Đối với hoạt động tự học, tài liệu cung cấp các định hướng rõ ràng: sinh viên tự nghiên cứu các giải thuật mở rộng được gợi ý trong chương trình (như thuật toán tìm kiếm nhị phân), tự thực hiện lại các bảng truy vết biến số trên giấy, và chuyển đổi các giải thuật giả mã sang các ngôn ngữ lập trình thực tế như C hoặc Pascal để kiểm chứng thời gian chạy giữa giải thuật lặp và giải thuật đệ quy.

---

Điểm nổi bật và cập nhật (250-300 từ)

Giáo trình Cấu trúc dữ liệu và Giải thuật (2019) của Trường Cao đẳng Giao thông Vận tải Trung ương I được xây dựng theo chuẩn chương trình đào tạo cao đẳng nghề, tập trung vào tính chuẩn hóa học thuật kết hợp thực tiễn giảng dạy kỹ thuật.

Điểm nổi bật trọng tâm của giáo trình là việc sử dụng ngôn ngữ diễn giải tựa Pascal độc lập. Lựa chọn này loại bỏ sự phụ thuộc vào các thư viện hay cấu trúc dựng sẵn của các ngôn ngữ lập trình hiện đại, buộc người học phải hiểu tường tận cơ chế quản lý dữ liệu ở tầng cơ sở: từ cách thức máy tính phân bổ từ máy ($w$), tính toán độ dời địa chỉ ($LOC$), đến quy trình liên kết các nút trong bộ nhớ thông qua các biến con trỏ.

Giáo trình tích hợp các ứng dụng nền tảng của cấu trúc dữ liệu vào quá trình xử lý của máy tính và trình biên dịch:

• Ứng dụng cấu trúc cây nhị phân để biểu diễn các biểu thức số học hai ngôi và kỹ thuật duyệt cây (Pre-order, In-order, Post-order) để chuyển đổi giữa các dạng biểu thức trung tố, tiền tố và hậu tố Ba Lan (Lukasiewicz).
• Ứng dụng cấu trúc Đống (Heap) – một dạng cây nhị phân hoàn chỉnh biểu diễn qua véc-tơ – để tối ưu hóa bài toán sắp xếp dữ liệu.
• Ứng dụng cây nhị phân tìm kiếm (BST) để thực hiện thao tác tìm kiếm và chèn phần tử với quy trình so sánh khóa phân nhánh trái/phải rõ ràng.

---

Đối tượng sử dụng giáo trình (200-250 từ)

Giáo trình được biên soạn chuyên biệt cho các nhóm đối tượng sau:

• Sinh viên: Tài liệu học tập bắt buộc cho sinh viên trình độ Cao đẳng ngành Tin học ứng dụng thuộc Trường Cao đẳng Giao thông Vận tải Trung ương I và sinh viên các ngành Công nghệ thông tin, Kỹ thuật phần mềm tại các trường cao đẳng kỹ thuật.
• Điều kiện tiên quyết (Prerequisites): Để tiếp thu hiệu quả nội dung giáo trình, người học cần có kiến thức nền tảng về Toán rời rạc, tư duy logic giải quyết bài toán và kiến thức nhập môn lập trình cơ sở (nắm vững các khái niệm biến số, biểu thức, câu lệnh rẽ nhánh và vòng lặp).
• Giảng viên: Sử dụng làm tài liệu tham khảo nội bộ chuẩn mực để biên soạn bài giảng lý thuyết, thiết kế bài tập thực hành trên lớp, xây dựng ngân hàng câu hỏi thi và đề tài kiểm tra đánh giá cho học phần Cấu trúc dữ liệu và Giải thuật.
• Người tự học và tham khảo: Phù hợp cho lập trình viên và người tự học muốn củng cố tư duy thuật toán cốt lõi, tìm hiểu nguyên lý tổ chức dữ liệu tầng thấp và cơ chế vận hành bộ nhớ của máy tính.

---

Câu hỏi thường gặp (250-300 từ)

1. Giáo trình này phù hợp với ai? Giáo trình được thiết kế chuẩn hóa cho sinh viên hệ Cao đẳng ngành Tin học ứng dụng, giảng viên chuyên ngành công nghệ thông tin và người học cần xây dựng nền tảng tư duy thuật toán vững chắc.

2. Cần kiến thức nền nào trước khi học giáo trình này? Người học cần trang bị kiến thức lập trình cơ bản (biến, cấu trúc điều khiển If, For, While, hàm/thủ tục) và tư duy logic toán học để phân tích các bài toán giải thuật và tính toán chỉ số mảng.

3. Điểm khác biệt của giáo trình so với các tài liệu lập trình thông thường là gì? Giáo trình không dạy cú pháp của một ngôn ngữ lập trình thương mại mà dùng ngôn ngữ diễn giải tựa Pascal trung tính, đi sâu vào cơ chế tính toán địa chỉ bộ nhớ ($LOC$) và kỹ thuật liên kết con trỏ ở mức hệ thống.

4. Làm sao để tự học và nắm vững kiến thức trong giáo trình hiệu quả? Người học nên đọc kỹ định nghĩa và tính chất của từng cấu trúc, vẽ lại sơ đồ biến đổi dữ liệu trên giấy qua từng bước thực thi thuật toán, sau đó tự cài đặt lại các đoạn mã giả sang các ngôn ngữ như C, C++ hoặc Pascal.

5. Giáo trình có những bài toán thực tế nào được phân tích chi tiết? Tài liệu cung cấp các bài toán mẫu kinh điển có số liệu và giải thuật hoàn chỉnh như: sắp xếp chọn, sắp xếp chèn, sắp xếp nổi bọt trên dãy số mẫu, bài toán Tháp Hà Nội, đổi cơ số $N=39$ sang nhị phân, tính biểu thức hậu tố Ba Lan, và tìm kiếm trên cây nhị phân BST.

---

Kết luận (150 từ)

Giáo trình Cấu trúc dữ liệu và Giải thuật (Mã tài liệu: THUD - MH15) của Trường Cao đẳng Giao thông Vận tải Trung ương I cung cấp một hệ thống kiến thức học thuật chuẩn tắc, khúc chiết về các cấu trúc dữ liệu nền tảng và phương pháp thiết kế giải thuật trong khoa học máy tính.

Lộ trình tiếp cận kiến thức được phân định rõ ràng từ phân tích giải thuật, cấu trúc tuyến tính (mảng, danh sách liên kết, ngăn xếp, hàng đợi) đến cấu trúc phi tuyến (cây, đồ thị). Tài liệu là khung tham chiếu học thuật tin cậy, định hình tư duy tổ chức dữ liệu và tạo nền tảng vững chắc cho sinh viên trước khi bước vào các học phần lập trình chuyên sâu và phát triển phần mềm ứng dụng.

Trích đoạn nội dung tài liệu

CHƯƠNG I: GIẢI THUẬT Giới thiệu về môn học: “Cấu trúc dữ liệu và giải thuật là một trong những môn học cơ bản của sinh viên nghành CNTT khi muốn tiếp cận với lập trình và xây dựng phần mềm. liệu và các giải thuật được xem như là yếu tổ quan trọng nhất trong lập trình. CChuong trình phần mềm= Cấu trúc + Giải thuật. Cấu trúc dữ liệu có thé được xem như là một phương pháp lưu trữ dữ liệu trong.

máy tỉnh nhằm sử dụng một cách có hiệu quả những dữ liệu này. Và để sử dụng các dữ liệu một cách hiệu quả thì cẳn có các thuật toán áp dụng trên các dữ liệu đó. Đo vậy Cấu trúc dữ liệu và giải thuật là 2 yếu tổ không thể tách rời và có những, liên quan chặt ch với nhau. Cấu trúc dữ liệu và giải thuật ~_ Giải thuật (Thuật toán): Giải thuật là một tập hữu hạn các phép toán cơ sở .được sắp đặt theo quy tắc chính xác, nhằm giái một bài toán.

~ _ Các phép toán cơ sở là các phép toán đơn giản mà thời gian thực hiện nó luôn là một bằng số, nghĩa là nó không phụ thuộc vào kích thước của toán hạng ~ _ Các phép toán trong giải thuật luôn được xác định rõ rằng „không mập mở, si cũng có thể hiểu được cách thực hiện của nó. ~ _ Chú ý: Giải thuật có thể thay đổi khi cấu trúc dữ liệu thay đổi 1.2 Ngôn ngữ diễn giả: ~ _ Nếu sử dụng đến một ngôn ngữ lập trình cắp cao nào đó chẳng hạn như. Như vậy sẽ gặp một số hạn chế sau: ¬+ Phái luôn tuân thủ cú pháp chặt chế của ngôn ngữ đó, khiến cho việc trình bảy giải thật và cầu trúc dữ liệu có thiên hướng nặng nẻ, gò bó. + Phải phụ thuộc vào cấu trúc dữ liệu tiễn định (Mỗi một ngôn ngữ dữ liệu.

cđề ấn định sẵn những cấu trúc dữ liệu cho riêng mình)của ngôn ngữ. lên không thể hiện được dầy đủ các ý của từng giải thuật -+ Ngôn ngữ đã chọn không phải ai cũng ưa thích và sử dụng ~ _ Như vậy ở đây ta sẽ dùng ngôn ngữ thô hơn có đủ khả năng diễn đặt đc giải thuật ta tạm gọi bằng các tên ngôn ngữ tựa Pascal.Các quy tác bắt đầu 12 ‘Quy tác về cấu trúc chương trình: Mỗi chương trình đều được ngắn một tên để phân biệt, tên này được viết bằng chữ in hoa, có thể thêm dấu gạch nối va bắt đầu bằng từ khóa. Program VD: Program TEN_CHUONG_TRINH Độ dài tên không bị bạn chế: Sau tên có thể kèm theo lời thuyết minh (Ở đây ta quy ước dùng tiếng việt) Phin thuyết minh được đặt giữa 2 đầu (. Ký tự và biểu thức Ký tự dùng ở đây giống như các ngôn ngữ chuẳn 26 chữ cái Latinh in hoa hoặc in thường 10 chữ số thập phân Các dấu phép toán số học +, -, *,/, † (Lũy thừa) ‘Cc dau phép toán quan hệ: <,>, =, 52,# Git tri logic: True, false Dầu phép toán logic: and, or, not "Tên biển: Dấy chữ si và chữ số, đầu bằng chữ cái Biển chỉ số có hạng: A[f], B[(J] vv.

Còn bigu thức, cũng như th tự ưu tiên cũng giống như các ngôn ngỡ lập trình khác. (Cộng trừ trước nhân chia sau.) 123 “Các câu lệnh (Hay các chị thị) “Các câu lệnh trong chương trình được viết cách nhau bằng đâu chấm phải .V: Chỉ tên biến tên hàm. E: Chí biểu thức 6day cho phép dùng phép gán chung VD: A:=B:=4 2. Câu lệnh phép Có dạng: SLÍE 1,.n là các câu lệnh 'Nó chỗ phép nghép nhiều câu lệnh lại để thành một câu lệnh.

Câu lệnh điền kiện. Có dạng Tí BthenS Với B là biểu thức logic; S: Là một câu lệnh khác. Bu: Sx Else : Soot End case 'Với B,(I=12.n) là các điều kiện S(ŒE 1.n);là các câu lệnh. “Câu lệnh này cho phép phân biệt các tỉnh huồng xử lý khác nhau trong các điều kiện khác nhau mà không cần dùng đến câu lệnh iF lồng nhau.

Có thể điễn tả bởi sơ đỗ 6. Câu lệnh lặp s& Với số lần lặp biết trước. For ï:=m to n doS Nhằm thực hiện câu lệnh S với ắt giá trị nguyên từ m tới n (n>=m) với bước nhay tăng =1 Hoge: For i:=n down to m doS “Tương tự như câu lệnh trên với bước nhay giảm 1 'b. Với số lần lặp không biết trước While B do faise " ‘Chimg nào B có giá trịtrue thì thực hiện S Hoặc; Repeat $ until B Lặp S cho tới khi B có giá trị đúng (S có thể là một dãy lệnh) 7.

Câu lệnh vào ra “Có dạng: Read (<Danh sich bién>) ‘Write(<Danh sich biến hoặc dòng ký tự>) “Các biến trong danh sách cách nhau bởi dấu phẩy Dông ký tự là một dãy các ký tự đặt giữa 2 dấu °* I8. Câu lệnh kết thúc chương trình End 1.4 Chương trình con 1. Chương trình conn him Có dạng ameon <tên hàm>{<danh sách tham số>) S,:8.iSn Reture (Cau Ign két thúc chương trinh 6 day la reture thay cho end. Chương trình con thủ tye "Tương tự như trên chỉ khác ở chỗ: 2 Từkhóa oe w thaychofunetiom “Trong cấu tạo của chương trình con hàm bao giờ cũng có câu lệnh gán mà tên hảm nắm ở vế trái.

Còn đối với tên hàm con thủ tục thì không có Lời gọi chương trình con hàm thể hiện bằng tên hàm. Lời gọi của chương trình con thủ tục thể hiện bằng câu lệnh call có dạng: “Call<Tên thủ tục>(<Danh sách tham số thực>) 1.3 Thiết kế giải thuật ~_ Thiết kể kiểu top-down (Cách thiết kế đi từ tổng thể đến chỉ it — Chia để ti) Là tách bài toán ra thành các bài ra thành các bài toán con mỗi bài toán con này lại áp dụng một chiến thuật tương tự (Chia nhỏ dần) cho tới khi tới những bài toán con đủ nhỏ để có thể giải trực tiếp được. Sau đó chỉ cần tổng. hợp lại các phéo xử lý để có giải thuật cũa bài toán gốc.

Cách làm: ~ Xác định được dỡ dữ liệu yêu cầu: Cho biết cái gi (Input) và đôi hồi cái ‘(out put) = Dé gidi quyết được yêu cầu thì phải làm gì ~ _ Với mỗi công việc ấy thì phải làm thể nào ? 'VD: Ta xét bài toán sau : Sắp xếp dãy số (a:, a2, .a,) Thành dãy số tăng. din, 'Nhờ vậy đấy số Input nếu có dạng chẳng hạn (33,77,11, 55, 99, 22, 44, 88, 66) "Thi day #6 œutput phải có dạng (11, 22, 33, 44, 55, 66, 77, $8, 99) « _ Để có đc kết quả output như vậy th phải làm gi? .Có thể thấy rằng sắp xếp theo kiểu tăng dẫn nghĩa là: -+ Số bé nhất trong N số phải được đặt ở vị trí đầu tiên + Số bé nhất trong (N-1) số côn lại phải đc đặt vào vị trị thứ 2 + aw ‘Nhu vậy có 2 công việc chính phải làm: -+ Chọn số bé nhất trong diy số chưa được sắp xếp 2 + Dat né vio vj tri sau phiin tử cuối của dây số đã được sắp xếp. “Chủ ý: Lúc đầu đây số còn rồng, sau đó nó được bổ xung dẫn dẫn các phần tử vào Các công việc trên được thực lặp lại (n-1) lẫn: lần đầu với n số, lẫn cuối với 286. « _ Tới đây ta có thể điễn đặt sơ bộ gii thuật sắp XẾp của tạ như sau: Procedure selection-sort(A,n); {A là veeio gồm n phần từ là các số cho] 1.

2 công việc được lặp lãi n-1 lần or i=l to (n-l) do begin 2. Chọn số nhỏ nhất Ak] trong đãy các số Ai Afi*1]. Hoán vị giữa Afk] va Afi] 4. End; Bây giời ta đi sâu vào từng công việc + Chon số nhỏ nhất trong dãy s6: Afi], A[ï*1.

Loc == Akl; Alk] = Ali: Ali] = Loc; 6 And: 7. Reture 14 Đánh giá giải thuật ~ Khi một giải thuật được thực hiện thường nó liên quan đến 2 yếu tố -+ Không gian nhớ cần thiết cho những cầu trúc lưu trữ ¬+ Thời gian cần thiết để thực hiện 'Nếu Thời gian thực hiện giải thuật cảng nhanh thì không gian nhớ cần thiết cho cấu trúc lưu trữ dữ liệu cảng lớn. Thông thường thời gian thực hiện giải thuật vẫn được chủ ý nhiễu hơn. Vì vậy ta sét tới việc đánh giá thời gian thực hiện giải thuật ~_.

_ Củng một bải toán nếu giải thuật AI có thời gian thực hiện là : Tinj=än ~_ Giảithuật A2 có thời gian thực hiện là: T,(n)=2n ~ ___ Tathấy khin đủ lớn thì T,ƒn)< T;ín) (Chỉ cần m4) và n cảng lớn thì sự chênh lệnh cảng rõ. Như vậy lúc đó ta có thể nồi: ~_. Khin đủ lớn thì giải thuật A1 nhanh hơn giải thuật A2, 1.8 Giải thuật đệ quy 1.1 Định nghĩa: ~- Đệ quy là một khái niệm rất qua trọng trong tin học ~ Một đối tượng gọi là đệ quy nếu nó bao gồm chính nó như một bộ phận ~_ Một hảm gọi là đệ quy nếu trong định nghĩa của nó lại có dang là chính nó. 'VD : Hảm tính giai thừa của một số nguyên dương với quy ước 0!=1 thi hàm này sẽ được định nghĩa như sau: 1.

Néu N>O thi n!= n(n-1)! ‘Nhu vay trong định nghia n! lại có (n-1)! Dé chinh li tính đệ quy ‘VD: Ta muốn tinh 4! Theo dinh nghia ta 6: 4I=4.2! 22 Ueto! Như vậy 4!= 4. Ví dụ về thủ tục đệ quy 1. Hàm tính nt Function FACT(n); Ifn=0 then FACT ==1 Ele FACT:=n *FACT(a-1); Reture 2. Diy sé FIBONACCI Day fibonacei ¢6 dạng như sau: 1,1,2,3,5,8,13,21,34,55, ‘Voi số đầu la 1 va 1 thi số sau là tổng của hai số đứng trước nó.

Các số này được cai là giá trị của bảm Eib với đối số là số nguyên dương n mà ta gọi là hàm Eibonaeci. Ta có thể định nghĩa hảm này như sau: ~ Néu n=l hoge n=2 thi Fib(n)=1 ~_ Nếu m2 thi Fib(n)=Fib(n-1) + Fib (n-2) ~_ Từ đó ta có thé viết giải thuật tính giá trị của Fib(n) dưới dạng thủ túc đệ quy như sau Function Fib(a) If nc=2 then Fib:=1; Else FIB:=Fib(a-1)}+Fib(a-2) Reture 3. Bài toán thấp Hà Nội Đây là một bài toán mang tính chất một trò chơi và có nội dung như sau: 'Có n đĩa kích thước nhỏ dẫn , đĩa có lỗ ở giữa , có thể sắp xếp chúng chồng. lên nhau xuyên qua một cọc, to ớ đưới nhỏ ở trên ,để cuỗi cùng có một chồng đĩa giống như cái tháp (Như dang tap rủa ở hồ gương Hà Nội) ~ Cổ n cọc A, B, C.

Hiện N đĩa đang được xếp ở cột A yêu cầu đặt ra: Chuyển. 'cọe đĩa từ cọc A sang cọc C, theo những điều kiện sau 1. Mỗi lần chỉ được chuyển 1 dia '2. Không khi nảo có tỉnh huồng đĩa to ở trên „ đĩa nhỏ ở dưới .