Bài giảng tin học đại cương chương 4 lê thị ngọc thảo

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (674.75 KB, 29 trang )

Trang 1<div class="page_container" data-page="1">

CHƯƠNG 4:

CHƯƠNG TRÌNH & GIẢI THUẬT

</div>Trang 2<div class="page_container" data-page="2">

Các khái niệm (1)

z

Thuật tốn

•

Cách hiểu đơn giản

•

Tập các hướng dẫn thực hiện một cơng việc.

•

Tập hữu hạn các hướng dẫn rõ ràng để người giải tốn có thể theo đó mà giải quyết được vấn đề.

•

Một phương pháp thể hiện lời giải của vấn đề.

•

Algorithm: nhà tốn học Trung Á

•

Muhammad Bin Musa Al-Khwarizmi

•

class="text_page_counter">Trang 3<div class="page_container" data-page="3">

Các khái niệm (2)

z

Thuật tốn (tt)

•

Trong khoa học máy tính

•

Một dãy hữu hạn các bước rõ ràng và thực thi được.

•

Q trình hành động theo các bước này phải dừng và

cho được kết quả như mong muốn.

•

Tính xác định

•

Hướng dẫn giải rõ ràng và đúng

•

Tính hữu hạn

</div>Trang 5<div class="page_container" data-page="5">

•

1.Lập danh sách các mơn học theo tên, số đvht

•

2.Sắp thứ tự các mơn học giảm dần theo số đvht

•

3.Chọn ra một mơn học có nhiều đvht nhất

•

Câu hỏi???

</div>Trang 6<div class="page_container" data-page="6">

Các khái niệm (5)

z

Tính mập mờ (tt):

•

Phân biệt mập mờ và chọn lựa có quyết định.

•

Mập mờ là thiếu thơng tin hoặc có nhiều chọn lựa nhưng khơng đủ điều kiện để quyết định.

•

Chọn lựa có quyết định là hoàn toàn xác định duy nhất

trong điều kiện cụ thể của vấn đề

•

Sửa lại:

•

3.Chọn ra một mơn học có nhiều đvht nhất.

•

3.1 Nếu chỉ có một mơn học nhiều đvht nhất: chọn một

•

3.2 Nếu có nhiều mơn học cùng số đvht: sắp xếp tăng dần theo tên môn học trong thứ tự từ điển rối chọn môn đầu tiên.

</div>Trang 7<div class="page_container" data-page="7">

Các khái niệm (6)

z

Tính thực thi được:

•

Hiển nhiên

•

Chỉ xét trong điều kiện hiện tại của bài tốn

•

Cho ví dụ về điều kiện hiện tại:???

z

Tính dừng:

•

Khơng dừng: Lặp vơ tận, bị quẫn

•

Dễ vi phạm nhất

</div>Trang 8<div class="page_container" data-page="8">

Các khái niệm (7)

z

Tính dừng -Ví dụ:

•

Tính tổng các số ngun dương lẻ trong khoảng từ 1 đến n ta có thuật tốn sau :

•

B1. Hỏi giá trị của n.

</div>Trang 9<div class="page_container" data-page="9">

Các khái niệm (8)

z

Tính dừng -Ví dụ:

•

Chỉ dừng khi n chẵn

•

Khi n lẻ phải thay B4 bằng:

•

B4. Nếu i >= n+1 thì sang bước B8, ngược lại sang bước B5

z

Tính đúng:

•

Chứng minh thuật tốn đúng!!!

•

Khó đạt được nhất

</div>Trang 11<div class="page_container" data-page="11">

Các khái niệm (10)

z

Các đặc trưng khác của thuật tốn

•

Ðầu vào và đầu ra (input/output) .

•

Tính hiệu quả (effectiveness): theo tiêu chuẩn

•

Khối lượng tính tốn, khơng gian và thời gian thi hành.

•

Là yếu tố quyết định để đánh giá, chọn lựa

•

Nhiều phương pháp để đánh giá tính hiệu quả của thuật tốn.

•

Tính tổng qt (generalliness) :

•

Áp dụng được cho mọi trường hợp của bài tốn

•

</div>Trang 13<div class="page_container" data-page="13">

Các khái niệm - Ví dụ (2)

•

3. Trường hợp a khác 0 thì

•

3.1. Tính giá trị D = b2-4ac

•

3.2. Nếu D > 0 thì

•

3.2.1. Phương trình có hai nghiệm phân biệt x1,x2

•

3.2.2. Giá trị của hai nghiệm được tính theo cơng thức

</div>Trang 15<div class="page_container" data-page="15">

Các khái niệm - Ví dụ (4)

z

Bài toán : Cho hai số nguyên dương a và b. Tìm ước số chung lớn nhất của a và b.

z

Thuật tốn Euclid

•

1. u cầu cho biết giá trị của a, b.

•

2. a0 = a

•

3. b0 = b

•

4. i = 0

</div>Trang 16<div class="page_container" data-page="16">

Các khái niệm - Ví dụ (5)

•

5. Nếu ai khác bi thì thực hiện các thao tác sau, ngược lại qua bước 7.

</div>Trang 17<div class="page_container" data-page="17">

Các phương pháp biểu diễn

z

Thuật tốn:

•

Một phương pháp thể hiện lời giải bài tốn

•

Phải tn theo một số quy tắc nhất định

z

Có 3 phương pháp biểu diễn thuật tốn :

•

Dùng ngơn ngữ tự nhiên.

•

Dùng lưu đồ-sơ đồ khối (flowchart).

•

Dùng mã giả (pseudocode).

</div>Trang 18<div class="page_container" data-page="18">

Ngôn ngữ tự nhiên

z

Ngơn ngữ thường ngày:

•

Liệt kê các bước của thuật tốn, q trình thực hiện lần lượt (trừ khi có u cầu nhảy_

•

Khơng thể hiện rõ cấu trúc của thuật tốn

•

Dài dịng, có thể gây hiểu lầm hoặc khó hiểu

•

Khơng u cầu người viết hay đọc nắm quy tắc.

•

Khơng có một quy tắc cố định

•

Tính dễ đọc:

•

viết các bước con lùi vào bên phải

•

đánh số bước theo quy tắc phân cấp như 1, 1.1, ...

</div>Trang 19<div class="page_container" data-page="19">

Lưu đồ - sơ đồ khối (1)

z

Cơng cụ trực quan diễn đạt thuật tốn.

•

Biểu diễn bằng mơ hình – hình vẽ

z

Theo dõi được:

•

sự phân cấp các trường hợp

•

q trình xử lý của thuật toán

z

Được dùng trong những thuật tốn

•

rắc rối

</div>Trang 20<div class="page_container" data-page="20">

Lưu đồ - sơ đồ khối (2)

z

Phân biệt hai loại thao tác:

•

Chọn lựa theo một điều kiện nào đó

•

Xử lý, hành động

</div>Trang 21<div class="page_container" data-page="21">

Lưu đồ - sơ đồ khối (3)

z

Chọn lựa theo một điều kiện nào đó

•

Decision

•

Biểu diễn bằng một hình thoi, bên trong chứa biểu thức điều kiện.

•

Ví dụ: thao tác "nếu a = b thì thực hiện thao

tác B2, ngược lại thực hiện B4" là thao tác

chọn lựa

</div>Trang 22<div class="page_container" data-page="22">

Lưu đồ - sơ đồ khối (4)

z

Xử lý, hành động.

•

Process

•

Biểu diễn bằng một hình chữ nhật, bên trong chứa nội dung xử lý.

•

Ví dụ: "Chọn một mơn học và in ra." là một

thao tác thuộc loại hành động.

</div>Trang 23<div class="page_container" data-page="23">

Lưu đồ - sơ đồ khối (5)

z

Q trình thực hiện các thao tác:

•

Đường đi – route

•

Biểu diễn bằng cung có hướng

•

nối giữa 2 thao tác: thực hiện lần lượt

</div>Trang 24<div class="page_container" data-page="24">

Lưu đồ - sơ đồ khối (6)

z

Thao tác chọn lựa: có thể có hai hướng đi

•

một hướng ứng với điều kiện thỏa

•

một hướng ứng với điều kiện khơng thỏa.

•

2 cung có nhãn

•

Đ/Đúng,Y/Yes

•

S/Sai,N/No

</div>Trang 25<div class="page_container" data-page="25">

Lưu đồ - sơ đồ khối (7)

z

Ðiểm cuối (terminator)

•

Biểu diễn bằng hình ovan

•

Điểm khởi đầu

•

chỉ có cung đi ra

•

bên trong ovan ghi chữ: bắt đầu/start/begin

•

Điểm kết thúc

•

Chỉ có cung đi vào

•

bên trong ovan ghi chữ: kết thúc/end

</div>Trang 26<div class="page_container" data-page="26">

Phương trình thuật toán giải pt bậc 2. Đường chấm ứng với trường hợp nghiệm kép, ví dụ: a=1,b=2,c=1

</div>Trang 27<div class="page_container" data-page="27">

Lưu đồ - sơ đồ khối (8)

z

Điểm nối (connector)

•

Nối các phần khác nhau của

</div>Trang 28<div class="page_container" data-page="28">

Mã giả (pseudo code) (1)

z Vay mượn các cú pháp của một ngơn ngữ lập

trình

•

dùng một phần ngơn ngữ tự nhiên

•

bị phụ thuộc vào ngơn ngữ lập trình.

z Mọi ngơn ngữ lập trình đều có những thao tác

</div>Trang 29<div class="page_container" data-page="29">

Mã giả (2)

Một đoạn mã giả của thuật toán giải pt bậc hai

if Delta > 0 then begin

</div>

Bài giảng tin học đại cương chương 4 lê thị ngọc thảo

<b>CHƯƠNG 4: </b>

<b>CHƯƠNG TRÌNH & GIẢI THUẬT</b>

<b>Các khái niệm (1)</b>

Thuật tốn

•

•

•

•

•

•

•

<b>Các khái niệm (2)</b>

Thuật tốn (tt)

•

•

•

•

•

•

•

•

•

•

<b>Các khái niệm (5)</b>

Tính mập mờ (tt):

•

•

•

•

•

•

•

<b>Các khái niệm (6)</b>

Tính thực thi được:

•

•

•

Tính dừng:

•

•

<b>Các khái niệm (7)</b>

Tính dừng -Ví dụ:

•

•

<b>Các khái niệm (8)</b>

Tính dừng -Ví dụ:

•

•

•

Tính đúng:

•

•

<b>Các khái niệm (10)</b>

Các đặc trưng khác của thuật tốn

•

•

•

•

•

•

•

•

<b>Các khái niệm - Ví dụ (2)</b>

•

•

•

•

•

<b>Các khái niệm - Ví dụ (4)</b>

Bài toán : Cho hai số nguyên dương a và b. Tìm ước số chung lớn nhất của a và b.

<b>Thuật tốn Euclid</b>

•

•

•

•

<b>Các khái niệm - Ví dụ (5)</b>

•

<b>Các phương pháp biểu diễn</b>

Thuật tốn: