Bản tóm tắt nội dung học tập

Nội dung dưới đây sẽ cung cấp một cái nhìn tổng quan về các khái niệm nền tảng trong lập trình và giải thuật, bao gồm cách tiếp cận giải quyết vấn đề, cấu trúc dữ liệu phức hợp, tìm kiếm và sắp xếp, phân tích độ phức tạp của thuật toán, đệ quy và an toàn mã nguồn.

Khung giải quyết vấn đề theo Polya

Polya đã giới thiệu một phương pháp luận để giải quyết vấn đề, được biết đến với "bốn bước":

1. Hiểu vấn đề: Đảm bảo bạn hiểu rõ yêu cầu và mục tiêu của bài toán.
2. Lập kế hoạch: Xây dựng chiến lược giải quyết, có thể bao gồm việc chia nhỏ bài toán hoặc áp dụng các thuật toán đã biết.
3. Thực thi: Triển khai kế hoạch thông qua tính toán, viết mã hoặc thực nghiệm.
4. Kiểm tra lại: Rà soát giải pháp để đảm bảo tính chính xác và rút ra bài học cho tương lai.

Kiểu dữ liệu đơn giản và tổ hợp

• Kiểu dữ liệu đơn giản (Primitive Types): Bao gồm số nguyên, số thực, ký tự, giá trị boolean - những thành phần không thể phân chia thêm.
• Kiểu dữ liệu tổ hợp (Composite Types): Được tạo từ các kiểu dữ liệu đơn giản, như mảng, danh sách liên kết, lớp học,...

Cấu trúc dữ liệu phức hợp

Một số cấu trúc dữ liệu phổ biến bao gồm:

• Mảng: Tập hợp các phần tử cùng loại.
• Danh sách liên kết: Chuỗi các nút, mỗi nút chứa dữ liệu và tham chiếu tới nút kế tiếp.
• Ngăn xếp: Cấu trúc LIFO (Last In First Out).
• Hàng đợi: Cấu trúc FIFO (First In First Out).
• Cây: Hệ thống phân cấp gồm các nút và cạnh, ví dụ cây nhị phân, cây B.
• Đồ thị: Dùng để mô hình hóa mối quan hệ phức tạp giữa các đối tượng.

Thuật toán tìm kiếm và sắp xếp

Vài thuật toán cơ bản:

• Tìm kiếm tuyến tính: Kiểm tra từng phần tử một.
• Tìm kiếm nhị phân: Áp dụng trên dãy đã sắp xếp để giảm phạm vi tìm kiếm.
• Sắp xếp nổi bọt: So sánh và hoán đổi các phần tử kề nhau nhiều lần.
• Sắp xếp chọn: Tìm phần tử nhỏ nhất và đặt vào vị trí thích hợp.
• Sắp xếp chèn: Chèn từng phần tử vào đúng chỗ trong dãy đã sắp xếp.
• Sắp xếp nhanh: Sử dụng chiến lược chia để trị bằng cách chọn phần tử trục.

Phân tích độ phức tạp

Độ phức tạp thuật toán đo lường tốc độ tăng trưởng thời gian chạy hoặc không gian bộ nhớ khi kích thước đầu vào tăng. Các ký hiệu thường gặp bao gồm O(n), O(n²), O(log n).

Đệ quy

Đệ quy là kỹ thuật mà hàm gọi chính nó để giải quyết bài toán nhỏ hơn. Hai yếu tố quan trọng:

• Điều kiện dừng: Khi nào hàm ngừng gọi chính nó.
• Bước đệ quy: Cách thức chia nhỏ bài toán và xử lý từng phần.

An toàn mã nguồn

Các biện pháp đảm bảo an toàn mã nguồn:

• Quản lý quyền truy cập chặt chẽ.
• Sử dụng mã hóa để bảo vệ mã khỏi truy cập trái phép.
• Áp dụng giao thức bảo mật như SSH, TLS khi truyền mã.
• Phát tán mã nguồn dưới dạng khó đọc.
• Thực hiện kiểm tra bảo mật định kỳ.
• Tăng cường nhận thức bảo mật cho nhân viên.

Cấu trúc điều khiển trong C

Cấu trúc điều khiển giúp quản lý luồng thực thi chương trình.

Câu lệnh điều kiện

// Nếu
if (dieukien) {
    // Thực hiện nếu điều kiện đúng
}

// Nếu-Không
if (dieukien) {
    // Thực hiện nếu điều kiện đúng
} else {
    // Thực hiện nếu điều kiện sai
}

// Nhiều điều kiện
if (dieukien1) {
    // Thực hiện nếu điều kiện 1 đúng
} else if (dieukien2) {
    // Thực hiện nếu điều kiện 2 đúng
} else {
    // Thực hiện nếu tất cả điều kiện đều sai
}

// Switch-case
switch (bien) {
    case gia_tri1:
        // Thực hiện nếu biến bằng giá trị 1
        break;
    case gia_tri2:
        // Thực hiện nếu biến bằng giá trị 2
        break;
    default:
        // Thực hiện nếu không có trường hợp nào khớp
}

Câu lệnh lặp

// Vòng lặp for
for (khoitao; dieukien; tang) {
    // Thực hiện vòng lặp
}

// Vòng lặp while
while (dieukien) {
    // Thực hiện vòng lặp
}

// Vòng lặp do-while
do {
    // Thực hiện ít nhất một lần
} while (dieukien);

// Break và Continue
break; // Thoát khỏi vòng lặp
continue; // Bỏ qua phần còn lại và tiếp tục vòng lặp mới

Hàm trong C

Hàm cho phép đóng gói mã để tái sử dụng.

Xây dựng hàm

kieuluoi ham(ten_thamso1 kieuthamso1, ...) {
    // Nội dung hàm
    return gia_tri; // Nếu kiểu trả về không phải void
}

Gọi hàm

ketqua = ham(thamso1, thamso2, ...);

Truyền tham số

• Theo giá trị: Truyền bản sao của giá trị, mọi thay đổi không ảnh hưởng đến biến gốc.
• Theo địa chỉ: Truyền địa chỉ bộ nhớ, cho phép sửa đổi trực tiếp biến gốc.

Hàm đệ quy

int giaithua(int n) {
    if (n == 0) {
        return 1;
    }
    return n * giaithua(n - 1);
}