Font size
WorksheetsBài tập về bài toán NP và NPC
Total questions: 66
Worksheet time: 36mins
Trong các bước sau, bước nào không đúng khi chứng minh bài toán là NPC?
Chứng minh bài toán thuộc NP
Tìm một bài toán trong lớp P để quy dẫn
Quy dẫn bài toán đang xét về bài toán đã biết
Dùng bài toán đã biết là NPC để quy dẫn về bài toán đang xét
Bài toán nào sau đây thuộc NPC?
3-SAT
Phân hoạch tập (Partition)
Tìm kiếm tuyến tính
Nhân hai số nguyên lớn
Bài toán nào sau đây là ví dụ của bài toán NPC:
Bài toán phủ định
Tìm đường đi Hamilton
Bài toán nhân ma trận
Sắp xếp chèn
Trong định lý Cook, bài toán nào được minh chứng đầu tiên là NPC?
A. Partition
B. 3-SAT
C. TSP
D. CIRCUIT-SAT
đặc điểm của bài toán thuộc lớp npc là: Chọn 2 phương án đúng nhất
Không thuộc lớp NP
Là bài toán quyết định
Không thể kiểm định lời giải trong thời gian đa thức
Mọi bài toán trong NP có thể quy dẫn đến nó
Để chứng minh một bài toán là NPC, ta cần:
Chứng minh nó có lời giải duy nhất
Tìm một bài toán NPC có thể quy dẫn về nó
Chứng minh bài toán đó thuộc NP
Chứng minh mọi bài toán P đều quy dẫn về nó
Một bài toán A thuộc lớp NP và mọi bài toán trong lớp NP đều có thể quy dẫn về A trong thời gian đa thức thì:
Bài toán thuộc lớp NP-Hard
Bài toán có thể giải được trong thời gian tuyến tính
Bài toán thuộc lớp NPC
Bài toán không thể là bài toán tối ưu
Một bài toán được gọi là NP-Hard khi:
Có thuật toán không đơn định giải trong thời gian đa thức
Có thể được giải trong thời gian đa thức
Nếu có thuật toán đa thức giải nó thì mọi bài toán trong NP cũng giải được
Mọi bài toán trong NP có thể quy dẫn đến nó
Khẳng định nào sau đây đúng về lớp np_hard: chọn 2 đáp án đúng nhất.
Bao gồm các bài toán mà mọi bài toán NP đều quy dẫn đến
Bao gồm các bài toán mà mọi bài toán NP đều quy dẫn đến
Có thể bao gồm cả bài toán tối ưu
Không chứa các bài toán quyết định
Điều kiện nào cần thỏa mãn để một bài toán được xem là NPC:
A. Thuộc lớp NP
B. Có thể kiểm định nghiệm trong thời gian tuyến tính
C. Không cần là bài toán quyết định
D. Mọi bài toán NP quy dẫn về nó
Trong phép quy dẫn từ KNAPSACK sang PHẠT, điều nào sau đây là đúng khi xét mối liên hệ giữa ba lô và lịch trình?
Mỗi đồ vật được xử lý tại thời điểm cụ thể
Trọng lượng tối đa của ba lô tương đương với hạn định hoàn thành
Mỗi công việc tương ứng với một điểm phạt ứng với trọng lượng
Trọng lượng balo được ánh xạ thành tổng thời gian xử lý cho phép
Trong thuật toán Quicksort, phần tử “chốt” (pivot) được dùng để làm gì?
So sánh các phần tử với phần tử “chốt” để phân hoạch mảng
Sử dụng để phân hoạch mảng
Dùng để lưu trữ giá trị lớn nhất
Dùng để kết thúc đệ quy
Trong mô hình nhân số nguyên cải tiến (thuật toán Strassen), mục đích chính là gì?
Giảm số phép nhân từ 4 còn 3
giảm số phép cộng từ 5 còn 2
Giảm độ phức tạp từ O(n²) xuống O(n^1.59)
loại bỏ phép chia
Trong bài toán Tháp Hà Nội, để di chuyển n đĩa từ cọc nguồn sang cọc đích, ta cần:
Dùng đệ quy chuyển từng đĩa
Chuyển tất cả đĩa cùng lúc
Dùng thuật toán quay lui
Di chuyển n-1 đĩa sang cọc phụ trước
Trong thuật toán Mergesort, các bước chính là gì?
Gọi đệ quy sắp xếp từng nửa
Chia mảng thành hai nửa
Tìm phần tử chốt để phân hoạch
Trộn hai nửa lại với nhau
Các bước cơ bản của kỹ thuật chia để trị bao gồm:
A. Chia nhỏ – Giải quyết – Tổng hợp (kết hợp)
B. Tìm kiếm và duyệt toàn bộ
C. Phân tích và tổng hợp
xử lý đồng thời và lưu trữ
Khi nào việc áp dụng kỹ thuật chia để trị hiệu quả nhất?
Khi bài toán có nhiều vòng lặp lồng nhau
Khi các bài toán con có thể giải đồng thời
Khi bài toán có thể phân tách thành các bài toán con độc lập
Khi cần giảm độ phức tạp bằng phương pháp vét cạn
Hàm đánh giá g(x) trong nhánh cận có vai trò gì?
Hỗ trợ sắp xếp thứ tự mở rộng nhánh
Giúp xác định nhánh nào có khả năng chứa lời giải tốt
Để xác định hàm mục tiêu
Không cần liên quan đến hàm mục tiêu
Trong bài toán TSP với nhánh cận, ta dùng cận dưới g(x) để:
Ưu tiên nhánh có tổng chi phí tạm thời nhỏ nhất
Lựa chọn hành trình ngắn nhất ngay lập tức
Cắt bỏ các nhánh có chi phí không thể tối ưu
Tăng tốc việc liệt kê tất cả các hành trình
Trong cây tìm kiếm của bài toán TSP:
Mỗi nút biểu diễn một hành trình tạm thời
cần xây toàn bộ cây trước khi chọn hành trình tối ưu
cận dưới càng lớn thì phương án càng tốt
nhánh cận giúp rút ngắn số tổ hợp phải xét
Các bước chính của kỹ thuật quay lui gồm
A. Chấp nhận giá trị nếu thoả điều kiện
B. Duyệt ngẫu nhiên các giá trị
C. Loại trừ tất cả các giá trị nhỏ hơn
D. Đưa ra tập để cử cho xi
Để liệt kê dãy nhị phân độ dài n bằng quay lui, ta cần
Tập đề cử là {0,1}
Duyệt tất cả các tổ hợp dãy nhị phân
Sử dụng mảng đánh dấu giá trị đã chọn
Áp dụng cấu trúc cây tìm kiếm tuyến tính
Trong cây tìm kiếm của bài toán TSP (Chọn 2 phương án đúng)
Cần xây toàn bộ cây trước khi chọn hành trình tối ưu
Cận dưới càng lớn thì phương án càng tốt
Nhánh cận giúp rút ngắn số tổ hợp phải xét
Mỗi nút biểu diễn một hành trình tạm thời
Kỹ thuật quay lui hoạt động dựa trên?
Loại bỏ các cấu hình không thỏa mãn tính chất T
Ưu tiên các phương án có giá trị mục tiêu cao
Sinh ra lời giải bằng phương pháp ngẫu nhiên.
Duyệt tất cả phương án có thể theo đệ quy.
Trong bài toán chiếc balo, để xây dựng hàm cận trên cần?
Cộng thêm khả năng tối đa hóa giá trị còn lại
Tính tổng trọng lượng của mọi đồ vật
Sắp xếp đồ vật theo đơn giá giảm dần
xét hết các hoán vị khả thi
trong kỹ thuật nhánh cận khi nào có thể loại bỏ một nhánh?
khi cận dưới của phương án lớn hơn giá trị tối ưu hiện tại
khi cận dưới bằng 0
khi không còn giá trị đề cử
khi phương án không có lời giải
Trong liệt kê hoán vị n phần tử (1, 2, ..., n) Điều kiện chấp nhận là?
sắp xếp dãy theo thứ tự tăng
phần tử xuất hiện nhiều hơn một lần
phần tử chưa xuất hiện trong cấu hình
mỗi giá trị xuất hiện đúng 1 lần
Trong việc sinh dãy nhị phân, yếu tố nào là điều kiện dừng?
Khi không còn bit nào để xét
khi gặp bit bằng 0 thì dừng
khi độ dài dãy đạt n
khi số tổ hợp vượt ngưỡng giới hạn
Điểm khác biệt giữa kỹ thuật nhánh cận và quay lui?
nhánh cận cho lời giải nhanh hơn trong mọi trường hợp
Nhánh cận sử dụng hàm cận để loại bỏ nhánh không cần thiết
Quay lui luôn sinh toàn bộ không gian nghiệm
quay lui không áp dụng được cho bài toán tối ưu
Để liệt kê dãy nhị phân độ dài n bằng quay lui, ta cần:
Áp dụng cấu trúc cây tìm kiếm tuyến tính
Sử dụng mảng đánh dấu giá trị đã chọn
Duyệt tất cả các tổ hợp dãy nhị phân
Tập đệ cử là (0,1)
Hàm đánh giá g(x) trong nhánh cận có vai trò gì?
Để xác định hàm mục tiêu
Hỗ trợ sắp xếp thứ tự mở rộng nhánh
Không cần liên quan đến hàm mục tiêu
giúp xác định nhánh nào có khả năng chứ lời giải tốt
Trong việc sinh dãy nhị phân, yếu tố nào là điều kiện dừng?
Khi không còn bịt nào để xét
Khi số tổ hợp vượt ngưỡng giới hạn
Khi độ dài dãy đạt n
Khi gặp bịt bằng 0 thì dừng
Tư tưởng và kỹ thuật chủ yếu của phương pháp quy hoạch động dựa vào:
Nguyên lý tối ưu Bellman
Tìm kiếm vét cạn
Lập bảng kết quả các bài toán con
Phân tích truy hồi
Kỹ thuật quy hoạch động hiệu quả hơn chia để trị trong trường hợp nào?
Không cần lưu lời giải bài toán con
Các bài toán con lặp lại nhiều lần
Có công thức truy hồi rõ ràng
Không có sự trùng lặp bài toán con
Đặc điểm chung giữa bài toán tổ hợp và xâu con chung:
Có công thức quy hoạch động rõ ràng
Sử dụng được cây Huffman
cần lưu bảng 2 chiều
tính toán dựa trên đơn giá
Trong bài toán xâu con chung dài nhất (LCS): Chọn đáp án đúng.
Độ phức tạp chỉ O(n)
Có thể có nhiều xâu có cùng độ dài cực đại
Áp dụng quy hoạch động với bảng 2 chiều
Phải vét cạn toàn bộ không gian nghiệm
Về bài toán xâu con chung dài nhất (LCS), phát biểu nào đúng?
Có thể có nhiều xâu có cùng độ dài
Áp dụng quy hoạch động với bảng 2 chiều
Độ phức tạp luôn là O(n)
Cần xét toàn bộ xâu con bằng vét cạn
Điều kiện nào cần có để áp dụng quy hoạch động?
Có sự chống chéo bài toán con
Các bài toán con phải độc lập hoàn toàn
Có công thức truy hồi rõ ràng
Không cần cấu trúc con tối ưu
Khi áp dụng thuật toán tham lam, cần đảm bảo:
Không cần xét toàn bộ không gian lời giải
Có hàm chọn ứng viên tốt nhất
Không tạo chu trình thiếu trong bài toán TSP
Có thể quay lại các lựa chọn trước đó
Kỹ thuật quay lui (Backtracking) dùng để:
Giải các bài toán có không gian trạng thái hữu hạn, có thể vét cạn lời giải
Giải bài toán không gian trạng thái vô hạn
Giải bài toán không có cấu trúc ràng buộc
Giải bài toán tuyến tính
Khi dùng quay lui để tìm nghiệm, nếu phương án hiện tại không thể dẫn tới nghiệm đúng thì:
Tiếp tục đi sâu hơn
Quay lui để thử nhánh khác
Kết thúc thuật toán ngay
Chọn ngẫu nhiên một nhánh khác
So với vét cạn, kỹ thuật quay lui có ưu điểm:
Xét tất cả các khả năng như vét cạn
Loại bỏ được nhiều nhánh vô ích
Đảm bảo nhanh hơn trong mọi trường hợp
Có thể dừng sớm khi tìm thấy nghiệm
Bài toán lập lịch cuộc họp áp dụng kỹ thuật nào sau đây: (Chọn 2 phương án đúng)
Options:
Quy hoạch động (Dynamic Programming)
Quay lui (Backtracking)
Tham lam (Greedy)
Duyệt vét cạn (Brute-force / Exhaustive search)
Đặc điểm nổi bật của kỹ thuật tham lam là gì?
Không cần lưu trữ lời giải các bước trước
Luôn đảm bảo nghiệm tối ưu toàn cục
Duyệt toàn bộ không gian nghiệm
Chọn lựa tối ưu cục bộ tại mỗi bước
Trong bài toán tính số tổ hợp C(n, k), kỹ thuật quy hoạch động sử dụng:
A. Mảng 2 chiều theo cấu trúc tam giác Pascal
B. Mệnh đề lựa chọn tối ưu tại mỗi bước như trong thuật toán tham lam
C. Hàm chọn dựa trên đơn giá từng phần tử
D. Mảng 1 chiều để tối ưu bộ nhớ
Trong bài toán tìm xâu con chung dài nhất (LCS):
Dùng quy hoạch động từ dưới lên để tránh đệ quy
Duyệt hết mọi xâu con để tìm đáp án
Dùng bảng 2 chiều để lưu độ dài L(i,j)
Kết quả cuối cùng là L[m,n]
Trong bài toán TSP (người du lịch), khi dùng thuật toán tham lam.: Sinh viên chọn 2 phương án đúng nhất
Tìm đường đi ngắn nhất tuyệt đối
Có thể không cho lời giải tối ưu
Cần xét tất cả các hoán vị
Độ phức tạp thường là O(n²)
Kết quả cuối cùng của kỹ thuật chia để trị được hình thành từ:
Hợp nhất các kết quả từ các nhánh nhỏ về gốc theo mô hình cây
Chọn ngẫu nhiên nghiệm từ các bài toán con
Tổng hợp kết quả của các bài toán con
Dữ liệu đầu vào
Khi áp dụng kỹ thuật chia để trị trong bài toán nhân hai số nguyên lớn, việc chia nhỏ các số nhằm mục đích gì?
Chia số thành từng chữ số đơn để áp dụng nhân truyền thống dễ hơn
Chia số thành hai phần có số chữ số xấp xỉ nhau để thực hiện nhân các phần nhỏ hơn
Tìm các thừa số nguyên tố của số để giảm độ phức tạp nhân
Áp dụng nhân các phần nhỏ rồi tổng hợp kết quả dựa trên hệ số mũ của cơ số
Đặc điểm đúng của QuickSort:
Luôn chia mảng thành hai phần bằng nhau
Là thuật toán đệ quy tuyến tính
Đạt độ phức tạp O(nlogn) trong trường hợp trung bình
Thuộc loại thuật toán chia để trị
Trong thuật toán Quicksort, phần tử "chốt" được dùng để:
Sử dụng để phân hoạch mảng
So sánh các phần tử với phần tử "chốt" để phân hoạch mảng
Duyệt toàn bộ máng
Lưu trữ tạm thời phần tử nhỏ nhất
Trong kỹ thuật chia để trị, điều nào sau đây là đúng?
Các bước tổng hợp thường cần thiết để hoàn thành bài toán
Các bài toán con thường có cấu trúc khác biệt hoàn toàn
Việc tổng hợp kết quả không cần thiết
Việc chia bài toán con giúp đơn giản hóa bài toán chính
Đặc điểm đúng của kỹ thuật chia để trị:
Không sử dụng được cho các bài toán lớn
Không thể áp dụng song song hoá
Thường sinh ra thuật toán đệ quy
Cần xác định rõ bài toán cơ sở
Đặc điểm đúng của bài toán tìm kiếm nhị phân là:
Mỗi bước chia đôi khoảng tìm kiếm
Phù hợp với mảng chưa sắp
Tìm kiếm trên mảng đã sắp xếp
Có độ phức tạp O(n)
Trong bài toán xếp lịch thi đấu thể thao, kỹ thuật chia để trị giúp:
Lập lịch thi đấu cho mọi số lượng vận động viên
Rút ngắn số ngày thi đấu
Giảm số trận mỗi ngày
Tăng độ khó của bài toán
Kỹ thuật chia để trị được sử dụng để làm gì trong giải bài toán? (Sinh viên chọn 2 phương án đúng nhất)
Giải các bài toán con có cấu trúc giống bài toán ban đầu
Chia bài toán lớn thành các bài toán con nhỏ hơn
Giải bài toán theo phương pháp vét cạn
Bỏ qua các bài toán con nếu không cần thiết
Khi giải bài toán chiếc ba lô bằng nhánh cận:
Không cần xét các tổ hợp đã thử
Phải tính tổng giá trị và tổng trọng lượng tạm thời
Có thể dừng sớm nếu vượt quá dung lượng balô
Cần một hàm cận để đánh giá khả năng tiếp tục
Bài toán lập lịch cuộc họp áp dụng kỹ thuật nào sau đây?
A. Quy hoạch động
B. Tham lam
C. Quay lui
D. Duyệt vét cạn
Kỹ thuật quay lui hoạt động dựa trên:
Loại bỏ các cấu hình không thỏa mãn tính chất T
Duyệt tất cả phương án có thể theo đệ quy
Sinh ra lời giải bằng phương pháp ngẫu nhiên
Ưu tiên các phương án có giá trị mục tiêu cao
Trong kỹ thuật nhánh cận, khi nào có thể loại bỏ một nhánh?
Khi cận dưới bằng 0
Khi không còn giá trị để cử
Khi phương án không có lời giải
Khi cận dưới của phương án lớn hơn giá trị tối ưu hiện tại
Trong kỹ thuật quy hoạch động, hai đặc điểm quan trọng của bài toán cần có là
A. Bài toán có thể giải được bằng vét cạn
B. Có bài toán con gối nhau
C. Có thể biểu diễn bằng cây nhị phân
D. Có cấu trúc con tối ưu
Thuật toán tham lam có điểm nào nổi bật?
A. Lựa chọn tại mỗi bước là quyết định cuối cùng
B. Luôn chính xác với mọi bài toán tối ưu
C. Phải lưu lại toàn bộ trạng thái trước đó
D. Không cần xét lại các lựa chọn trước đó
Trong bài toán tối ưu tuyến tính theo kỹ thuật tham lam, phương án nào sau đây là đúng? (Chọn 2 phương án)
Luôn tìm được nghiệm tối ưu
Có thể không đổi được nếu mệnh giá không phù hợp
Chọn tiền mệnh giá nhỏ trước
Chọn tiền mệnh giá lớn trước
Với bài toán ba lô giá trị nguyên, thuật toán tham lam sẽ hiệu quả khi:
A. Tỷ lệ giá trị/trọng lượng là tiêu chí chọn
B. Giá trị mỗi vật là như nhau
C. Không giới hạn số lượng mỗi loại vật
D. Trọng lượng ba lô thay đổi liên tục
Trong giải thuật Mergesort, các bước chính là: (Chọn 2 phương án)
A. Chia mảng thành hai nửa
B. Gọi đệ quy sắp xếp từng nửa
C. Duyệt tuần tự và chèn từng phần tử
D. Sắp xếp bằng cách chọn phần tử nhỏ nhất
Trong kỹ thuật quay lui, điều kiện nào là bắt buộc?
Không trùng lặp cấu hình
Không có điều kiện chấp nhận
Không sử dụng đệ quy
Không bỏ sót cấu hình
