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

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.
Nội dung trích xuất từ tài liệu:
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ôiThiết Kế & Đánh Giá Thuật ToánPhân Tích Thuật ToánTS. Lê Nguyên KhôiTrường Đại Học Công Nghệ - ĐHQGHNNội DungThuật toánBài toán sắp xếpSắp xếp chènPhân tích thời gian chạy sắp xếp chèn1Thuật ToánMột thủ tục tính toán được định nghĩa rõ ràngMột chuỗi các bước tính toánNhận một tập các giá trị đầu vàoTrả một tập các giá trị đầu raTính đúng đắn: với tất cả các tập giá trị đầuvào, thuật toán đưa ra tập giá trị đầu ra đúng2Bài ToánSắp xếpTìm kiếmMạng Internet (Định tuyến dữ liệu)Thương mại điện tửDoanh nghiệp sản xuấtĐường đi ngắn nhấtChuỗi chung dài nhấtVân vân …3Một Số Vấn Đề KhácCấu trúc dữ liệuHiệu quả:Cách lưu trữ và tổ chức dữ liệu tạo điều kiện truycập và thay đổi một cách dễ dàngP: thuật toán có thể chạy trong thời gian đa thứcNP-complete: không thể chạy trong khoảng thời gianhợp lýSong song:Nhiều phép tính mỗi giây bằng nhiều lõi4