• Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 14: Xấp xỉ - Lê Nguyên KhôiGiáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 14: Xấp xỉ - Lê Nguyên Khôi

    Đa mục tiêu (multiobjective) Thỏa mãn các ràng buộc không đơn giản Chuyển ràng buộc khó thành mục tiêu Mục tiêu song song / theo thứ tự Kiểu hình – kiểu gien (phenotype – genotype) Phenotype: xác định lời giải nào tốt hơn Genotype: cung cấp nhiều thông tin hơn Dữ liệu thời gian thực (real-time data) Sự cần thiết tìm lời giải cận tối ưu D...

    pdf21 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 782 | Lượt tải: 0

  • Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 13: Đường đi ngắn nhất - Lê Nguyên KhôiGiáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 13: Đường đi ngắn nhất - Lê Nguyên Khôi

    Nếu đỉnh k nằm trên đường đi ngắn nhất từ i tới j thì đường đi từ I tới k và đường đi từ k tới j là đường đi ngắn nhất Nếu 〖c_ij〗^((k)) là độ dài đưuòng đi không qua k, tức là đường đi này chỉ đi qua các đỉnh trong S^((k-1)) , khi đó 〖c_ij〗^((k))= 〖c_ij〗^((k-1)) Nếu 〖c_ij〗^((k)) là độ dài đường đi qua k, thì trên đường đi này đoạn từ i tới k có...

    pdf31 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 829 | Lượt tải: 1

  • Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 12: Đồ thị - Lê Nguyên KhôiGiáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 12: Đồ thị - Lê Nguyên Khôi

    G = (V, E) là đồ thị định hướng không chu trình Sắp xếp các đỉnh đồ thị thành một danh sách Sao cho nếu có cung (u,v) thì u cần đứng trước v trong danh sách đó Sắp xếp topo dựa trên DFS Thực hiện DFS trên đồ thị Khi kết thúc quá trình DFS trên một đỉnh u thì thêm u vào cuối danh sách Kết thúc DFS trên toàn đồ thị, đảo ngược danh sách, ...

    pdf22 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 770 | Lượt tải: 0

  • Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 11: Tham ăn - Lê Nguyên KhôiGiáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 11: Tham ăn - Lê Nguyên Khôi

    Xóa một cạnh bất kỳ (u, v) ∈ T. Thì, cây T được chia thành 2 cây con T_1 và T_2 Định lý. Cây con T_1 là cây bao trùm nhỏ nhất của G_1=(V_1, E_1) là đồ thị con của G bao gồm các đỉnh của T_1 V_1 = đỉnh của T_1 E_1= {(x,y)∈E:x,y ∈ V_1 } Tương tự với T_2 Thuật Toán Prim U: tập các đỉnh kề các cạnh trong tập cạnh T Ban đầu tập U chứa một đ...

    pdf25 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 787 | Lượt tải: 0

  • Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 10: Lập trình động - Lê Nguyên KhôiGiáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 10: Lập trình động - Lê Nguyên Khôi

    Kiểm tra tất cả các dãy con của x[1 . . m] xem có phải dãy con của y[1 . . n] không Phân tích Kiểm tra = 0 (n) cho mỗi dãy con. Có 2^m dãy con của x. Thời gian chạy xấu nhất = 0 (n2m), thời gian hàm mũ.

    pdf22 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 734 | Lượt tải: 0

  • Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 9: Chặn dưới sắp xếp - Lê Nguyên KhôiGiáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 9: Chặn dưới sắp xếp - Lê Nguyên Khôi

    Giả thiết dữ liệu trong khoảng [0, 1) Tạo ngẫu nhiên Phân bố đồng đều Độc lập với nhau Ý tưởng Chia khoảng dữ liệu thành phần bằng nhau Phân bố dữ liệu vào các giỏ Sắp xếp từng giỏ Liệt kê phần tử trong giỏ Sắp Xếp Giỏ Trường hợp tốt nhất, mỗi dữ liệu được phân vào một giỏ Trường hợp khác, sắp xếp từng giỏ sử dụng sắp xếp chè...

    pdf26 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 785 | Lượt tải: 0

  • Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 8: Bảng băm - Lê Nguyên KhôiGiáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 8: Bảng băm - Lê Nguyên Khôi

    Tuyến tính Ưu điểm: xét tất cả các vị trí trong mảng Phép chèn luôn thực hiện được, trừ khi mảng đầy Nhược điểm: Dữ liệu tập trung thành các đoạn Tìm kiếm tuần tự trong từng đoạn Bình phương Ưu điểm: tránh nhược điểm thăm dò tuyến tính Nhược điểm: không xét tất cả các vị trí trong mảng Phép chèn có thể không thực hiện được Băm k...

    pdf19 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 726 | Lượt tải: 0

  • Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 7: Cây tìm kiếm nhị phân - Lê Nguyên KhôiGiáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 7: Cây tìm kiếm nhị phân - Lê Nguyên Khôi

    Các thao tác chèn và xóa có thể làm thay đổi tính chất của cây Do chính các thao tác này Đổi màu các nút Cấu trúc lại các kết nối nút Phép xoay: đảm bảo thứ tự trong của khóa Phép thực hiện trong thời gian 0 (1) Georgy Adelson-Velsky & Evgenil Landis đề xuất năm 1962 Độ cao 2 cây của của một nút khác nhau nhiều nhất 1 Thời gian 0(log n) ...

    pdf22 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 814 | Lượt tải: 0

  • Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 6: Cấu trúc cây - Lê Nguyên KhôiGiáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 6: Cấu trúc cây - Lê Nguyên Khôi

    Chèn liên tục vào MinHeap, nhưng không khôi phục tính chất thứ tự bộ phận.Khôi phục tính chất thứ tự bộ phận (sử dụng downheap) bắt đầu từ đỉnh chính giữa Sắp Xếp Cây Thứ Tự Bộ Phận – So Sánh Giống sắp xếp gộp (merge sort) Độ phức tạp 0 (n logn) Giống sắp xếp chèn (insertion sort) In-place algortihm

    pdf35 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 857 | Lượt tải: 0

  • Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 5: Sắp xếp nhanh - Lê Nguyên KhôiGiáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 5: Sắp xếp nhanh - Lê Nguyên Khôi

    Phân hoạch dựa trên phần tử ngẫu nhiên: Thời gian chạy không phụ thuộc vào dữ liệu đầu vào. Không cần giả thiết về phân phối của dữ liệu đầu vào. Không dữ liệu nào tạo nên trường hợp xấu nhất. Trường hợp xấu nhất chỉ do hàm sinh số ngẫu nhiên. Giả thiết khi phân tích thời gian chạy Mảng bao gồm các phần tử khác nhau Mảng có các phần tử g...

    pdf20 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 745 | Lượt tải: 0