I. МАТЕМАТИЧНІ ОСНОВИ АНАЛІЗУ АЛГОРИТМІВ

ВСТУП

Теорія алгоритмів – це наука, що вивчає загальні властивості та закономірності алгоритмів, різноманітні формальні моделі їх подання. На основі формалізації поняття алгоритму можливе порівняння алгоритмів за їх ефективністю, перевіркою їх еквівалентності, визначення областей застосовності.

Даний курс служить формуванню знань і умінь, які утворюють теоретичний фундамент, необхідний для постановки і вирішення завдань в галузі інформатики, для коректного розуміння обмежень, що виникають при створенні обчислювальних структур, алгоритмів і програм обробки інформації.

Як відомо, після закінчення кожного десятиріччя елементна база комп'ютерів, операційні системи, засоби доступу та самі програми змінюються корінним чином. Однак структури і алгоритми, що лежать в їх основі, залишаються незмінними протягом набагато більшого часу. Ці основи стали закладатися тисячоліття тому, коли розроблена формальна логіка і розроблені перші алгоритми.

Зараз, коли можливості обчислювальної техніки багаторазово зросли, а самих персональних комп'ютерів значно більше, ніж людей, які вміють їх ефективно використовувати, розуміння того, що можна і що не можна зробити за допомогою сучасної обчислювальної техніки набуває виняткового значення.

Саме загальна теорія алгоритмів показала, що є завдання, які нерозв'язні ні при якому збільшенні потужності обчислювальних засобів. Теорія складності обчислень поступово призводить до розуміння того, що бувають завдання розв'язні, але об'єктивно-складні, причому складність їх може виявитися в деякому сенсі абсолютної, тобто практично недоступною для сучасних ЕОМ.

В даному курсі ставилися наступні завдання:

1. Викласти питання, що рекомендовані навчальною програмою на основі галузевого стандарту вищої освіт України з напряму підготовки 6.050101 «Комп’ютерні науки», які потрібно для фахівця вищої кваліфікації.

2. Сформувати методичний матеріал до вивчення курсу «Теорія алгоритмів».

3. Підвищити рівень знань студентів в області математичного аналізу алгоритмів, теорії обчислювальності, алгоритмічних стратегія та в аналізі класів складності алгоритмів.

У результаті освоєння даного курсу студент на основі чіткого розуміння відповідних теоретичних розділів повинен вміти:

- Реалізовувати найпростіший вид логічного перетворення інформації в довільному базисі логічних функцій;

- Виділяти в доказових міркуваннях природної мови логічну структуру, будувати схеми формальних доказів і перевіряти їх правильність.

- Проектувати та формалізовувати системи рішень різноманітних задач.