Lý thuyết độ phức tạp chuyên ngành tin học

#1

có anh chị, bạn bè nào đã hoặc đang học môn lý thuyết độ phức tạp không ạ? em rất cần người chỉ giáo một số vấn đề của môn này ạ

#2

Bạn đang mắc ở chỗ nào thì nêu lên cụ thể nhé.

#3

dạ tại sao thời gian tính toán phải là hàm số với biến là độ dài của input ạ?

#4

Rõ ràng quá rồi còn gì. Input đâu có giống nhau trong tất cả mọi trường hợp đâu.
Ví dụ như:

input n
for i = 1 -> n
    for j = 1 -> n
        output (i * j)

Thời gian chạy khi n = 10 và n = 10000 khác nhau. Còn độ phức tạp trong ví dụ này luôn là O(n^2). Thời gian phụ thuộc vào độ phức tạp và giá trị của input.

#5

à em hiểu rồi ạ, ^^ cảm ơn a đã chỉ giáo, em học môn này mà cứ thấy NP, NPC nhưng không hiểu bản chất các thứ, nên rất mông lung.đang phải tìm hiểu lại từ đâu, hihi

#6

Thời gian tính toán phụ thuộc nhiều biến, độ dài của input chỉ là 1 trong số đó, ngoài ra còn có tốc độ IO, số CPU core, memory space, tính chất input (sort, partial sort,…), vân vân.

Biến độ dài input được dùng nhiều nhất trong tính toán độ phức tạp nên khi nghĩ độ phức tạp thì hay dùng biến n - độ dài input.

Thêm nữa là máy tính trong ví dụ giải thuật thường giới hạn 1 CPU, 1 thời điểm thực hiện 1 lệnh, không có asynchronous. Bạn mở rộng các yếu tố trên cho máy tính thì tính toán độ giải thuật phức tạp hơn chút. :grinning:

3 Likes
#7

Complexity class thì đã đào sâu vào KHMT rồi, người ta sẽ bắt đầu với các hàm cơ bản trước (log, lũy thừa, mũ, giai thừa) rồi đi tới big-O, theta, small-o.

2 Likes
#8

với yêu cầu ‘Xây dựng máy Turing tất định xóa các từ’ thì e xây dựng như thế nào cho hợp lý ạ? có quy tắc nào để xây dựng các máy turing không ạ?

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?