Bài giảng Tin học cơ sở

Bài giảng Tin học cơ sở trình bày các nội dung chính sau: Bài toán và thuật toán, các phương pháp biểu diễn thuật toán, các đặc trưng của thuật toán,... Mời các bạn cùng tham khảo để nắm nội dung chi tiết bài giảng.
Nội dung trích xuất từ tài liệu:
Bài giảng Tin học cơ sở ĐẠI HỌC QUỐC GIA HÀ NỘITRƯỜNG ĐẠI HỌC CÔNG NGHỆ BÀIGIẢNG TINHỌCCƠSỞ BÀI 7 . THUẬT TOÁN Giảngviên:ĐÀOKIẾNQUỐC Mobile098.91.93.980 Email:dkquoc@vnu.edu.vnNỘI DUNG Bàitoán và thuật toán Các phương pháp biểu diễn thuật toán Các đặc trưng của thuật toán Input Yêu cầu OutputKHÁI NIỆM BÀI TOÁN Cho số tự n có phải số “có” hay nhiên n nguyên tố hay “không” không Cho hồ sơ Tìm tất cả các sinh Danh sách sv điểm sinh viên viên có điểm trung thoả mãn bình trên 8 Thiết kế hình Tính sức bền Độ bền học, tải trọng Cho một bài toán nghĩa là cho input, và yêu cầu để tìm (tính) ra outputKHÁI NIỆM THUẬT TOÁN Thuật toán (algorithm) là một quá trình gồm một dãy hữu hạn các thao tác có thể thực hiện được sắp xếp theo một trình tự xác định dùng để giải một bài toán Ví dụ : thuật toán Euclid tìm ước số chung lớn nhất của hai số tự nhiên. – USCLN(a,b) = USCLN (b,a)) – Nếu a> b, USCLN(a,b) = USCLN (a-b,b) – USCLN(a,a)= aTHUẬT TOÁN EUCLIDTIM USCLN CỦA HAI SỐ TỰ NHIÊNBài toán: Cho hai số m, n tìm d = USCLN(m,n)1. Bước 1: Kiểm tra nếu m= n thì về bước 5, nếu không thực hiện tiếp bước 22. Bước 2: Nếu m> n thì về bước 4 nếu không thực hiện tiếp bước 33. Bước 3: m VÍ DỤ CÁC BƯỚC CỦA THUẬT TOÁN EUCLID Bước 1: Kiểm tra nếu m= n thì về bước 5, nếu không thực hiện tiếp bước 2m n Bước 2: Nếu m> n thì về bước 4, mn và n. Kết thúc3 6 mCÁC ĐẶC TRƯNG CỦA THUẬT TOÁN Input Output Tính xác định Tính khả thi Tính dừng Tính phổ dụngPHƯƠNG PHÁP BIỂU DIỄN THUẬT TOÁN Dùng các chỉ dẫn Dùng sơ đồ khối Dùng cấu trúc điều khiểnBIỂU DIỄN BẰNG LƯU ĐỒ/SƠ ĐỒ KHỐI Khối thao tác Khối output Khối input đối tượng:= biểu Khối input thức Khởi đầu Kết thúc Khối điều kiện + - Thứ tự xử lý BIỂU DIỄN BẰNG LƯU ĐỒ thuật toán EUCLID Bước 1: Kiểm tra nếu m= n thì về bước 5, nếu không thực hiện tiếp bước 2 Bước 2: Nếu m> n thì về bước 4, nếu không thực hiện tiếp bước 3 Bước 3: m n ? d:= m + -m:=m-n n:= n - m dBIỂU DIỄN BẰNG CẤU TRÚC ĐIỀU KHIỂN Trong khi m n thì lặp lại khối sau: read(m,n); Nếu m > n thì while m n do Bớt m đi một lượng là n if m>n then Điều chỉnh lại giá trị Nếu ngược lại thì m:=m-n của m và n Bớt n đi một lượng là m else n:= n-m; Cho tới khi m = n thì tuyên bố USCLN chính là giá trị chung của write(m); m và n Chương trình trong PASCALHIỆU QUẢ CỦA THUẬT TOÁN Mỗi bài toán có thể có nhiều thuật toán khác nhau: hiệu quả khác nhau – Độ phức tạp về thời gian: quy về số phép tính cơ bản cần được thực hiện – Độ phức tạp không gian: sự tiêu tốn không gian nhớ.VÍ DỤ HIỆU QUẢ TÌM KIẾM Bài toán tìm kiếm: Cho một dãy n số khác nhau a1,a2...ai... an và một số x. Hãy cho biết x có trong dãy số đó hay không và ở vị trí thứ bao nhiêu. Thuật toán tìm kiếm tuần tự như sau:Bước 1. Cho i = 1Bước 2. Nếu ai = x thì chuyển tới bước 5, nếu không thực hiện tiếp bước 3Bước 3. Tăng i lên 1 và kiểm tra i > n. Nếu đúng về bước 4. Nếu sai quay về bước 2Bước 4. Tuyên bố không có số x. Kết thúcBước 5. Tuyên bố số x chính là số thứ i. Kết thúc Số bước tìm trung bình là n/2. Nếu có 1 triệu phần tử thì phải mất khoảng 500.000 phép so sánhHIỆU QUẢ CỦA THUẬT TOÁN Thuật toán 2: Tìm kiếm nhị phân (thu hẹp dần vùng tìm kiếm, đối với danh sách đã được sắp xếp)Bước 1. Cho d := 1, c:=n (d: đầu, c: cuối, g: giữa)Bước 2. Tính g := [(d+c)/2]Bước 3. So x với ag. Nếu x=ag chuyển tới bước 7. Nếu khác thì tiếp tục thực hiện bước 4Bước 4. Nếu d=c thì tuyên bố không có số x và kết thúc. Nếu không thì thực hiện bước 5 tiếp theoBước 5. Nếu x < ag thì thay c bằng ag và quay về bước 2. Nếu không th ...