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

Bài toán Range Minimum Query RMQ preprocessing(){ for (i = 0; i < N; i++) M[0,i] = i; for (j = 0; 2j ≤ N; j++){ for(i = 0; i + 2j -1 < N; i++){ if a[M[j-1,i]] < a[M[j-1,i+2j-1]] then{ M[j,i] = M[j-1,i]; }else{ M[j,i] = M[j-1,i+2j-1];  Truy vấn RMQ(i,j)  k = [log(j-i+1)]  RMQ(i,j) = M[k,i] nếu a[M[k,i]] ≤ a[M[k, j-2k+1]] M[k, j-2k+1]...

6 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 467 | Lượt tải: 0

Quy hoạch động sử dụng deque  Định nghĩa bài toán con  S(i): tổng cực đại của dãy con của dãy a1, , ai thỏa mãn đề bài mà phần tử cuối cùng là ai  Công thức quy hoạch động  S(i) = max(ai + S(j) | L1 ≤ i – j ≤ L2}  Khởi tạo deque, lưu trữ các chỉ số j sao cho S(j) không tăng và là ứng cử viên để tính toán các bài toán con S(i)  Mỗi khi...

6 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 343 | Lượt tải: 0

Truy vết  Bài toán dãy con tăng dần dài nhất  prev[i]: chỉ số của phần tử trước phần tử a[i] trong lời giải của bài toán con Pi.  select: chỉ số của bài toán con mà lời giải của bài toán con đó là lời giải của bài toán xuất phát 16Truy vết incsubseq(a1,a2,. . ., aN){ s[1] = 1; prev[1] = -1; res = s[1]; select = 1; for i = 2 → N do{ s[...

20 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 384 | Lượt tải: 0

Giảm để trị  Chia bài toán (chia theo dữ liệu) xuất phát thành các bài toán con  Giải 1 bài toán con và dẫn ra lời giải của bài toán xuất phát (các bài toán con khác không cần giải  tránh dư thừa)  Tìm kiếm nhị phân  Tính lũy thừa Tìm kiếm nhị phân Mã giả bSearch(a,left, right, x){ if left = right then{ if a[left] = x return left; ...

31 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 404 | Lượt tải: 0

huật toán nhánh và cận 64  Duyệt nhánh và cận:  Phương án bộ phận (a1, , ak) trong đó a1 gán cho x1, ak gán cho xk  Phương án (a1, , ak, bk+1, ,bn) là một phương án đầy đủ được phát triển từ (a1, ,ak) trong đó bk+1 gán cho xk+1, , bn được gán cho x n  Với mỗi phương án bộ phận (x1, , xk), hàm cận dưới g(x1, , xk ) có giá trị khôn...

66 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 414 | Lượt tải: 0

Hàng đợi  Cấu trúc dữ liệu cất trữ các đối tượng một cách tuyến tính  Thao tác  Thêm 1 phần tử  Lấy ra 1 phần tử  Nguyên tắc: vào trước – ra trước 12Stack 13 #include using namespace std; int main(){ stack S; for(int i = 0; i < 5; i++){ S.push(i); } while(!S.empty()){ int v = S.top(); S.pop(); cout << ...

15 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 390 | Lượt tải: 0

- Bước 1: Giả sử ở phần trên, sinh viên đã quan sát được địa chỉ IP phân giải từ tên miền nct.soict.hust.edu.vn của máy chủ Web là X. Điền giá trị ip.addr == X (Lưu ý: Thay X bằng địa chỉ IP đã quan sát được) vào mục Filter của Wireshark. Sinh viên sẽ quan sát thấy các thông điệp mà máy trạm trao đổi với máy chủ Web. Câu hỏi 4(1 điểm): Trước khi t...

6 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 1088 | Lượt tải: 1

Câu hỏi 4(1 điểm): Xác định các thông số sau của gói tin • STT gói tin (No.): • Địa chỉ IP nguồn: • Địa chỉ IP đích: • Số hiệu cổng nguồn: • Số hiệu cổng đích: • Sequence Number: • ACK Number: • Kích thước phần tiêu đề TCP: • Kích thước phần dữ liệu: • Các cờ được thiết lập: • Gói tin này được đóng gói vào gói tin của giao thức tầng mạng...

8 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 577 | Lượt tải: 0

Bước 3 (1 điểm): Kiểm tra kết nối (cần demo với trợ giảng) Đến lúc này nếu các cấu hình đều đúng thì các máy ở các mạng đã có thể chuyển dữ liệu cho nhau. Sử dụng lệnh traceroute để kiểm tra tính thông suốt của các kết nối giữa máy trạm hn- workstation và sg-workstation, dn-workstation. 3.4 Dịch vụ DHCP và Kết nối đến ISP Công ty muốn kết nối đế...

9 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 559 | Lượt tải: 0

Giao thức ICMP ICMP (Internet Control Message Protocol) là một giao thức báo cáo lỗi, thông báo cho sender biết việc gửi data đi có vấn đề, cũng giống như bộ định tuyến sử dụng để tạo thông báo lỗi đến địa chỉ IP nguồn khi các sự cố mạng ngăn chặn việc phân phối các IP packages. ICMP tạo và gửi thư đến địa chỉ IP nguồn, cho biết rằng một gateway v...

3 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 451 | Lượt tải: 0