intTypePromotion=1
ADSENSE

Bài giảng Thiết kế và đánh giá thuật toán: Phân tích thuật toán - TS. Lê Nguyên Khôi

Chia sẻ: N N | Ngày: | Loại File: PDF | Số trang:29

33
lượt xem
2
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Thiết kế và đánh giá thuật toán: Phân tích thuật toán" cung cấp cho người học các kiến thức: Thuật toán, bài toán sắp xếp, sắp xếp chèn, phân tích thời gian chạy sắp xếp chèn. Mời các bạn cùng tham khảo.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Thiết kế và đánh giá thuật toán: Phân tích thuật toán - TS. Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán<br /> Phân Tích Thuật Toán<br /> TS. Lê Nguyên Khôi<br /> Trường Đại Học Công Nghệ - ĐHQGHN<br /> <br /> Nội Dung<br /> <br /> <br /> Thuật toán<br /> <br /> <br /> <br /> Bài toán sắp xếp<br /> <br /> <br /> <br /> Sắp xếp chèn<br /> <br /> <br /> <br /> Phân tích thời gian chạy sắp xếp chèn<br /> <br /> 1<br /> <br /> Thuật Toán<br /> <br /> <br /> <br /> <br /> <br /> <br /> Một thủ tục tính toán được định nghĩa rõ ràng<br /> Một chuỗi các bước tính toán<br /> Nhận một tập các giá trị đầu vào<br /> Trả một tập các giá trị đầu ra<br /> Tính đúng đắn: với tất cả các tập giá trị đầu<br /> vào, thuật toán đưa ra tập giá trị đầu ra đúng<br /> <br /> 2<br /> <br /> Bài Toán<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> Sắp xếp<br /> Tìm kiếm<br /> Mạng Internet (Định tuyến dữ liệu)<br /> Thương mại điện tử<br /> Doanh nghiệp sản xuất<br /> Đường đi ngắn nhất<br /> Chuỗi chung dài nhất<br /> Vân vân …<br /> <br /> 3<br /> <br /> Một Số Vấn Đề Khác<br /> <br /> <br /> Cấu trúc dữ liệu<br /> <br /> <br /> <br /> <br /> Hiệu quả:<br /> <br /> <br /> <br /> <br /> <br /> Cách lưu trữ và tổ chức dữ liệu tạo điều kiện truy<br /> cập và thay đổi một cách dễ dàng<br /> P: thuật toán có thể chạy trong thời gian đa thức<br /> NP-complete: không thể chạy trong khoảng thời gian<br /> hợp lý<br /> <br /> Song song:<br /> <br /> <br /> Nhiều phép tính mỗi giây bằng nhiều lõi<br /> <br /> 4<br /> <br />
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2