Cấu trúc dữ liệu và giải thuật (DSA)

Cấu trúc dữ liệu và giải thuật (DSA)

• Cấu trúc dữ liệu phù hợp nhất cho việc truy cập ngẫu nhiên các phần tử là mảng.
• Ưu điểm của danh sách liên kết so với mảng là khả năng chèn và xóa các phần tử hiệu quả hơn.
• Cây tìm kiếm nhị phân được tối ưu hóa cho thao tác tìm kiếm, chèn và xóa.
• Heap được sử dụng để thực hiện hàng đợi ưu tiên.

Giải thuật

• Giải thuật đệ quy là giải thuật tự gọi chính nó để giải quyết một vấn đề.
• Điều kiện dừng trong giải thuật đệ quy có vai trò ngăn chặn việc gọi đệ quy vô hạn.
• Ví dụ về giải thuật đệ quy: Tính giai thừa của một số.
• Độ phức tạp thời gian của giải thuật sắp xếp nổi bọt là O(n^2).
• Các phương pháp tìm kiếm nhanh nhất là tìm kiếm nhị phân (trên dữ liệu đã sắp xếp) và bảng băm (hash table).

Lập trình hướng đối tượng (OOP)

• Bốn trụ cột chính của OOP là tính đóng gói, tính kế thừa, tính đa hình và tính trừu tượng.
• Tính đóng gói có nghĩa là kết hợp dữ liệu và phương thức hoạt động trên dữ liệu đó thành một đơn vị duy nhất.
• Tính kế thừa cho phép một lớp kế thừa các thuộc tính và phương thức của một lớp khác.
• Tính đa hình là khả năng một đối tượng có nhiều hình thức khác nhau.
• Tính trừu tượng có vai trò ẩn các chi tiết triển khai phức tạp và chỉ hiển thị các thông tin cần thiết.

Ngôn ngữ OOP

• Các ngôn ngữ lập trình hỗ trợ OOP: Java, C++, Python, C#.
• Sự khác biệt giữa lớp và đối tượng: Lớp là bản thiết kế, còn đối tượng là một thể hiện của lớp.
• Phương thức khởi tạo dùng để khởi tạo các đối tượng của một lớp.

Kiến trúc máy tính

• CPU (Central Processing Unit) là bộ xử lý trung tâm, thực hiện các lệnh của chương trình.
• RAM (Random Access Memory) là bộ nhớ truy cập ngẫu nhiên, dùng để lưu trữ dữ liệu tạm thời. ROM (Read-Only Memory) là bộ nhớ chỉ đọc, dùng để lưu trữ dữ liệu cố định.
• Bộ nhớ cache dùng để tăng tốc độ truy cập dữ liệu bằng cách lưu trữ các dữ liệu thường xuyên được sử dụng.
• Bo mạch chủ kết nối các thành phần như CPU, RAM, card đồ họa, ổ cứng.
• Bus là một hệ thống dây dẫn dùng để truyền dữ liệu giữa các thành phần trong máy tính.

Hoạt động máy tính

• Chu trình lệnh (fetch-decode-execute) là quá trình CPU lấy lệnh từ bộ nhớ, giải mã lệnh và thực hiện lệnh.
• Kiến trúc Von Neumann là kiến trúc máy tính mà dữ liệu và lệnh được lưu trữ trong cùng một không gian bộ nhớ.
• Ngắt là một tín hiệu yêu cầu CPU tạm dừng công việc hiện tại để xử lý một sự kiện khác.

Mạng máy tính

• Mô hình OSI có 7 lớp.
• Mô hình TCP/IP có 4 lớp.
• Hub kết nối các thiết bị trong mạng LAN bằng cách phát lại tín hiệu đến tất cả các cổng. Switch kết nối các thiết bị bằng cách chuyển gói tin đến đúng cổng đích. Router kết nối các mạng khác nhau bằng cách định tuyến gói tin.

Giao thức mạng

• HTTP (Hypertext Transfer Protocol) là giao thức truyền tải siêu văn bản, dùng để truyền tải dữ liệu trên web.
• DNS (Domain Name System) là hệ thống phân giải tên miền thành địa chỉ IP.
• TCP (Transmission Control Protocol) là giao thức truyền tải hướng kết nối, đảm bảo độ tin cậy của dữ liệu.
• IP (Internet Protocol) là giao thức định tuyến gói tin trên mạng Internet.
• UDP (User Datagram Protocol) là giao thức truyền tải không kết nối, nhanh hơn TCP nhưng không đảm bảo độ tin cậy.
• FTP (File Transfer Protocol) là giao thức truyền tải tệp tin.
• SMTP (Simple Mail Transfer Protocol) là giao thức truyền tải thư điện tử.
• Địa chỉ IP là địa chỉ duy nhất của một thiết bị trên mạng. Các lớp địa chỉ IP bao gồm lớp A, B, C, D, E.
• Subnet mask dùng để chia mạng thành các mạng con.

Nguyên lý hệ điều hành

• Hệ điều hành là phần mềm quản lý tài nguyên của máy tính và cung cấp giao diện cho người dùng.
• Tiến trình là một chương trình đang thực thi, còn luồng là một đơn vị thực thi nhỏ hơn trong một tiến trình.
• Quản lý bộ nhớ bao gồm các kỹ thuật như phân trang, phân đoạn và bộ nhớ ảo.
• Hệ thống tệp là cách tổ chức và lưu trữ tệp tin trên ổ đĩa.

Quản lý tài nguyên

• Các thuật toán lập lịch CPU bao gồm FCFS, SJF, Priority Scheduling, Round Robin.
• Deadlock là tình trạng hai hoặc nhiều tiến trình chờ đợi lẫn nhau để giải phóng tài nguyên, dẫn đến không có tiến trình nào có thể tiếp tục thực hiện. Để tránh deadlock, có thể sử dụng các kỹ thuật như ngăn chặn chiếm đoạt tài nguyên, yêu cầu tài nguyên theo thứ tự.

Cơ sở dữ liệu (CSDL)

• Mô hình quan hệ tổ chức dữ liệu thành các bảng, mỗi bảng chứa các hàng và cột.
• SQL (Structured Query Language) là ngôn ngữ truy vấn có cấu trúc, dùng để truy vấn và quản lý dữ liệu trong cơ sở dữ liệu quan hệ.
• Các truy vấn SQL cơ bản bao gồm SELECT, INSERT, UPDATE, DELETE.

SQL

• Mệnh đề WHERE dùng để lọc các bản ghi thỏa mãn một điều kiện nhất định.
• Mệnh đề JOIN dùng để kết hợp các bản ghi từ hai hoặc nhiều bảng dựa trên một cột chung.

Hệ phân tán

• Hệ phân tán là một tập hợp các máy tính độc lập hoạt động cùng nhau như một hệ thống duy nhất.
• Các đặc điểm của hệ phân tán bao gồm tính đồng thời, tính nhất quán, khả năng chịu lỗi và khả năng mở rộng.
• Các thách thức của hệ phân tán bao gồm quản lý tính đồng thời, đảm bảo tính nhất quán và xử lý lỗi.

Kiến trúc hệ phân tán

• Các mô hình kiến trúc hệ phân tán bao gồm kiến trúc client-server, kiến trúc peer-to-peer và kiến trúc đám mây.
• Tính đồng thời là khả năng nhiều người dùng hoặc ứng dụng truy cập và sửa đổi dữ liệu cùng một lúc.
• Tính nhất quán là đảm bảo rằng tất cả các bản sao của dữ liệu đều giống nhau.
• Khả năng chịu lỗi là khả năng hệ thống tiếp tục hoạt động bình thường ngay cả khi một số thành phần bị lỗi.