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 />