Chương 1: Tổng quan về lập trình

Giới thiệu những kiến thức cơ bản về máy tính, lập trình và thuật toán, những nền tảng quan trọng trước khi bắt đầu tìm hiểu các kỹ thuật lập trình.

1. Tổng quan về máy tính và lập trình

Máy tính là công cụ cơ bản giúp con người xử lý thông tin nhanh chóng và chính xác. Đối với lập trình viên, việc hiểu cách máy tính hoạt động và cách chương trình được thực thi là nền tảng quan trọng để viết mã hiệu quả, tối ưu và hạn chế lỗi.

Phần này sẽ giới thiệu những kiến thức cơ bản về máy tính và lập trình, giúp bạn có nền tảng vững chắc để tiếp cận các kỹ thuật lập trình nâng cao.

1.1. Tổng quan về máy tính

Trong lập trình, hiểu về máy tính thông qua cách nó nhận dữ liệu, xử lý thông tin đến xuất kết quả là nền tảng cần thiết cho mọi lập trình viên. Kiến thức này giúp người lập trình nắm vững cách phần cứng và phần mềm phối hợp, từ đó tạo ra những chương trình hiệu quả, tối ưu.

Phần tổng quan này sẽ giới thiệu những khái niệm cơ bản về máy tính, tạo nền tảng vững chắc để tiếp cận các kỹ thuật lập trình nâng cao.

1.1.1. Chức năng của máy tính

Máy tính là một thiết bị điện tử tiên tiến, có khả năng:

Tiếp nhận dữ liệu (Input): Nhận thông tin từ người dùng hoặc các thiết bị ngoại vi để xử lý.
Xử lý dữ liệu (Processing): Thực hiện các phép toán, thao tác logic và các lệnh theo chương trình đã được lập trình sẵn.
Xuất kết quả và lưu trữ thông tin (Output & Storage): Cung cấp kết quả sau khi xử lý và lưu trữ dữ liệu để sử dụng trong tương lai.

1.1.2. Cấu trúc của máy tính

Để máy tính thực hiện được các chức năng nhận dữ liệu, xử lý thông tin và xuất kết quả, nó cần được tổ chức theo một cấu trúc hợp lý, bao gồm các thành phần phần cứng và phần mềm. Sự phối hợp chặt chẽ giữa các thành phần này đảm bảo máy tính hoạt động hiệu quả và ổn định. Dưới đây là tổng quan về cấu trúc cơ bản của một hệ thống máy tính.

Phần cứng (Hardware)

Phần cứng là tập hợp các bộ phận vật lý của máy tính, đảm nhận vai trò xử lý dữ liệu, lưu trữ thông tin và cung cấp các phương tiện để tương tác với người dùng. Hiểu về phần cứng giúp lập trình viên nắm rõ cách các lệnh và chương trình được thực thi, từ đó viết mã hiệu quả và tối ưu hơn. Dưới đây là các thành phần chính của phần cứng máy tính.

Phần cứng đóng vai trò là "xương sống" và "bộ não" của hệ thống, bao gồm:

CPU (Central Processing Unit): Bộ xử lý trung tâm, được xem là “bộ não” của máy tính, thực hiện các lệnh.
RAM (Random Access Memory): Bộ nhớ truy cập ngẫu nhiên, lưu trữ tạm thời dữ liệu đang được CPU xử lý.
Ổ cứng (Hard Disk): Lưu trữ dữ liệu lâu dài.
Thiết bị ngoại vi: Chuột, bàn phím, màn hình, máy in,…

Phần mềm (Software)

Phần mềm là tập hợp các chương trình và dữ liệu điều khiển hoạt động của phần cứng, cho phép máy tính thực hiện các chức năng cụ thể. Nó bao gồm hệ điều hành, quản lý tài nguyên phần cứng và cung cấp môi trường cho các ứng dụng, cũng như các chương trình phục vụ nhu cầu trực tiếp của người dùng. Hiểu rõ phần mềm giúp lập trình viên viết chương trình tương thích, tối ưu và khai thác hiệu quả khả năng của máy tính.

Là các chương trình và dữ liệu điều khiển hoạt động của máy tính, phần mềm được chia thành hai nhóm chính:

Hệ điều hành (Operating System - OS): Quản lý và điều phối toàn bộ tài nguyên phần cứng như CPU, bộ nhớ, thiết bị ngoại vi, đồng thời cung cấp môi trường cho các ứng dụng chạy. Hệ điều hành cũng đảm bảo an toàn, bảo mật và kiểm soát truy cập vào tài nguyên hệ thống.
Ví dụ: Windows, macOS, Linux.
Ứng dụng (Application Software): Bao gồm các chương trình được thiết kế để phục vụ nhu cầu cụ thể của người dùng, như soạn thảo văn bản, xử lý bảng tính, duyệt web, đồ họa hay phần mềm lập trình. Các ứng dụng tương tác với hệ điều hành để sử dụng phần cứng và thực hiện chức năng mong muốn.
Ví dụ: Microsoft Word, Excel, Chrome, Photoshop.

1.2. Khái niệm cơ bản về lập trình

Lập trình là quá trình tạo ra các chỉ thị (instructions) để máy tính thực hiện một nhiệm vụ nhất định.

Mục đích của lập trình là tạo ra các giải pháp tự động, chính xác và hiệu quả cho nhiều vấn đề trong đời sống và công việc. Thông qua lập trình, con người có thể tự động hóa công việc, xử lý khối lượng dữ liệu lớn nhanh chóng, giải quyết các bài toán phức tạp, đồng thời phát triển các ứng dụng, website, trò chơi và các hệ thống phần mềm khác.

Hiểu rõ các khái niệm cơ bản về lập trình giúp người học nắm được cách thức hoạt động của chương trình, cách xử lý dữ liệu và cách giải quyết vấn đề một cách logic.

1.3. Sơ lược về ngôn ngữ lập trình

Ngôn ngữ lập trình là phương tiện để viết các chỉ thị cho máy tính.

1.3.1. Ngôn ngữ máy (Machine Language):

Là ngôn ngữ cơ bản nhất mà máy tính có thể hiểu trực tiếp, được biểu diễn hoàn toàn bằng các chuỗi nhị phân gồm 0 và 1.

Mỗi lệnh trong ngôn ngữ máy tương ứng với một thao tác cụ thể trên phần cứng, như di chuyển dữ liệu, thực hiện phép tính, hoặc nhảy đến vị trí khác trong bộ nhớ. Vì máy tính có thể thực thi ngay các lệnh này mà không cần thông dịch hay biên dịch, ngôn ngữ máy là duy nhất mà phần cứng hiểu trực tiếp.

Ví dụ: 10110000 01100001 11000011

1.3.2. Ngôn ngữ bậc cao (High-level Language):

Ngôn ngữ bậc cao là loại ngôn ngữ lập trình được thiết kế gần gũi với ngôn ngữ tự nhiên, giúp lập trình viên dễ đọc, dễ viết và dễ hiểu hơn so với ngôn ngữ máy hay ngôn ngữ hợp ngữ.

Ngôn ngữ bậc cao cho phép lập trình viên viết các chương trình phức tạp mà không cần quan tâm trực tiếp đến chi tiết phần cứng như địa chỉ bộ nhớ hay lệnh nhị phân.

Ví dụ: $\texttt{C}$ , $\texttt{C++}$ , Java, Python, $\texttt{C\#}$ , JavaScript,… Những ngôn ngữ này hỗ trợ các tính năng như biến, hàm, cấu trúc điều khiển, vòng lặp, đối tượng, giúp tổ chức chương trình một cách logic và dễ bảo trì.

1.4. Ngôn ngữ lập trình C++

$\texttt{C++}$ là một ngôn ngữ lập trình bậc cao, mạnh mẽ và linh hoạt, được sử dụng rộng rãi trong phát triển phần mềm, ứng dụng, game, hệ thống nhúng và nhiều lĩnh vực kỹ thuật khác. Ngôn ngữ này kế thừa cú pháp từ $\texttt{C}$ nhưng mở rộng với các tính năng lập trình hướng đối tượng, cho phép tổ chức chương trình theo các lớp và đối tượng, từ đó dễ quản lý, mở rộng và tái sử dụng mã nguồn.

$\texttt{C++}$ hỗ trợ cả lập trình thủ tục và lập trình hướng đối tượng, đồng thời cung cấp khả năng thao tác trực tiếp với phần cứng và quản lý bộ nhớ, giúp lập trình viên kiểm soát hiệu suất và tối ưu chương trình. Nhờ sự kết hợp giữa tính linh hoạt, hiệu suất cao và cấu trúc rõ ràng, $\texttt{C++}$ trở thành ngôn ngữ phổ biến trong giáo dục, nghiên cứu khoa học, phát triển phần mềm và các ứng dụng đòi hỏi hiệu suất.

Các đặc điểm nổi bật của $\texttt{C++}$ :

Hướng đối tượng: Hỗ trợ lập trình theo lớp, đối tượng, kế thừa, đa hình.
Hiệu suất cao: Thao tác trực tiếp với bộ nhớ, gần với phần cứng.
Tính linh hoạt: Kết hợp lập trình thủ tục và lập trình hướng đối tượng.
Thư viện phong phú: STL (Standard Template Library) cung cấp các cấu trúc dữ liệu và thuật toán chuẩn.

2. Thuật toán

Thuật toán là tập hợp các bước rõ ràng và có thứ tự để giải quyết một vấn đề hoặc thực hiện một nhiệm vụ nhất định. Trong lập trình, thuật toán là nền tảng giúp lập trình viên thiết kế chương trình logic, tối ưu hóa hiệu suất và đảm bảo kết quả chính xác. Hiểu và xây dựng được thuật toán tốt là bước quan trọng trước khi viết mã, vì một chương trình hiệu quả luôn bắt nguồn từ một thuật toán hiệu quả.

2.1. Khái niệm về vấn đề/bài toán

Trong lập trình và khoa học máy tính, việc giải quyết một nhiệm vụ hay yêu cầu cụ thể thường bắt đầu từ việc xác định vấn đề và bài toán:

Vấn đề: Là yêu cầu, tình huống hoặc mục tiêu cần giải quyết. Vấn đề thường được mô tả bằng ngôn ngữ tự nhiên và có thể mang tính trừu tượng.
Ví dụ: “Tìm cách sắp xếp danh sách điểm số của sinh viên từ cao xuống thấp.”
Bài toán: Là dạng biểu diễn của vấn đề sao cho có thể xử lý được bằng logic, thuật toán hoặc máy tính. Bài toán thường được xác định rõ ràng với dữ liệu đầu vào, quy trình xử lý và kết quả đầu ra.
Ví dụ: Bài toán là yêu cầu từ vấn đề, có thể cung cấp dữ liệu đầu vào với một danh sách chưa được sắp xếp, kèm yêu cầu xử lý (vấn đề), và kết quả đầu ra.

Tóm lại, vấn đề là yêu cầu thực tế cần giải quyết, còn bài toán là cách biểu diễn vấn đề để có thể thiết kế thuật toán và lập trình xử lý. Việc phân biệt rõ ràng hai khái niệm này là bước đầu tiên để xây dựng các thuật toán chính xác và hiệu quả.

2.2. Các bước giải quyết vấn đề/bài toán bằng máy tính

Để giải quyết một vấn đề hoặc bài toán bằng máy tính, lập trình viên thường thực hiện theo các bước tuần tự sau:

Bước 1: Xác định vấn đề/bài toán

Hiểu rõ yêu cầu, mục tiêu cần đạt được và các dữ liệu liên quan.
Phân biệt giữa vấn đề (tổng quát, thực tế) và bài toán (biểu diễn cụ thể, có thể xử lý bằng máy tính).

Bước 2: Lựa chọn giải pháp

Phân tích các phương án khả thi để giải quyết bài toán.
Đánh giá ưu nhược điểm của từng phương án về hiệu quả, độ phức tạp và khả năng thực hiện.

Bước 3: Xây dựng thuật toán hoặc thuật giải

Thiết kế các bước logic, tuần tự hoặc lặp lại để giải quyết bài toán.
Thuật toán phải rõ ràng, đầy đủ và đảm bảo có kết thúc.

Bước 4: Cài đặt chương trình (Lập trình)

Chuyển thuật toán thành mã lệnh bằng một ngôn ngữ lập trình cụ thể.
Tuân thủ cú pháp và quy tắc của ngôn ngữ được sử dụng.

Bước 5: Hiệu chỉnh chương trình

Kiểm tra, phát hiện và sửa các lỗi trong chương trình.
Đảm bảo chương trình chạy đúng theo thuật toán đã thiết kế và đáp ứng yêu cầu bài toán.

Bước 6: Thực hiện chương trình

Chạy chương trình với dữ liệu đầu vào thực tế.
Đánh giá kết quả đầu ra, so sánh với mong đợi và áp dụng vào thực tiễn.

Các bước này tạo thành một quy trình có hệ thống, giúp lập trình viên giải quyết vấn đề một cách logic, chính xác và hiệu quả.

2.3. Khái niệm về thuật toán

Thuật toán là nền tảng của lập trình và giải quyết vấn đề bằng máy tính. Trước khi viết chương trình, lập trình viên cần hiểu rõ cách xây dựng các bước logic để đạt được kết quả mong muốn.

Trong lập trình, thuật toán (Algorithm) được định nghĩa là một dãy hữu hạn các thao tác cần thực hiện để giải quyết một bài toán.

2.4. Các tiêu chuẩn của thuật toán

Một thuật toán chỉ thực sự hữu ích khi nó đáp ứng các tiêu chuẩn cụ thể. Việc hiểu và áp dụng các tiêu chuẩn này giúp lập trình viên thiết kế thuật toán dễ theo dõi, triển khai chương trình chính xác và tránh các lỗi không đáng có. Phần này sẽ giới thiệu những tiêu chuẩn quan trọng mà mọi thuật toán cần tuân thủ.

Một thuật toán được coi là tốt khi đáp ứng các tiêu chuẩn cơ bản sau:

Tính chính xác: Output đầu ra của thuật toán phải đúng với yêu cầu.
Tính khách quan: Khi thực hiện nhiều lần trên nhiều máy khác nhau, thuật toán phải trả ra kết quả giống nhau.
Tính hữu hạn: Thời gian thực hiện của thuật toán là hữu hạn, không lặp vô hạn.
Tính tổng quát: Thuật toán có thể áp dụng cho nhiều tập dữ liệu đầu vào tương tự.
Tính hiệu quả: Các bước thực hiện rõ ràng, hợp lý, tránh lãng phí thời gian và tài nguyên.

Việc tuân thủ các tiêu chuẩn này giúp lập trình viên xây dựng thuật toán logic, chính xác và tối ưu, từ đó dễ dàng chuyển đổi sang chương trình máy tính hiệu quả và đáng tin cậy.

2.5. Các phương pháp biểu diễn thuật toán

Để thuật toán dễ hiểu, dễ phân tích và dễ triển khai thành chương trình, cần phải biểu diễn nó một cách rõ ràng và trực quan. Có nhiều phương pháp biểu diễn thuật toán khác nhau, mỗi phương pháp có ưu điểm riêng phù hợp với từng đối tượng và mục đích sử dụng.

2.5.1. Dùng ngôn ngữ tự nhiên

Một trong những phương pháp đơn giản nhất để biểu diễn thuật toán là sử dụng ngôn ngữ tự nhiên, tức là mô tả các bước thực hiện bằng văn bản thông thường.

Phương pháp này dễ hiểu, đặc biệt phù hợp với người mới học hoặc khi truyền đạt thuật toán cho những người không quen với ký hiệu lập trình.

Tuy nhiên, nhược điểm là ngôn ngữ tự nhiên có thể không chính xác tuyệt đối, dễ dẫn đến hiểu nhầm hoặc thiếu rõ ràng khi thuật toán phức tạp

Ví dụ: Mô tả bằng ngôn ngữ tự nhiên thuật toán tính tổng các số từ 1 đến n.

Bắt đầu.
Nhập số nguyên dương n.
Khởi tạo biến sum bằng 0.
Lặp từ i = 1 đến i = n:
    Cộng i vào sum.
In kết quả sum.
Kết thúc.

2.5.2. Dùng lưu đồ (Flowchart)

Lưu đồ là một phương pháp biểu diễn thuật toán bằng các hình khối và mũi tên, thể hiện thứ tự và logic của các bước thực hiện. Mỗi loại hình khối trong lưu đồ có ý nghĩa riêng.

Phương pháp này giúp trực quan hóa thuật toán, dễ dàng phát hiện lỗi logic và truyền đạt ý tưởng cho người khác. Lưu đồ đặc biệt hữu ích khi thuật toán phức tạp hoặc khi làm việc nhóm, vì nó giúp mọi người nắm bắt quy trình một cách nhanh chóng và chính xác.

Các ký hiệu cơ bản bao gồm:

Khối giới hạn: Bắt đầu/Kết thúc.
Khối vào ra (Input/Output): Nhập hoặc xuất dữ liệu.
Khối lựa chọn (Decision): Rẽ nhánh theo điều kiện.
Khối thao tác (Process): Thao tác cần thực hiện.
Đường đi (Arrow): Chỉ hướng các bước tiếp theo.

Ví dụ: Mô tả bằng lưu đồ thuật toán tính tổng các số từ 1 đến n.

2.5.3. Dùng mã giả (Pseudocode)

Mã giả (Pseudocode) là một công cụ trung gian giữa ý tưởng thuật toán và ngôn ngữ lập trình thực tế. Thay vì viết trực tiếp bằng ngôn ngữ lập trình với cú pháp nghiêm ngặt, mã giả sử dụng cú pháp gần gũi, dễ hiểu, chú trọng vào logic và bước thực hiện của thuật toán.

Ví dụ: Mô tả bằng mã giả tổng các số từ 1 đến N.

BEGIN
    sum <- 0
    FOR i FROM 1 TO N
        sum <- sum + i
    END FOR
    PRINT sum
END

2.6. Độ phức tạp của Thuật toán

Độ phức tạp của thuật toán là một khái niệm cơ bản trong khoa học máy tính dùng để đánh giá hiệu quả của thuật toán. Nó thể hiện mức độ tiêu tốn tài nguyên của thuật toán khi xử lý dữ liệu, được phân loại theo độ phức tạp về thời gian và không gian.

2.6.1. Độ phức tạp thời gian (Time Complexity)

Độ phức tạp thời gian của một thuật toán là thước đo lượng thời gian cần thiết để thuật toán hoàn thành dựa trên kích thước đầu vào $n$ . Đây là tiêu chí quan trọng nhất khi đánh giá hiệu quả thuật toán trong lập trình, bởi thời gian chạy quyết định trực tiếp đến hiệu năng và khả năng xử lý dữ liệu lớn.

Độ phức tạp về thời gian thường biểu diễn bằng ký hiệu $BigO$ :

$O(1)\rightarrow$ thời gian cố định
$O(n)\rightarrow$ tuyến tính
$O(n^2)$ , $O(\log n)$ , $O(n \log n)$ …

Việc xem xét độ phức tạp về thời gian có ý nghĩa rất lớn trong lập trình, khi giúp lập trình viên lựa chọn được thuật toán tối ưu cho dữ liệu lớn, cho phép dự đoán hiệu năng trước khi triển khai thực tế và so sánh các thuật toán khác nhau về mặt tốc độ.

2.6.2. Độ phức tạp không gian (Space Complexity)

Độ phức tạp không gian của một thuật toán là thước đo lượng bộ nhớ cần thiết để thuật toán hoàn thành công việc dựa trên kích thước đầu vào $n$ . Nó phản ánh khả năng tiêu thụ tài nguyên bộ nhớ của thuật toán, bao gồm các biến, mảng, stack, các biến tạm thời và bộ nhớ sử dụng trong đệ quy.

Tuy nhiên:

Trong lập trình, khi nhắc đến “độ phức tạp của thuật toán”, người ta thường chủ yếu nói về độ phức tạp thời gian (Time Complexity). Lý do là vì thời gian chạy của thuật toán ảnh hưởng trực tiếp đến hiệu năng chương trình, trong khi độ phức tạp không gian chỉ quan trọng khi bộ nhớ hạn chế.

Đồng thời, thời gian thực tế có thể khác nhau trên từng máy tính do sự khác biệt về phần cứng, tốc độ CPU, RAM, bộ nhớ cache, vì vậy việc đánh giá độ phức tạp không dựa trên thời gian tuyệt đối mà dựa trên tốc độ tăng trưởng theo kích thước đầu vào. Đây là lý do Time Complexity trở thành tiêu chí chính khi phân tích thuật toán.

Các bạn có thể tìm hiểu kỹ hơn về Thuật toán và độ phức tạp của thuật toán trong Chương 1: Giới thiệu về giải thuật ở môn Cấu trúc dữ liệu và Giải thuật

1. Tổng quan về máy tính và lập trình​

1.1. Tổng quan về máy tính​

1.1.1. Chức năng của máy tính​

1.1.2. Cấu trúc của máy tính​

1.2. Khái niệm cơ bản về lập trình​

1.3. Sơ lược về ngôn ngữ lập trình​

1.3.1. Ngôn ngữ máy (Machine Language):​

1.3.2. Ngôn ngữ bậc cao (High-level Language):​

1.4. Ngôn ngữ lập trình C++​

2. Thuật toán​

2.1. Khái niệm về vấn đề/bài toán​

2.2. Các bước giải quyết vấn đề/bài toán bằng máy tính​

2.3. Khái niệm về thuật toán​

2.4. Các tiêu chuẩn của thuật toán​

2.5. Các phương pháp biểu diễn thuật toán​

2.5.1. Dùng ngôn ngữ tự nhiên​

2.5.2. Dùng lưu đồ (Flowchart)​

2.5.3. Dùng mã giả (Pseudocode)​

2.6. Độ phức tạp của Thuật toán​

2.6.1. Độ phức tạp thời gian (Time Complexity)​

2.6.2. Độ phức tạp không gian (Space Complexity)​

Tài liệu tham khảo