Bài giảng Tin học đại cương - Chương 1: Cơ bản về tin học

 các tham chiếu. Như vậy ta có thể đi vào xa lộ thông tin của thế giới.
 URL (Unifrom Resource Locator)
 – Là chuẩn định vị tài nguyên trên mạng (thường gọi là link). Căn cứ
 vào URL người dùng có thể di chuyển từ văn bản này tới văn bản
 khác trong khái niệm siêu văn bản.
 – Được dùng để tham chiếu tới tài nguyên trên Internet
 – Cú pháp URL:
 • Protocol://Domain-name:Port/Folder/Page?Variable=Value#Label
 – Vd: 
ttdung@utc2.edu.vn 41
1.3. Khái niệm về vấn đề và bài toán
 Bài toán
 – Trong phạm vi tin học, bài toán được hiểu là một công việc 
 nào đó mà ta muốn máy tính thực hiện.
 – 2 yếu tố quan trọng của bài toán:
 • Input: dữ liệu đưa vào
 • Output: kết quả cần tìm của bài toán.
 – Vd: Viết một dòng chữ ra màn hình. Bài toán giải phương 
 trình bậc 2; Bài toán quản lý điểm..v.v
 Thuật toán
 – Là một dãy hữu hạn các thao tác được sắp xếp theo một trình 
 tự xác định sao cho khi thực hiện dãy thao tác đó thì từ Input 
 của bài toán ta sẽ có Output cần tìm.
ttdung@utc2.edu.vn 42
Các bước giải bài toán
 Bước 1 - Xác định bài toán
 – Xác định rõ Input và Output của bài toán.
 – Cần xác định input, output một cách cẩn thận vì nó sẽ ảnh
 hưởng tới việc lựa chọn thuật toán giải quyết. Trong tin học, đôi
 khi việc xác định input/output còn phụ thuộc vào ngôn ngữ lập
 trình sử dụng.
 Bước 2 - Thiết kế thuật toán
 – Là bước quan trọng nhất để giải bài toán
 – Một bài toán có thể có nhiều thuật toán để giải quyết
 – Cần quan tâm tới tính hiệu quả của thuật toán (về bộ nhớ, về 
 thời gian thực hiện..v.v)
ttdung@utc2.edu.vn 43
Các bước giải bài toán (tt)
Bước 3 – Viết chương trình
 – Lựa chọn ngôn ngữ lập trình phù hợp với nhu cầu và khả năng của 
 bản thân
 – Cần tận dụng các tiện ích mà các IDE (Integrated Deverlopment
 Environment)
Bước 4 – Hiệu chỉnh, làm tinh chương trình
 – Cần đưa nhiều bộ số liệu khác nhau vào kiểm thử
 – Đôi khi cần có kinh nghiệm và đầu óc phán đoán lỗi.
Bước 5 – Viết tài liệu
 – Là hướng dẫn sử dụng, kết quả thử nghiệm, hoặc mô tả chi tiết thuật 
 toán
ttdung@utc2.edu.vn 44
Thuật toán – Thuật giải
 Định nghĩa:
 – Thuật toán (algorithm) là một dãy hữu hạn các thao tác được 
 sắp xếp theo một trình tự xác định sao cho khi thực hiện dãy 
 thao tác đó thì từ Input của bài toán ta sẽ có Output cần tìm.
 Các đặc trưng của thuật toán
 – Tính hữu hạn
 – Tính xác định
 – Tính đúng đắn
 – Tính chi tiết: thao tác trong thuật toán phải chặt chẽ, đủ chi tiết
 để 1 đối tượng có thể thực hiện được thuật toán.
 – Tính phổ dụng
ttdung@utc2.edu.vn 45
Thuật toán – Thuật giải (tt)
 Từ giải thuật đến chương trình
 Giải thuật chỉ là “phương pháp”.
 Sử dụng giải thuật như thế nào để giải quyết bài toán
 – Cần phải có máy tính.
 – Lập trình: Mô tả (cài đặt) giải thuật lên máy tính.
 Biểu diễn đối tượng xử lý bởi dữ liệu (data) trong chương trình
 (có nhiều kiểu dữ liệu với cấu trúc khác nhau).
 Thuật giải + cấu trúc dữ liệu = chương trình
ttdung@utc2.edu.vn 46
Thuật toán – Thuật giải (tt)
 Có phải mọi bài toán đều có thuật giải?
 Có những bài toán không có giải thuật tổng
 quát để giải quyết.
 Có những bài toán chưa có giải thuật hữu
 hiệu để giải quyết.
 Có những bài toán chưa có giải thuật tìm lời
 giải.
ttdung@utc2.edu.vn 47
Biểu diễn thuật toán
Liệt kê từng bước
Sử dụng sơ đồ khối
Sử dụng giả ngôn ngữ lập trình
ttdung@utc2.edu.vn 48
Phương pháp liệt kê từng bước
 Các thao tác của giải thuật được liệt kê từng bước.
 Tại mỗi bước, sử dụng ngôn ngữ tự nhiên để diễn tả công
 việc phải làm.
 Bước đứng trước (có số thứ tự nhỏ hơn) được thực hiện
 trước.
 Ưu nhược điểm
 – Dễ hiểu, dễ làm
 – Phụ thuộc vào “cách hành văn” của người diễn đạt
 – Với những giải thuật phức tạp, cách diễn đạt này trở nên
 rườm rà
 – .
ttdung@utc2.edu.vn 49
Ví dụ
 Giải thuật “Tìm vị trí xuất hiện đầu tiên của một số 
 nguyên trong dãy số nguyên đã cho”:
Bước 1: Nhập dãy số nguyên a1, a2, ., aN
Bước 2: Nhập số nguyên s
Bước 3: Gán vị trí p ban đầu = 0 và vị trí i đang xét = 1 p = 0, i=1
Bước 4: So sánh ai với s
 Nếu ai =s thì ghi nhận vị trí p = i → Sang Bước 5
 Nếu ai ≠ s và i < N thì gán i=i+1 và lặp lại bước 4, ngược 
 lại sang Bước 5
Bước 5: Nếu p ≠ 0 thì đưa ra vị trí cần tìm là p, ngược lại thông báo không 
tìm thấy giá trị s trong dãy số đã cho.
Bước 6: Kết thúc.
ttdung@utc2.edu.vn 50
Biểu diễn thuật toán bằng sơ đồ khối
 Sử dụng các hình khối để minh hoạ cho các lệnh hay
 thao tác.
 Sử dụng mũi tên để diễn đạt thứ tự thực hiện.
 Đây là cách diễn đạt khoa học, có tính nhất quán cao.
 Các hình khối cơ bản
 – Khối bắt đầu.
 – Khối kết thúc.
 – Khối thao tác cụ thể.
 – Khối kiểm tra điều kiện.
 – Khối vào/ra dữ liệu.
 – Khối gọi chương trình con.
 Các ký pháp.
ttdung@utc2.edu.vn 51
Các hình khối cơ bản
  Gọi chương trình con A (ít
  Khối bắt đầu và kết thúc
 dùng)
 Begin A
 End
  Khối thực thi công việcA
  Khối kiểm tra điều kiện
 – Tuỳ thuộc điều kiện (Đúng 
 A hay Sai) mà rẽ nhánh thích 
 hợp
  Khối input/output
 Đúng
 Điểm nối Điều kiện
 Sai
ttdung@utc2.edu.vn 52
Sơ đồ một số cấu trúc cơ bản
• Cấu trúc rẽ nhánh
 if.then if.then
 else
ttdung@utc2.edu.vn 53
Sơ đồ một số cấu trúc cơ bản
• Cấu trúc lặp xác định
 Biến = 1, 2, , n
 A
ttdung@utc2.edu.vn 54
Sơ đồ một số cấu trúc cơ bản (tt)
• Cấu trúc lặp không xác định
 whiledo repeatuntil
ttdung@utc2.edu.vn 55
Tính chu vi và diện tích HCN
Phương pháp liệt kê  Sơ đồ khối
 – B1. Nhập hai cạnh a,b
 – B2. Tính chu vi
 • C = 2*(a+b) Nhập a,b
 – B3. Tính diện tích
 • S = a*b
 – B4. In chu vi C
 – B5. In diện tích S
 – Kết thúc
ttdung@utc2.edu.vn 56
Ví dụ
ttdung@utc2.edu.vn 57
Bài tập
1. Thuật toán tính chu vi, diện tích hình chữnhật
2. Thuật toán kiểm tra năm nhuận (năm nhuận là 
 năm chia hết cho 400 hoặc chia hết cho 4 
 nhưng không chia hết cho 100)
3. Thuật toán tính chu vi, diện tích tam giác biếtđộ 
 dài 3 cạnh (kiểm tra 3 cạnh tạo thành tam giác 
 hay không trước khi tính)
4. Thuật toán hoán đổi giá trị của 2 số a và b
ttdung@utc2.edu.vn 58
Bài tập
1. Nhập 2 số nguyên dương a, b. Tìm UCLN và
 BCNN của 2 số đó.
2. Nhập số nguyên a, kiểm tra xem a có phải là số
 nguyên tố không?
3. Nhập số nguyên a, kiểm tra xem a có phải là số
 hoàn hảo hay không?
ttdung@utc2.edu.vn 59
Một số bài toán cơ bản
• Bài toán đếm
• Bài toán tính tổng
• Bài toán tính tích
• Bài toán tìm giá trị lớn nhất, nhỏnhất
ttdung@utc2.edu.vn 60
 Bàitoánđếm
 Begin i = 1, 2, ,n
 Input: n S
 Bt logic
 i = 1, 2, ,n Đ
 Dem = Dem + 1
 Input: ai
 Output: Dem
 Dem = 0
 End
ttdung@utc2.edu.vn 61
Bài tập
1. Nhập dãy số nguyên gồm n phần tử, đếm số phần tử 
 chia 5 dư 2 và nằm trong đoạn [x, y] với x, y nhập từ 
 bàn phím.
2. Nhập dãy số nguyên gồm n phần tử, tính trung bình 
 cộng và trung bình nhân các phần tử chẵn, và không 
 nằm trong đoạn [-35, 25].
3. Nhập dãy số nguyên gồm n phần tử.
 a. Đếm số cặp 2 phần tử liên tiếp thỏa mãn điều kiện số
 sau lớn hơn số trước.
 b. Đếm số cặp 2 phần tử liên tiếp có tích chia hết cho
 tổng.
ttdung@utc2.edu.vn 62
Bài tập
 c. Đếm số cặp 3 phần tử liên tiếp có tổng chia hết cho 5.
 d. Đếm số cặp 3 phần tử liên tiếp tạo thành cấp số cộng.
 4. Cho n điểm nằm trong mặt phẳng tọa độ xOy.
 a. Đếm số điểm nằm trong góc phần tư thứnhất.
 b. Đếm số điểm nằm trên đường phần giác của góc phần tưthứ 
 nhất.
 c. Đếm số điểm nằm phía trên đường phần giác của góc phần tư
 thứ nhất.
 d. Đếm số điểm nằm trong hình tròn tâm O bán kính R(điểm nằm
 trên đường trònđược coi là nằm trong hình tròn).
 e. Đếm số đoạn thẳng cắt trục hoành.
ttdung@utc2.edu.vn 63
Bàitoántínhtổng
 Begin
 Input: n i = 1, 2, ,n
 i = 1, 2, ,n
 S = S + ai
 Input: ai
 Output: S
 S = 0
 End
ttdung@utc2.edu.vn 64
Bàitoántínhtích
 Begin
 Input: n i = 1, 2, ,n
 i = 1, 2, ,n
 T = T * ai
 Input: ai
 Output: T
 T =1
 End
ttdung@utc2.edu.vn 65
Ví dụ
 1. Nhập số nguyên dương n và số thực x.Tính
 1+ 1 + 2 1 + 푛
 푆 = 2 + + + ⋯+
 2 3 푛 +1
 2. Nhập số nguyên dương n và số thực x.Tính
 +3 +5 + 2푛 +1
 푆 = 2 + + + ⋯+
 9 11 2푛 +7
 3. Nhập số nguyên dương n và số thực x.Tính
 푆 = + (1 + )3+(2 + )3+ ⋯+ (푛 + )3
 4. Nhập số thực x. Tính
 푆 = + +⋯+ (n lần)
 5. Nhập số nguyên dương n. Tính
 1.3.5. ⋯.푛 (nlẻ) 
 푆 = ቊ
 2.4.6. ⋯.푛 (nchẵn)
 6. Nhập số nguyên dương n và số thực x.Tính
 2 푛
 푆 = 2013 + + + ⋯+
ttdung@utc2.edu.vn 2! 푛! 66
Bàitoántìm gtln(gtnn)
 Begin i = 1, 2, ,n
 Input: n S
 Max <ai
 i = 1, 2, , n Đ
 Max =ai
 Input: ai
 Output: Max
 Max =a1
 End
ttdung@utc2.edu.vn 67
Ví dụ
1. Cho dãy số thực gồm n phần tử. Tìm một phần tử có GTLN và vị trí của nó trong dãy.
2. Cho dãy số thực gồm n phần tử.
 a. Tìm cặp 2 phần tử liên tiếp có tích nhỏ nhất.
 b. Tìm cặp 3 phần tử liên tiếp có tổng lớn nhất. Tổng đó là bao nhiêu.
3. Cho dãy số nguyên gồm n phần tử.
 a. Tìm phần tử âm nhỏ nhất.
 b. Tìm phần tử chẵn lớnnhất.
 c. Tìm phần tửnhỏ nhất lớn hơn 5.
4. Nhập n điểm trong mặt phẳng tọa độxOy.
 a. Tìm hình tròn nhỏ nhất tâm O chứa tất cả các điểm.
 b. Tìm tọa độ của điểm xa gốc tọa độ nhất.
 c. Trong số các điểm nằm trong góc phần tư thứ nhất, xác định khoảng cách từ gốc 
 tọa độ tới điểmgần nhất.
ttdung@utc2.edu.vn 68
Biểu diễn thuật toán bằng giả ngôn ngữ
Giả ngôn ngữ
 – Dựa trên ngôn ngữ lập trình bậc cao.
 – Gần với ngôn ngữ tự nhiên của con người.
 – Ví dụ:
 • Ngôn ngữ giả Pascal (tựa Pascal) có các ký pháp khá giống với
 ngôn ngữ lập trình Pascal, được rút gọn sao cho dễ diễn đạt.
Giả ngôn ngữ được đưa ra với mục đích diễn đạt các giải
 thuật sao cho gần với ngôn ngữ lập trình và ngôn ngữ tự
 nhiên.
Sử dụng giả ngôn ngữ khiến việc chuyển từ giải thuật sang
 chương trình dễ dàng hơn.
ttdung@utc2.edu.vn 69
Giải thuật tính tổng N số tự nhiên đầu tiên
 • Nhập N 
 i:=0 
 S:=0 
 REPEAT
 • S:=S+i
 • i:=i+1
 • UNTIL (i>N)
 • In S
ttdung@utc2.edu.vn 70
Thiết kế thuật toán
 Các bước giải bài toán trên máy tính:
 – Xác định bài toán
 – Thiết kế giải thuật
 – Viết chương trình
 – Hiệu chỉnh, làm tinh
 – Viết tài liệu
 Thiết kế giải thuật là từ yêu cầu của một bài toán, diễn đạt một 
 giải thuật giải quyết bài toán đó.
 – Mô-đun hoá việc giải quyết bài toán.
 – Tinh chỉnh từng bước.
 Phân tích giải thuật
 – Xem xét các tiêu chuẩn của giải thuật có được thoả mãn không, nếu 
 có thì đến mức độ nào.
ttdung@utc2.edu.vn 71
Thiết kế từ trên xuống
Các bài toán lớn đòi hỏi giải thuật có quy mô lớn.
Mô-đun hoá
– Bài toán = nhiều mô-đun
– Mô-đun lớn = nhiều mô-đun con.
– Việc giải quyết một mô-đun ở mức thấp nhất là “đủ đơn giản”
→ Chia để trị.
• Thiết kế từ trên xuống (top- down design): Bài toán 
 được xem xét từ tổng quát đến chi tiết.
ttdung@utc2.edu.vn 72
Bài toán giải phương trình bậc 2
 GIẢI PHƯƠNG TRÌNH BẬC II
 NHẬP HỆ SỐ XỬ LÝ HIỂN THỊ KẾT QUẢ
 TRƯỜNG HỢP SUY BIẾN TRƯỜNG HỢP KHÔNG SUY BIẾN
 TÍNH DELTA TÍNH NGHIỆM THEO DELTA
ttdung@utc2.edu.vn 73
Phương pháp tinh chỉnh từng bước
 Phương pháp tinh chỉnh từng bước (stepwise refinement)
 – Ban đầu, sử dụng ngôn ngữ tự nhiên để diễn tả những
 công việc chính của giải thuật.
 – Các bước sau, các công việc được chi tiết hoá dần dần,
 ngôn ngữ tự nhiên được thay thế dần dần bằng giả ngôn
 ngữ.
 – Cuối cùng, giả ngôn ngữ được chuyển sang ngôn ngữ lập
 trình
Đặc điểm
 – Thể hiện rõ ý tưởng thiết kế từ trên xuống
 – Gắn liền việc thiết kế giải thuật với việc lập trình
ttdung@utc2.edu.vn 74
Bài toán sắp xếp dãy số (tăng dần)
 Phác thảo “thô” với những “ý tưởng cơ bản”
 – “Từ dãy các số chưa được sắp xếp, tìm số nhỏ nhất và đưa lên đầu”
 – Lặp lại quy trình trên tới khi dãy chưa được sắp xếp trở thành rỗng.
 Ban đầu, dãy chưa sắp xếp là dãy đã cho, dãy đã sắp xếp là 
 rỗng.
 Lưu trữ dãy bằng “mảng” (danh sách các số), đưa số nhỏ nhất (aj) 
 lên đầu danh sách là đổi chỗ nó với số đầu tiên.
 Đổi chỗ
 – Số trung gian := aj
 – aj := số đầu tiên
 – Số đầu tiên : = số trung gian
 , cuối cùng ta được chương trình với ngôn ngữ cụ thể
ttdung@utc2.edu.vn 75
Phân tích thuật toán
  Tính đúng đắn
 – Chạy thử nghiệm, đối chiếu kết quả → phát hiện được tính sai.
 – Dùng công cụ toán học để chứng minh → tính đúng đắn.
  Tính đơn giản
 – Giải thuật có dễ hiểu, dễ lập trình không?
  Tính hiệu quả
 – Đơn giản chưa chắc đã hiệu quả.
 – Đối với nhiều bài toán, tính hiệu quả là quan trọng, các giải thuật 
 đơn giản lại gây tốn tài nguyên, chạy chậm.
 – Thời gian tính toán → Độ phức tạp tính toán
 – Những giải thuật hiệu quả phải có độ phức tạp (thời gian) tính toán chấp
 nhận được.
  Tính hữu hạn dừng
 – Chứng minh, suy luận
 – Chạy thử
ttdung@utc2.edu.vn 76
Một số thuật toán thường gặp
 Bài toán tìm kiếm
 – Thuật toán tìm kiếm tuyến tính
 – Thuật toán tìm kiếm nhị phân
 Bài toán tìm số USCLN của 2 số
 – Thuật toán lặp, kiểm tra các giá trị từ 1,2,...,min(a, b)
 – Thuật toán phân tích các số nguyên đã cho thành các thừa số
 nguyên tố.
 – Thuật toán euclide
 Bài toán sắp xếp dãy tăng/giảm dần
 – Thuật toán nổi bọt (bubble sort)
 – Thuật toán chọn trực tiếp (selection sort)
 – Thuật toán chèn trực tiếp (insertion sort)
 – Thuật toán sắp vun đống (heap sort)
ttdung@utc2.edu.vn 77
Một số thuật toán thường gặp (tt)
 Thuật toán đệ quy
 – Định nghĩa: Một thuật toán được gọi là đệ quy nếu 
 nó giải bài toán bằng cách rút gọn liên tiếp bài 
 toán ban đầu tới bài toán đồng dạng với dữ liệu 
 đầu vào nhỏ hơn.
 – Ví dụ:
 Bài toán tính n!
 Bài toán tìm số thứ n của dãy số Fibonaci
 Bài toán tìm USCLN của 2 số a, b
 Bài toán tìm kiếm nhị phân
 Bài toán tháp Hà Nội
 ttdung@utc2.edu.vn 78
Bài tập
Vẽ sơ đồ biểu diễn thuật toán tìm trung bình cộng
 của dãy số a1, a2, , an
Vẽ sơ đồ biểu diễn thuật toán tìm TBC các số
 chẵn và chia hết cho 5 trong dãy số a1, a2, , an
Vẽ sơ đồ biểu diễn thuật toán đếm xem trong dãy
 số a1, a2, , an có bao nhiêu cặp có chỉ số liên
 tiếp (vd: a2, a3) thỏa điều kiện tích chúng chia hết
 tổng của chúng.
Hãy vẽ sơ đồ thuật toán tìm và in ra các số là số
 nguyên tố trong dãy số a1, a2,...,aN
ttdung@utc2.edu.vn 79
Bài tập (tt)
 3. Hãy vẽ sơ đồ thuật toán tìm trong số các phần tử của dãy a1, a2,...,aN
 có bao nhiêu cặp (ai, aj) với i≠j thỏa điều kiện ai+aj = x
 4. Hãy vẽ sơ đồ thể hiện thuật toán đổi một số nguyên dương N sang hệ
 đếm cơ số 2 (hệ nhị phân).
 5. Hãy vẽ sơ đồ thể hiện thuật toán giải phương trình bậc 2: ax2+ bx + c =
 0
 6. Hãy vẽ sơ đồ thể hiện toán tìm tích của 2 ma trận Amxn và Bnxp
 7. Hãy vẽ sơ đồ thể hiện thuật toán tìm độ dài của đường gấp khúc đi qua
 N điểm trên mặt phẳng M1(x1, y1), M2(x2, y2),....,Mn(xn, yn).
 8. Vẽ sơ đồ thể hiện thuật toán sắp xếp lại dãy số a1, a2,...,an theo thứ tự
 giảm dần.
 9. Vẽ sơ đồ thể hiện thuật toán tìm các phần tử trong dãy a1, a2,...,an
 thỏa điều kiện ai = ai-1 + ai-2 + ...+ a2+ a1
 10.Vẽ sơ đồ thể hiện thuật toán tìm trung bình cộng của các phần tử là số
 chính phương trong dãy a1, a2,...,aN 80