Thuật Toán Cơ Bản

Algorithms

Definition: A step-by-step procedure or formula for solving a problem.
Types of Algorithms:
- Sorting Algorithms: Organize data in a specified order (e.g., Quick Sort, Merge Sort, Bubble Sort).
- Search Algorithms: Retrieve information stored within data structures (e.g., Binary Search, Linear Search).
- Graph Algorithms: Process graph data structures (e.g., Dijkstra’s algorithm, Depth-First Search, Breadth-First Search).
- Dynamic Programming: Break down problems into simpler subproblems (e.g., Fibonacci sequence, Knapsack problem).
Algorithm Efficiency:
- Time Complexity: How the runtime of an algorithm grows with input size (Big O notation).
- Space Complexity: How the memory requirement grows with input size.
Heuristics: Techniques to find approximate solutions for complex problems.
Greedy Algorithms: Make the locally optimal choice at each stage with the hope of finding a global optimum.

Operating Systems

Definition: Software that acts as an intermediary between computer hardware and users.
Main Functions:
- Process Management: Handles process scheduling, execution, and termination.
- Memory Management: Manages the allocation and deallocation of memory space for processes.
- File System Management: Controls how data is stored and retrieved (e.g., file permissions, directories).
- Device Management: Manages device communication via drivers and ensures peripherals are properly utilized.
Types of Operating Systems:
- Batch Operating Systems: Execute jobs in batches without user interaction.
- Time-Sharing Operating Systems: Allow multiple users to use the system simultaneously (e.g., UNIX).
- Real-Time Operating Systems: Respond to input instantly and are used in systems requiring immediate processing (e.g., embedded systems).
Common Operating Systems: Windows, macOS, Linux, Android, iOS.
Virtual Memory: Allows the execution of processes that may not completely reside in memory, using disk space as an extension of RAM.
Kernel: Core component that manages system resources and communication between hardware and software.

Thuật toán

Định nghĩa: Quy trình hoặc công thức từng bước để giải quyết một vấn đề.
Các loại thuật toán:
- Thuật toán sắp xếp: Tổ chức dữ liệu theo thứ tự xác định (ví dụ: Quick Sort, Merge Sort, Bubble Sort).
- Thuật toán tìm kiếm: Lấy thông tin lưu trữ trong cấu trúc dữ liệu (ví dụ: Tìm kiếm nhị phân, Tìm kiếm tuyến tính).
- Thuật toán đồ thị: Xử lý cấu trúc dữ liệu đồ thị (ví dụ: Thuật toán Dijkstra, Tìm kiếm theo chiều sâu, Tìm kiếm theo chiều rộng).
- Lập trình động: Phân tách các vấn đề thành các tiểu vấn đề đơn giản hơn (ví dụ: Dãy số Fibonacci, Bài toán Balo).
Hiệu suất thuật toán:
- Độ phức tạp thời gian: Cách mà thời gian chạy của thuật toán tăng theo kích thước đầu vào (biểu diễn bằng ký hiệu Big O).
- Độ phức tạp không gian: Cách mà yêu cầu bộ nhớ tăng theo kích thước đầu vào.
- Kỹ thuật thông minh: Các phương pháp tìm kiếm giải pháp gần đúng cho các vấn đề phức tạp.
- Thuật toán tham lam: Đưa ra lựa chọn tối ưu cục bộ tại mỗi giai đoạn nhằm hy vọng tìm ra giải pháp tối ưu toàn cục.

Hệ điều hành

Định nghĩa: Phần mềm đóng vai trò trung gian giữa phần cứng máy tính và người sử dụng.
Chức năng chính:
- Quản lý quy trình: Xử lý lập lịch, thực thi và kết thúc quy trình.
- Quản lý bộ nhớ: Quản lý phân phối và giải phóng không gian bộ nhớ cho các quy trình.
- Quản lý hệ thống tệp: Kiểm soát cách dữ liệu được lưu trữ và truy xuất (ví dụ: quyền tệp, thư mục).
- Quản lý thiết bị: Quản lý giao tiếp thiết bị thông qua trình điều khiển và đảm bảo các thiết bị ngoại vi được sử dụng đúng cách.
Các loại hệ điều hành:
- Hệ điều hành theo lô: Thực hiện các công việc theo nhóm mà không cần tương tác từ người dùng.
- Hệ điều hành chia sẻ thời gian: Cho phép nhiều người dùng sử dụng hệ thống đồng thời (ví dụ: UNIX).
- Hệ điều hành thời gian thực: Phản hồi ngay lập tức đối với đầu vào và được sử dụng trong các hệ thống yêu cầu xử lý ngay lập tức (ví dụ: hệ thống nhúng).
Hệ điều hành phổ biến: Windows, macOS, Linux, Android, iOS.
Bộ nhớ ảo: Cho phép thực hiện các quy trình có thể không hoàn toàn tồn tại trong bộ nhớ, sử dụng không gian đĩa như mở rộng của RAM.
Nhân hệ điều hành: Thành phần cốt lõi quản lý tài nguyên hệ thống và giao tiếp giữa phần cứng và phần mềm.