Nguyên tắc cơ bản về lý thuyết độ phức hợp tính toán EITC/IS/CCTF là chương trình Chứng nhận CNTT của Châu Âu về các khía cạnh lý thuyết của nền tảng khoa học máy tính cũng là cơ sở của mật mã khóa công khai bất đối xứng cổ điển được sử dụng rộng rãi trên Internet.
Chương trình học của Nguyên tắc cơ bản về lý thuyết độ phức tạp tính toán EITC/IS/CCTF bao gồm kiến thức lý thuyết về nền tảng của khoa học máy tính và mô hình tính toán dựa trên các khái niệm cơ bản như máy trạng thái hữu hạn xác định và không xác định, ngôn ngữ thông thường, lý thuyết máy tính và ngôn ngữ không có ngữ cảnh, lý thuyết tự động hóa, Turing Máy móc, khả năng giải mã của các vấn đề, đệ quy, logic và độ phức tạp của thuật toán cho các ứng dụng bảo mật cơ bản trong cấu trúc sau, bao gồm nội dung bài giảng video toàn diện làm tài liệu tham khảo cho Chứng nhận EITC này.
Độ phức tạp tính toán của một thuật toán là lượng tài nguyên cần thiết để vận hành nó. Tài nguyên thời gian và bộ nhớ được quan tâm đặc biệt. Độ phức tạp của một vấn đề được định nghĩa là độ phức tạp của các thuật toán tốt nhất để giải nó. Phân tích thuật toán là nghiên cứu về độ phức tạp của các thuật toán đã cho rõ ràng, trong khi lý thuyết độ phức tạp tính toán là nghiên cứu về độ phức tạp của các giải pháp vấn đề với các thuật toán đã biết tốt nhất. Cả hai miền đan xen vào nhau bởi vì độ phức tạp của thuật toán luôn là giới hạn trên đối với độ phức tạp của vấn đề mà nó giải quyết. Hơn nữa, thường xuyên phải so sánh độ phức tạp của một thuật toán nhất định với độ phức tạp của vấn đề cần giải quyết trong khi xây dựng các thuật toán hiệu quả. Trong hầu hết các trường hợp, thông tin duy nhất có sẵn về độ khó của một vấn đề là nó ít hơn mức độ phức tạp của các kỹ thuật hiệu quả nhất đã biết. Kết quả là, có rất nhiều sự chồng chéo giữa phân tích thuật toán và lý thuyết độ phức tạp.
Lý thuyết độ phức tạp đóng một vai trò quan trọng không chỉ trong nền tảng của các mô hình tính toán làm cơ sở cho khoa học máy tính mà còn trong nền tảng của mật mã bất đối xứng cổ điển (được gọi là mật mã khóa công khai) được phổ biến rộng rãi trong các mạng hiện đại, đặc biệt là trên Internet. Mã hóa khóa công khai dựa trên độ khó tính toán của một số vấn đề toán học bất đối xứng, chẳng hạn như phân tích nhân tử của các số lớn thành các thừa số nguyên tố của nó (phép toán này là một vấn đề khó trong phân loại lý thuyết độ phức tạp, vì không có thuật toán cổ điển hiệu quả nào được biết để giải nó với tài nguyên nhân rộng theo đa thức thay vì theo cấp số nhân với sự gia tăng kích thước đầu vào của bài toán, điều này trái ngược với một phép toán ngược rất đơn giản là nhân với các thừa số nguyên tố đã biết để cho số lớn ban đầu). Sử dụng tính bất đối xứng này trong kiến trúc của mật mã khóa công khai (bằng cách xác định mối quan hệ bất đối xứng về mặt tính toán giữa khóa công khai, có thể dễ dàng tính toán từ khóa riêng tư, trong khi khóa riêng không thể dễ dàng máy tính từ khóa công khai, người ta có thể công khai công bố khóa công khai và cho phép các bên giao tiếp khác sử dụng nó để mã hóa không đối xứng dữ liệu, sau đó chỉ có thể được giải mã bằng khóa cá nhân kết hợp, không có sẵn về mặt tính toán cho các bên thứ ba, do đó làm cho giao tiếp an toàn).
Lý thuyết độ phức tạp tính toán được phát triển chủ yếu dựa trên thành tựu của những người tiên phong về khoa học máy tính và thuật toán, chẳng hạn như Alan Turing, người có công trình quan trọng trong việc phá vỡ mật mã Enigma của Đức Quốc xã, đóng vai trò sâu sắc trong việc quân đồng minh giành chiến thắng trong Chiến tranh thế giới thứ hai. Phân tích mật mã nhằm mục đích thiết lập và tự động hóa các quy trình tính toán phân tích dữ liệu (chủ yếu là giao tiếp được mã hóa) để phát hiện ra thông tin ẩn được sử dụng để vi phạm hệ thống mật mã và giành quyền truy cập vào nội dung của thông tin liên lạc được mã hóa, thường có tầm quan trọng chiến lược về quân sự. Nó cũng là phân tích mật mã đã xúc tác cho sự phát triển của các máy tính hiện đại đầu tiên (ban đầu được áp dụng cho mục tiêu chiến lược là phá mã). Colossus của Anh (được coi là máy tính điện tử và chương trình hiện đại đầu tiên) có tiền thân là “quả bom” Ba Lan, một thiết bị tính toán điện tử do Marian Rejewski thiết kế để hỗ trợ phá mật mã Enigma, và được tình báo Ba Lan bàn giao cho Vương quốc Anh cùng với máy mã hóa Enigma của Đức bị bắt, sau khi Ba Lan bị Đức xâm lược vào năm 1939. Trên cơ sở của thiết bị này, Alan Turing đã phát triển bản sao tiên tiến hơn của mình để phá vỡ thành công thông tin liên lạc được mã hóa của Đức, sau này được phát triển thành máy tính hiện đại.
Vì lượng tài nguyên cần thiết để chạy một thuật toán thay đổi theo kích thước của đầu vào, độ phức tạp thường được biểu thị dưới dạng hàm f (n), trong đó n là kích thước đầu vào và f (n) là độ phức tạp trong trường hợp xấu nhất ( số lượng tài nguyên tối đa được yêu cầu trên tất cả các đầu vào có kích thước n) hoặc độ phức tạp trong trường hợp trung bình (giá trị trung bình của lượng tài nguyên trên tất cả các đầu vào có kích thước n). Số lượng các phép toán cơ bản được yêu cầu trên đầu vào có kích thước n thường được nêu dưới dạng độ phức tạp về thời gian, trong đó các phép toán cơ bản được cho là mất một lượng thời gian không đổi trên một máy tính cụ thể và chỉ thay đổi bởi một hệ số không đổi khi chạy trên một máy khác. Lượng bộ nhớ mà một thuật toán yêu cầu trên đầu vào có kích thước n được gọi là độ phức tạp của không gian.
Thời gian là tài nguyên thường được coi là tài nguyên nhất. Khi thuật ngữ “độ phức tạp” được sử dụng mà không có định nghĩa, nó thường đề cập đến độ phức tạp của thời gian.
Các đơn vị thời gian truyền thống (giây, phút, v.v.) không được sử dụng trong lý thuyết độ phức tạp vì chúng quá phụ thuộc vào máy tính được chọn và sự tiến bộ của công nghệ. Ví dụ, một máy tính ngày nay có thể thực thi một thuật toán nhanh hơn đáng kể so với một máy tính từ những năm 1960, tuy nhiên, điều này là do những đột phá về công nghệ trong phần cứng máy tính chứ không phải do chất lượng vốn có của thuật toán. Mục tiêu của lý thuyết độ phức tạp là để định lượng nhu cầu thời gian vốn có của các thuật toán, hoặc các giới hạn thời gian cơ bản mà một thuật toán sẽ áp đặt cho bất kỳ máy tính nào. Điều này được thực hiện bằng cách đếm có bao nhiêu hoạt động cơ bản được thực hiện trong quá trình tính toán. Các quy trình này thường được gọi là các bước vì chúng được coi là mất thời gian liên tục trên một máy cụ thể (tức là chúng không bị ảnh hưởng bởi số lượng đầu vào).
Một tài nguyên quan trọng khác là dung lượng bộ nhớ máy tính cần thiết để thực hiện các thuật toán.
Một tài nguyên khác thường được sử dụng là số lượng các phép toán số học. Trong trường hợp này, thuật ngữ "độ phức tạp số học" được sử dụng. Độ phức tạp thời gian nói chung là sản phẩm của độ phức tạp số học với một hệ số không đổi nếu giới hạn trên về kích thước của biểu diễn nhị phân của các số xảy ra trong quá trình tính toán được biết đến.
Kích thước của các số nguyên được sử dụng trong quá trình tính toán không bị ràng buộc đối với nhiều phương pháp và sẽ không thực tế nếu cho rằng các phép toán số học yêu cầu một khoảng thời gian cố định. Do đó, độ phức tạp thời gian, còn được gọi là độ phức tạp bit, có thể cao hơn đáng kể so với độ phức tạp số học. Ví dụ, khó khăn về số học khi tính toán định thức của một ma trận nn số nguyên là O (n ^ 3) đối với các kỹ thuật tiêu chuẩn (loại bỏ Gaussian). Bởi vì kích thước của các hệ số có thể mở rộng theo cấp số nhân trong quá trình tính toán, độ phức tạp bit của các phương pháp tương tự là cấp số nhân theo n. Nếu các kỹ thuật này được sử dụng kết hợp với số học đa mô-đun, độ phức tạp của bit có thể giảm xuống còn O (n ^ 4).
Độ phức tạp bit, theo thuật ngữ chính thức, đề cập đến số lượng hoạt động trên các bit cần thiết để chạy một thuật toán. Nó tương đương với độ phức tạp theo thời gian lên đến một yếu tố không đổi trong hầu hết các mô hình tính toán. Số lượng các thao tác trên các từ máy mà máy tính yêu cầu tỷ lệ với độ phức tạp của bit. Đối với các mô hình tính toán thực tế, độ phức tạp về thời gian và độ phức tạp của bit là như nhau.
Tài nguyên thường được xem xét trong việc sắp xếp và tìm kiếm là số lượng các mục so sánh. Nếu dữ liệu được sắp xếp tốt, đây là một chỉ báo tốt về độ phức tạp của thời gian.
Trên tất cả các đầu vào tiềm năng, việc đếm số bước trong một thuật toán là không thể. Bởi vì độ phức tạp của đầu vào tăng lên theo kích thước của nó, nó thường được biểu diễn dưới dạng một hàm của kích thước đầu vào là n (tính bằng bit), và do đó độ phức tạp là một hàm của n. Tuy nhiên, đối với các đầu vào có cùng kích thước, độ phức tạp của thuật toán có thể thay đổi đáng kể. Kết quả là, một loạt các chức năng phức tạp được sử dụng thường xuyên.
Độ phức tạp trong trường hợp xấu nhất là tổng của tất cả độ phức tạp cho tất cả đầu vào cỡ n, trong khi độ phức tạp trong trường hợp trung bình là tổng của tất cả độ phức tạp cho tất cả đầu vào cỡ n (điều này có ý nghĩa, vì số lượng đầu vào có thể có của một kích thước nhất định là có hạn). Khi thuật ngữ “độ phức tạp” được sử dụng mà không được định nghĩa thêm, thì độ phức tạp về thời gian trong trường hợp xấu nhất sẽ được tính đến.
Độ phức tạp trong trường hợp xấu nhất và trường hợp trung bình nổi tiếng là khó tính toán chính xác. Hơn nữa, các giá trị chính xác này có ít ứng dụng thực tế vì bất kỳ thay đổi nào trong máy hoặc mô hình tính toán sẽ làm thay đổi độ phức tạp một chút. Hơn nữa, việc sử dụng tài nguyên không quan trọng đối với các giá trị nhỏ của n, do đó, tính dễ thực hiện thường hấp dẫn hơn độ phức tạp thấp đối với n nhỏ.
Vì những lý do này, hầu hết sự chú ý được chú ý đến hành vi của độ phức tạp đối với n cao, tức là hành vi tiệm cận của nó khi n tiến đến vô cùng. Do đó, ký hiệu O lớn thường được sử dụng để chỉ độ phức tạp.
Mô hình tính toán
Việc lựa chọn một mô hình tính toán, bao gồm việc xác định các hoạt động thiết yếu được thực hiện trong một đơn vị thời gian, là yếu tố quan trọng trong việc xác định độ phức tạp. Điều này đôi khi được gọi là máy Turing đa loại khi mô hình tính toán không được mô tả cụ thể.
Mô hình tính toán xác định là mô hình trong đó các trạng thái tiếp theo của máy và các hoạt động sẽ được thực hiện hoàn toàn được xác định bởi trạng thái trước đó. Các hàm đệ quy, phép tính lambda và máy Turing là những mô hình xác định đầu tiên. Máy truy cập ngẫu nhiên (còn được gọi là máy RAM) là một mô hình phổ biến để mô phỏng máy tính trong thế giới thực.
Khi mô hình tính toán không được xác định, máy Turing đa loại thường được giả định. Trên máy Turing multitape, độ phức tạp về thời gian giống như trên máy RAM đối với hầu hết các thuật toán, mặc dù cần chú ý đáng kể đến cách dữ liệu được lưu trữ trong bộ nhớ để đạt được sự tương đương này.
Các lựa chọn khác nhau có thể được thực hiện ở một số bước tính toán trong mô hình tính toán không xác định, chẳng hạn như máy Turing không xác định. Trong lý thuyết độ phức tạp, tất cả các phương án khả thi đều được xem xét cùng một lúc và độ phức tạp về thời gian không xác định là lượng thời gian cần thiết khi các lựa chọn tốt nhất luôn được thực hiện. Nói một cách khác, việc tính toán được thực hiện đồng thời trên nhiều bộ xử lý (giống hệt nhau) theo yêu cầu và thời gian tính toán không xác định là thời gian mà bộ xử lý đầu tiên thực hiện để hoàn thành tính toán. Tính song song này có thể được sử dụng trong tính toán lượng tử bằng cách sử dụng các trạng thái vướng víu chồng chất khi chạy các thuật toán lượng tử chuyên biệt, chẳng hạn như tính toán thừa số của Shor đối với các số nguyên nhỏ.
Ngay cả khi mô hình tính toán như vậy hiện không thể thực hiện được, nó vẫn có ý nghĩa lý thuyết, đặc biệt là liên quan đến bài toán P = NP, bài toán này hỏi liệu các lớp phức tạp được tạo ra bằng cách sử dụng "thời gian đa thức" và "thời gian đa thức không xác định" là ít nhất giới hạn là như nhau. Trên máy tính xác định, việc mô phỏng thuật toán NP yêu cầu “thời gian theo cấp số nhân”. Nếu một nhiệm vụ có thể được giải quyết trong thời gian đa thức trên một hệ thống không xác định, nó thuộc loại khó NP. Nếu một vấn đề nằm trong NP và không dễ hơn bất kỳ vấn đề NP nào khác, nó được coi là NP-hoàn chỉnh. Bài toán Knapsack, bài toán nhân viên bán hàng lưu động và bài toán thỏa mãn Boolean đều là các bài toán tổ hợp hoàn chỉnh NP. Thuật toán nổi tiếng nhất có độ phức tạp theo cấp số nhân cho tất cả các vấn đề này. Nếu bất kỳ vấn đề nào trong số này có thể được giải quyết trong thời gian đa thức trên một máy xác định, thì tất cả các bài toán NP cũng có thể được giải quyết trong thời gian đa thức và P = NP sẽ được thiết lập. Vào năm 2017, nhiều người cho rằng P NP, ngụ ý rằng các tình huống xấu nhất của các vấn đề NP về cơ bản là khó giải quyết, tức là mất nhiều thời gian hơn bất kỳ khoảng thời gian khả thi nào (hàng thập kỷ) với độ dài đầu vào thú vị.
Tính toán song song và phân tán
Tính toán song song và phân tán liên quan đến việc phân chia xử lý trên nhiều bộ xử lý hoạt động cùng một lúc. Sự khác biệt cơ bản giữa các mô hình khác nhau là phương pháp gửi dữ liệu giữa các bộ xử lý. Việc truyền dữ liệu giữa các bộ xử lý thường rất nhanh trong tính toán song song, trong khi truyền dữ liệu giữa các bộ xử lý trong tính toán phân tán được thực hiện trên mạng và do đó chậm hơn đáng kể.
Một phép tính trên N bộ xử lý mất ít nhất thương số bằng N của thời gian nó thực hiện trên một bộ xử lý. Trong thực tế, vì một số nhiệm vụ con không thể được thực hiện song song và một số bộ xử lý có thể cần đợi kết quả từ một bộ xử lý khác, giới hạn lý tưởng về mặt lý thuyết này sẽ không bao giờ đạt được.
Do đó, vấn đề phức tạp quan trọng là phát triển các thuật toán sao cho tích số thời gian tính toán của số bộ xử lý càng gần càng tốt với thời gian cần thiết để thực hiện cùng một phép tính trên một bộ xử lý.
Tính toán lượng tử
Máy tính lượng tử là một máy tính có mô hình tính toán dựa trên cơ học lượng tử. Luận điểm của Church – Turing đúng với máy tính lượng tử, ngụ ý rằng bất kỳ vấn đề nào mà máy tính lượng tử có thể giải quyết cũng có thể được giải quyết bằng máy Turing. Tuy nhiên, về mặt lý thuyết, một số nhiệm vụ có thể được giải quyết bằng máy tính lượng tử chứ không phải máy tính cổ điển với độ phức tạp theo thời gian thấp hơn đáng kể. Hiện tại, điều này hoàn toàn là lý thuyết, vì không ai biết cách phát triển một máy tính lượng tử thực tế.
Lý thuyết độ phức tạp lượng tử được tạo ra để điều tra các loại vấn đề khác nhau có thể được giải quyết bởi máy tính lượng tử. Nó được sử dụng trong mật mã hậu lượng tử, là quá trình tạo ra các giao thức mật mã có khả năng chống lại các cuộc tấn công của máy tính lượng tử.
Mức độ phức tạp của vấn đề (giới hạn thấp hơn)
Sự phức tạp của các thuật toán có thể giải quyết vấn đề, bao gồm cả các kỹ thuật chưa được khám phá, là mức độ phức tạp của vấn đề. Kết quả là, độ phức tạp của một vấn đề bằng với độ phức tạp của bất kỳ thuật toán nào giải được nó.
Kết quả là, bất kỳ độ phức tạp nào được đưa ra trong ký hiệu O lớn đều thể hiện độ phức tạp của cả thuật toán và bài toán kèm theo.
Mặt khác, việc đạt được giới hạn thấp hơn đáng kể về độ phức tạp của vấn đề thường rất khó và có rất ít chiến lược để làm như vậy.
Để giải quyết hầu hết các vấn đề, tất cả dữ liệu đầu vào phải được đọc, điều này cần thời gian tương ứng với độ lớn của dữ liệu. Kết quả là, các bài toán như vậy ít nhất có độ phức tạp tuyến tính, hoặc, trong ký hiệu omega lớn, độ phức tạp là Ω (n).
Một số bài toán, chẳng hạn như trong đại số máy tính và hình học đại số tính toán, có các giải pháp rất lớn. Vì đầu ra phải được viết nên độ phức tạp bị hạn chế bởi kích thước tối đa của đầu ra.
Số lượng phép so sánh cần thiết cho một thuật toán sắp xếp có giới hạn dưới phi tuyến là Ω (nlogn). Kết quả là, các thuật toán sắp xếp tốt nhất là hiệu quả nhất vì độ phức tạp của chúng là O (nlogn). Thực tế là có n! cách sắp xếp thứ n dẫn đến giới hạn dưới này. Bởi vì mỗi so sánh chia tập hợp này của n! đơn đặt hàng thành hai phần, số lượng so sánh N cần thiết để phân biệt tất cả các đơn hàng phải là 2N> n !, ngụ ý O (nlogn) theo công thức của Stirling.
Giảm một vấn đề thành một vấn đề khác là một chiến lược phổ biến để giảm bớt các ràng buộc phức tạp.
Phát triển thuật toán
Đánh giá độ phức tạp của thuật toán là một yếu tố quan trọng của quá trình thiết kế vì nó cung cấp thông tin hữu ích về hiệu suất có thể được mong đợi.
Một sự hiểu lầm thường xuyên xảy ra rằng, do kết quả của định luật Moore, dự đoán sự phát triển theo cấp số nhân của sức mạnh máy tính hiện đại, việc đánh giá độ phức tạp của các thuật toán sẽ trở nên ít phù hợp hơn. Điều này không chính xác vì công suất tăng lên cho phép xử lý một lượng lớn dữ liệu (dữ liệu lớn). Ví dụ: bất kỳ thuật toán nào sẽ hoạt động tốt trong vòng chưa đầy một giây khi sắp xếp theo thứ tự bảng chữ cái danh sách vài trăm mục nhập, chẳng hạn như thư mục của một cuốn sách. Mặt khác, đối với một triệu mục nhập (ví dụ: số điện thoại của một thành phố lớn), các thuật toán cơ bản yêu cầu so sánh O (n2) sẽ phải thực hiện một nghìn tỷ phép so sánh, sẽ mất ba giờ với tốc độ 10 triệu phép so sánh mỗi giây. Mặt khác, sắp xếp nhanh và sắp xếp hợp nhất chỉ yêu cầu so sánh nlogn (độ phức tạp trong trường hợp trung bình đối với trường hợp trước, là độ phức tạp trong trường hợp xấu nhất đối với trường hợp sau). Điều này tạo ra khoảng 30,000,000 so sánh cho n = 1,000,000, chỉ mất 3 giây với 10 triệu so sánh mỗi giây.
Do đó, việc đánh giá độ phức tạp có thể cho phép loại bỏ nhiều thuật toán không hiệu quả trước khi triển khai. Điều này cũng có thể được sử dụng để tinh chỉnh các thuật toán phức tạp mà không cần phải kiểm tra tất cả các biến thể có thể có. Nghiên cứu về độ phức tạp cho phép tập trung nỗ lực để tăng hiệu quả của việc triển khai bằng cách xác định các bước tốn kém nhất của một thuật toán phức tạp.
Để tìm hiểu chi tiết về chương trình giảng dạy chứng nhận, bạn có thể mở rộng và phân tích bảng bên dưới.
Chương trình Chứng nhận Lý thuyết Độ phức tạp Tính toán Cơ bản của EITC/IS/CCTF tham khảo các tài liệu giáo khoa truy cập mở dưới dạng video. Quá trình học tập được chia thành cấu trúc từng bước (chương trình -> bài học -> chủ đề) bao gồm các phần chương trình học có liên quan. Tư vấn không giới hạn với các chuyên gia tên miền cũng được cung cấp.
Để biết chi tiết về kiểm tra thủ tục Chứng nhận Làm thế nào nó hoạt động.
Tài liệu đọc chương trình hỗ trợ tiểu học
S. Arora, B. Barak, Tính phức tạp: Phương pháp tiếp cận hiện đại
https://theory.cs.princeton.edu/complexity/book.pdf
Tài liệu đọc chương trình hỗ trợ trung học
O. Goldreich, Giới thiệu về Lý thuyết Độ phức tạp:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Giáo trình hỗ trợ đọc tài liệu về toán học rời rạc
J. Aspnes, Ghi chú về Toán học rời rạc:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
Giáo trình hỗ trợ đọc tài liệu về lý thuyết đồ thị
R. Diestel, Lý thuyết đồ thị:
https://diestel-graph-theory.com/
Tải xuống tài liệu chuẩn bị tự học ngoại tuyến hoàn chỉnh cho chương trình Nguyên tắc cơ bản về lý thuyết độ phức tạp tính toán EITC/IS/CCTF dưới dạng tệp PDF
Tài liệu chuẩn bị EITC/IS/CCTF – phiên bản tiêu chuẩn
Tài liệu chuẩn bị EITC/IS/CCTF – phiên bản mở rộng với các câu hỏi ôn tập