Tài liệu, ebook Công Nghệ Thông Tin

Tóm tắt 3.2. Sắp xếp topo trên DAG: Thuật toán của Tarjan 3.3. Tìm đường đi ngắn nhất  Single-source: Thuật toán tham ăn Dijsktra  All-pairs: Thuật toán quy hoạch động Floyd 3.4. Tìm cây bao trùm ngắn nhất  Thuật toán tham ăn Prim  Thuật toán tham ăn Kruskal

34 trang | Chia sẻ: thucuc2301 | Ngày: 20/11/2020 | Lượt xem: 776 | Lượt tải: 0

Đi qua đồ thị theo bề rộng  Sử dụng kĩ thuật tìm kiếm theo bề rộng  Breadth-First Search  Ý tưởng của tìm kiếm theo bề rộng xuất phát từ đỉnh v  Từ đỉnh v ta lần lượt đi thăm tất cả các đỉnh u kề đỉnh v mà u chưa được thăm.  Sau đó, đỉnh nào được thăm trước thì các đỉnh kề nó cũng sẽ được thăm trước.  Quá trình trên sẽ được tiếp tục ...

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

Ứng dụng GPS và GIS cho phép quản lý toàn bộ dữ liệu không gian và thuộc tính của các tuyến xe buýt theo thời gian thực, tạo ra khả năng điều phối hoạt động và chia sẻ dữ liệu (được ghi nhận bởi BlackBox) đồng bộ giữa Trung tâm điều hành với các cơ sở quản lý. Áp dụng hệ thống đề xuất để phục vụ công tác quản lý và điều hành xe buýt trên địa bàn Th...

8 trang | Chia sẻ: dntpro1256 | Ngày: 20/11/2020 | Lượt xem: 664 | Lượt tải: 0

Sắp xếp trong thời gian tuyến tính 65 diepht@vnu  Thuật toán sắp xếp đếm  counting sort  không so sánh các cặp phần tử  Giả sử dãy số nguyên nằm trong một khoảng nào đó

87 trang | Chia sẻ: thucuc2301 | Ngày: 20/11/2020 | Lượt xem: 698 | Lượt tải: 0

Bài toán ba lô: bài toán con 27 diepht@vnu  Khảo sát các tập con các đồ vật:  nếu có các đồ vật { i0, i1 . in } thì  ta xét tập con các đồ vật i0 . ik.  Khảo sát tất cả khối lượng cực đại nhỏ hơn:  nếu khối lượng cực đại của bài toán gốc là m thì  với mỗi số nguyên w trong khoảng 0.m, tìm giá trị cực đại của tập con của i0 . ik có khố...

34 trang | Chia sẻ: thucuc2301 | Ngày: 20/11/2020 | Lượt xem: 774 | Lượt tải: 0

Thuật toán Huffman  Với mỗi ký tự xuất hiện trong xâu nguồn, ta tạo ra một đỉnh chứa ký tự đó  gắn với giá trị ưu tiên bằng tần suất  Từ tập các cây chỉ có một đỉnh, tại mỗi bước ta kết hợp hai cây thành một cây  đỉnh cha sẽ gắn với giá trị ưu tiên bằng tổng độ ưu tiên các con  ta cần chọn hai cây nhị phân có mức ưu tiên nhỏ nhất đ...

45 trang | Chia sẻ: thucuc2301 | Ngày: 20/11/2020 | Lượt xem: 753 | Lượt tải: 0

Nhận xét (2/2)  Thăm dò bình phương  Ưu điểm: tránh được nhược điểm của thăm dò tuyến tính  Nhược điểm: không cho phép ta tìm đến tất cả các vị trí trong mảng  phép insert có thể không thực hiện được  nếu cỡ của mảng là số nguyên tố, thì thăm dò bình phương cho phép ta tìm đến một nửa số vị trí trong mảng  Băm kép  nếu cỡ của mảng ...

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

Phân tích độ phức tạp  Xét tập hợp có n phần tử cài đặt bởi cây tìm kiếm nhị phân độ cao h  không gian sử dụng là O(n)  các hàm find, insert và erase thực hiện trong thời gian O(h)  Độ cao h bằng O(n) trong trường hợp xấu nhất và O(log n) trong trường hợp tốt nhất

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

Phép toán gán  Nếu được cho các khai báo sau StringVar str1(10), str2(20); thì câu lệnh str1 = str2; là hợp lệ.  Nhưng vì thành phần value của StringVar là một con trỏ nên str1.value và str2.value trỏ tới cùng một vùng nhớ

63 trang | Chia sẻ: thucuc2301 | Ngày: 20/11/2020 | Lượt xem: 751 | Lượt tải: 0

Các dạng DSLK 28 diepht@vnu  DSLK đơn  singly linked list, uni-directional list, one-way list  DSLK kép  doubly linked list, bi-directional list  DSLK vòng tròn  ring list

32 trang | Chia sẻ: thucuc2301 | Ngày: 20/11/2020 | Lượt xem: 850 | Lượt tải: 0