Автор: Гуц А.К.
Издательство: О.: Наследие
Год издания: 2003
Страницы: 108
ISBN 5-8239-0126-7
Читать:
Скачать: matematicheskayalogika2003.djvu

ОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ КОМПЬЮТЕРНЫХ НАУК КАФЕДРА
КИБЕРНЕТИКИ
А.К. Гуц
Математическая логика и теория алгоритмов
Омск 2003
ВВК 60 УДК 53:630.11
Гуц А.К. Математическая логика и теория алгоритмов: Учебное пособие. -
Омск: Издательство Наследие. Диалог-Сибирь, 2003. - 108 с.
ISBN 5 - 8239 - 0126 - 7
Учебное пособие посвящено изложению основ математической логики и теории
алгоритмов. Основу пособия составляют конспекты лекций, которые читались
студентам второго курса отделения компьютерных наук Омского
государственного университета в 2002 году.
Для студентов, обучающихся по специальности 075200 - "Компьютерная
безопасность" и по специальности 220100 - "Вычислительные машины,
комплексы, системы и сети".
ISBN 5 - 8239 - 0126 - 7
(c) Омский госуниверситет, 2003
Оглавление
I Логика 7
1 Классическая логика 8
1.1. Логика высказываний............................... 8
1.1.1. Высказывания.............................. 8
1.1.2. Основные законы логики.................... 9
1.1.3. Логический парадокс Рассела............... 10
1.1.4. Алгебра (логика) высказываний............. 11
1.1.5. Релейно-контактные схемы.................. 12
1.1.6. Равносильные формулы...................... 14
1.1.7. Алгебра Буля.............................. 15
1.1.8. Истинные и общезначимые формулы........... 15
1.1.9. Проблема разрешимости..................... 15
1.1.10. Логическое следствие...................... 16
1.1.11. Силлогизмы................................ 17
1.2. Логика предикатов................................. 17
1.2.1. Предикаты и формулы....................... 18
1.2.2. Интерпретации............................. 19
1.2.3. Истинность и выполнимость формул. Модели,
общезначимость, логическое следствие........ 20
1.2.4. Готлоб Фреге.............................. 21
1.2.5. Сколемовские функции
и сколемизация формул....................... 22
1.3. Метод резолюций................................... 25
1.3.1. Метод резолюций в логике
высказываний................................ 25
1.3.2. Метод резолюций в логике
предикатов.................................. 29
3
4
Оглавление
2 Формальные теории (исчисления) 31
2.1. Определение формальной теории, или исчисления. . 32
2.1.1. Доказательство. Непротиворечивость теории.
Полнота теории............................... 32
2.2. Исчисление высказываний............................ 33
2.2.1. Язык и правила вывода исчисления высказываний
............................................. 33
2.2.2. Пример доказательства теоремы............... 35
2.2.3. Полнота и непротиворечивость
исчисления высказываний...................... 36
2.3. Исчисление предикатов.............................. 37
2.3.1. Язык и правила вывода исчисления предикатов 37
2.3.2. Полнота и непротиворечивость
исчисления предикатов........................ 39
2.4. Формальная арифметика.............................. 39
2.4.1. Эгалитарные теории......................... 39
2.4.2. Язык и правила вывода формальной арифметики
.............................................. 39
2.4.3. Непротиворечивость формальной
арифметики. Теорема Генцена.................. 40
2.4.4. Теорема Гёделя о неполноте.................. 41
2.4.5. Курт Гёдель................................. 42
2.5. Автоматический вывод теорем....................... 43
2.5.1. С.Ю. Маслов................................. 43
2.6. Логическое программирование....................... 45
2.6.1. Логическая программа........................ 46
2.6.2. Языки логического программирования.... 49
3 Неклассические логики 50
3.1. Интуиционистская логика............................ 50
3.2. Нечеткая логика.................................... 51
3.2.1. Нечеткие подмножества....................... 51
3.2.2. Операции над нечеткими
подмножествами............................... 52
3.2.3. Свойства множества нечетких
подмножеств.................................. 53
3.2.4. Нечеткая логика высказываний................ 54
3.2.5. Нечеткие релейно-контактные схемы........... 56
3.3. Модальные логики.................................. 56
3.3.1. Типы модальности............................ 57
Оглавление
5
3.3.2. Исчисления 1 и Т (Фейса-фон Вригта)........ 57
3.3.3. Исчисления S4, S5
и исчисление Брауэра........................ 58
3.3.4. Означивание формул......................... 59
3.3.5. Семантика Крипке........................... 60
3.3.6. Другие интерпретации модальных
знаков...................................... 62
3.4. Георг фон Вригт................................... 62
3.5. Временные логики.................................. 62
3.5.1. Временная логика Прайора................... 63
3.5.2. Временная логика Леммона................... 64
3.5.3. Временная логика фон Вригта............... 64
3.5.4. Приложение временных логик
к программированию......................... 65
3.5.5. Временная логика Пнуели.................... 67
3.6. Алгоритмические логики............................ 70
3.6.1. Принципы построения
1 >

Федеральное агентство по образованию

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Кафедра автоматизации обработки информации

Утверждаю:

Зав. каф. АОИ

профессор

Ю.П. Ехлаков

«__» _____________2007 г.

Методические указания

к выполнению практических работ по дисциплине

«Математическая логика и теория алгоритмов»

для студентов специальности 230102 –

«Автоматизированные системы обработки информации и управления»

Разработчики:

ст. преподаватель каф. АОИ

Т.О. Перемитина

Томск – 2007

Практическое занятие № 1 «Формулы алгебры высказываний» 3

Практическое занятие № 2 «Равносильные преобразования формул алгебры высказываний» 10

Практическое занятие № 3 «Нормальные формы формул» 12

Практическое занятие № 4 «Логические рассуждения» 14

Практическое занятие № 5 «Формулы логики предикатов» 18

Практическое занятие № 6 «Булевы функции» 23

Практическое занятие № 7 «Частично рекурсивные функции» 28

Практическое занятие № 8 «Машины Тьюринга» 34

Практическое занятие № 1 «Формулы алгебры высказываний»

Учение о высказываниях – алгебра высказываний, или алгебра логики, – является простейшей логической теорией. Атомарным понятием алгебры высказываний является высказывание – повествовательное предложение, в отношении которого имеет смысл утверждение об его истинности или ложности.

Пример истинного высказывания: "Земля вращается вокруг Солнца". Пример ложного высказывания: "3 > 5". Не всякое предложение является высказыванием, к высказываниям не относятся вопросительные и восклицательные предложения. Не является высказыванием предложение: «Каша – вкусное блюдо», так как не может быть единого мнения о том, истинно оно или ложно. Предложение «Есть жизнь на Марсе» следует считать высказыванием, так как объективно оно либо истинно, либо ложно, хотя никто пока не знает, какое именно.

Поскольку предметом изучения логики являются только значения истинности высказываний, для них вводят буквенные обозначения A, B, … или X,Y...

Считается, что каждое высказывание либо истинно, либо ложно. Для краткости, будем вместо значения истинно писать 1, а вместо значения ложно – 0. Например, X= "Земля вращается вокруг Солнца" иY= "3 > 5", причемX=1 иY= 0. Высказывание не может быть одновременно истинным и ложным.

Высказывания могут быть простыми и составными. Высказывания "Земля вращается вокруг Солнца" и "3 > 5" являются простыми. Составные высказывания образуются из простых с помощью связок естественного (русского) языка НЕ, И, ИЛИ, ЕСЛИ-ТО, ТОГДА-И-ТОЛЬКО-ТОГДА. При использовании буквенных обозначений для высказываний эти связки заменяются специальными математическими символами, которые можно рассматривать как символы логических операций.

Ниже, в таблице 1 приведены варианты символов для обозначения связок и названия соответствующих логических операций.

Отрицанием (инверсией) высказыванияX называется высказывание, истинное тогда и только тогда, когдаX ложно (обозначаетсяили, читается “неX ” или “неверно, чтоX ”).

Конъюнкцией
двух высказываний называется высказывание, истинное тогда и только тогда, когда истинны оба высказыванияX иY . Эта логическая операция соответствует соединению высказываний союзом ”и”.

Дизъюнкцией
двух высказыванийX иY называется высказывание ложное в том и только в том случае, когда оба высказыванияX иY ложны. В разговорной речи этой логической операции соответствует союз “или” (не исключающее “или”).

Импликацией двух высказыванийX и Y называется высказывание, ложное тогда и только тогда, когдаX истинно, аY – ложно (обозначается
; читается “X влечетY ”, “еслиX , тоY ”). Операнды этой операции имеют специальные названия:X – посылка,Y – заключение.

Эквиваленцией двух высказыванийX иY называется высказывание, истинное тогда и только тогда, когда истинностные значенияX иY одинаковы (обозначение:
).

Таблица 1. Логические операции

Операнды логических операций могут принимать только два значения: 1 или 0. Поэтому каждую логическую операцию , &,,,легко задать с помощью таблицы, указав значение результата операции в зависимости от значений операндов. Такая таблица называется таблицей истинности (табл. 2).

Таблица 2. Таблица истинности логических операций

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

Для систематического изучения формул, выражающих высказывания, вводят переменные высказывания P, P 1 , P 2 , ..., P N , принимающие значения из множества {0, 1}.

Формула логики высказываний F (P 1 , P 2 ,..., P N ) называется тавтологией или тождественно истинной , если ее значение для любых значений P 1 , P 2 ,..., P N есть 1 (истина). Формулы, принимающие значение “истина” хотя бы при одном наборе списка переменных, называются выполнимыми . Формулы, принимающие значение “ложь” при любых значениях переменных, называются противоречиями (тождественно ложными, невыполнимыми).

Предлагаемое учебное пособие (2-ое изд., стереотип.) составляет основу комплекта по курсу математической логики и теории алгоритмов, в который также входит сборник задач (Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов).

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

Введение. Математическая логика в системе современного образования.
Логика и интуиция. Логика традиционная и математическая логика. Немного истории. Математическая логика - логика или математика? Математическая логика в обучении математике. Математическая логика и современные ЭВМ.
Глава I. Алгебра высказываний.
§ 1. Высказывания и операции над ними.
Понятие высказывания. Отрицание высказывания. Конъюнкция двух высказываний. Дизъюнкция двух высказываний. Импликация двух высказываний. Эквивалентность двух высказываний. Союзы языка и логические операции (язык и логика). Общий взгляд на логические операции.
§2. Формулы алгебры высказываний.
Конструирование сложных высказываний. Понятие формулы алгебры высказываний. Логическое значение составного высказывания. Составление таблиц истинности для формул. Классификация формул алгебры высказываний. Мышление и математическая логика
§ 3. Тавтологии алгебры высказываний.
О значении тавтологий. Основные тавтологии. Основные правила получения тавтологии.
§ 4. Логическая равносильность формул.
Понятие равносильности формул. Признак равносильности формул. Примеры равносильных формул. Равносильные преобразования формул. Равносильности в логике и тождества в алгебре.
§ 5. Нормальные формы для формул алгебры высказываний.
Понятие нормальных форм. Совершенные нормальные формы. Представление формул алгебры высказываний совершенными дизъюнктивными нормальными (СДН) формами. Представление формул алгебры высказываний совершенными конъюнктивными нормальными (СКН) формами. Два способа приведения формулы алгебры высказываний к совершенной нормальной форме
§ 6. Логическое следование формул.
Понятие логического следствия. Признаки логического следствия. Два свойства логического следования. Следование и равносильность формул. Правила логических умозаключений. Еще один способ проверки логического следования. Нахождение следствий из данных посылок. Нахождение посылок для данного следствия.
§ 7. Приложение алгебры высказываний к логико-математической практике.
Прямая и обратная теоремы. Необходимые и достаточные условия. Противоположная и обратная противоположной теоремы. Закон контрапозиции. Модификация структуры математической теоремы. Методы доказательства математических теорем. Дедуктивные и индуктивные умозаключения. Правильные и неправильные дедуктивные умозаключения. Решение логических задач. Принцип полной дизъюнкции. Одно обобщение принципа полной дизъюнкции.
Глава II. Булевы функции.
§8. Множества, отношения, функции.
Понятие множества. Включение и равенство множеств. Операции над множествами. Бинарные отношения и функции. Понятие ларного отношения.
§ 9. Булевы функции от одного и двух аргументов.
Происхождение булевых функций. Булевы функции от одного аргумента. Булевы функции от двух аргументов. Свойства дизъюнкции, конъюнкции и отрицания. Свойства эквивалентности, импликации и отрицания. Выражение одних булевых функций через другие
§ 10. Булевы функции от п аргументов.
Понятие булевой функции. Число булевых функций. Выражение булевых функций через конъюнкцию, дизъюнкцию и отрицание. Булевы функции и формулы алгебры высказываний. Нормальные формы булевых функций.
§ 11. Системы булевых функций.
Полные системы булевых функций. Специальные классы булевых функций. Теорема Поста о полноте системы булевых функций
§ 12. Применение булевых функций к релейно-контактным схемам.
Идея применения. Две основные задачи теории релейно-контактных схем.
§ 13. Релейно-контактные схемы в ЭВМ.
Двоичный полусумматор. Одноразрядный двоичный сумматор. Шифратор и дешифратор.
§ 14. О некоторых других приложениях теории булевых функций.
Диагностика (распознавание) заболеваний. Распознавание образов.
Глава III. Формализованное исчисление высказываний.
§ 15. Система аксиом и теория формального вывода.
Начало аксиоматической теории высказываний: первоначальные понятия, система аксиом, правило вывода. Понятие вывода и его свойства. Теорема о дедукции и следствия из неё. Применение теоремы о дедукции. Производные правила вывода
§ 16. Полнота и другие свойства формализованного исчисления высказываний
Доказуемость формулы и ее тождественная истинность (синтаксис и семантика). Лемма о выводимости. Полнота формализованного исчисления высказываний. Теорема адекватности. Непротиворечивость формализованного исчисления высказываний. Разрешимость формализованного исчисления высказываний
§ 17. Независимость системы аксиом формализованного исчисления высказываний.
Понятие независимости. Независимость аксиомы (А1). Независимость аксиомы (А2). Независимость аксиомы (A3). Независимость системы аксиом
Глава IV. Логика предикатов.
§ 18. Основные понятия, связанные с предикатами.
Понятие предиката. Классификация предикатов. Множество истинности предиката. Равносильность и следование предикатов
§ 19. Логические операции над предикатами.
Отрицание предиката. Конъюнкция двух предикатов. Дизай перейти на страницу дикатов. Свойства отрицания, конъюнкции и дизъюнкции. Импликация и эквивалентность двух предикатов.
§ 20. Кванторные операции над предикатами.
Квантор общности. Квантор существования. Численные кванторы. Ограниченные кванторы. Логический квадрат
§ 21. Формулы логики предикатов.
Понятие формулы логики предикатов. Классификация формул логики предикатов. Тавтологии логики предикатов
§ 22. Равносильные преобразования формул и логическое следование формул логики предикатов
Понятие равносильности формул. Приведенная форма для формул логики предикатов. Предваренная нормальная форма для формул логики предикатов. Логическое следование формул логики предикатов
§ 23. Проблемы разрешения для обще значимости и выполнимости формул.
Постановка проблемы и ее неразрешимость в общем виде. Решение проблемы для формул на конечных множествах. Пример формулы, выполнимой на бесконечном множестве и невыполнимой ни на каком конечном множестве. Проблема разрешения выполнимости: влияние мощности множества и структуры формулы. Решение проблемы для формул, содержащих только одноместные предикатные переменные. Проблема разрешения общезначимости и мощность множества, на котором рассматривается формула. Решение проблемы для V-формул и 3-формул
§ 24. Применение логики предикатов к логико-математической практике.
Запись на языке логики предикатов различных предложении. Сравнение логики предикатов и логики высказываний. Строение математических теорем. Методы рассуждений: аристотелева силлогистика. Аристотелева силлогистика и логика предикатов. Теоретико-множественная интерпретация аристотелевой силлогистики. О других методах рассуждений. Принцип полной дизъюнкции в предикатной форме. Метод (полной) математической индукции Необходимые и достаточные условия. Логика предикатов и алгебра множеств.
§ 25. Формализованное исчисление предикатов.
Первоначальные понятия (язык формализованного исчисления предикатов). Система аксиом исчисления предикатов. Правила вывода. Теория формального вывода.
Глава V. Неформальные аксиоматические теории.
§ 26. Аксиоматический метод в математике и аксиоматические теории.
Понятие аксиоматической теории. Как возникают аксиоматические теории. Примеры аксиоматических теорий. Интерпретации и модели аксиоматической теории.
§ 27. Свойства аксиоматических теорий.
Непротиворечивость. Категоричность. Независимость системы аксиом. Полнота.
Глава VI. Формальные аксиоматические теории.
§ 28. О формальных аксиоматических теориях.
Об истории идеи формальной аксиоматической теории. Понятие формальной аксиоматической теории. Язык и метаязык, теоремы и метатеоремы формальной теории. Интерпретации и модели формальной теории. Семантическая выводимость. Метаматематика (свойства формальных аксиоматических теорий) . Формализованное исчисление высказываний как формальная аксиоматическая теория.Формализация теории аристотелевых силлогизмов.
§ 29. Свойства формализованного исчисления предикатов.
Оправданность аксиоматизации.Непротиворечивость формализованного исчисления предикатов. Теорема Гёделя о существовании модели. Полнота и адекватность формализованного исчисления предикатов. Неполнота формализованного исчисления предикатов в абсолютном и узком смыслах.Теорема компактности.
§ 30. Формальные теории первого порядка.
Теории первого порядка с равенством. О формальных теориях множеств. О формальной арифметике. О формальных теориях числовых систем.О формальной геометрии. О формальном математическом анализе. Обший взгляд на процесс формализации математической теории.О границах аксиоматического метода, метода формализации и логики.
Глава VII. Элементы теории алгоритмов.
§31. Интуитивное представление об алгоритмах.
Алгоритмы вокруг нас. Неформальное понятие алгоритма. Необходимость уточнения понятия алгоритма.
§ 32. Машины Тьюринга.
Определение машины Тьюринга.Применение машин Тьюринга к словам. Конструирование машин Тьюринга. Вычислимые по Тьюрингу функции. Правильная вычислимость функций на машине Тьюринга. Композиция машин Тьюринга. Тезис Тьюринга (основная гипотеза теории алгоритмов) . Машины Тьюринга и современные электронно-вычислительные машины.
§ 33. Рекурсивные функции.
Происхождение рекурсивных функций. Основные понятия теории рекурсивных функций и тезис Черча. Примитивно рекурсивные функции. Примитивная рекурсивность предикатов. Вычислимость по Тьюрингу примитивно рекурсивных функций. Функции Аккермана. Оператор минимизации. Общерекурсивные и частично рекурсивные функции. Вычислимость по Тьюрингу частично рекурсивных функций. Частичная рекурсивность функций, вычислимых по Тьюрингу.
§34. Нормальные алгоритмы Маркова.
Марковские подстановки. Нормальные алгоритмы и их применение к словам. Нормально вычислимые функции и принцип нормализации Маркова. Совпадение класса всех нормально вычислимых функций с классом всех функций, вычислимых по Тьюрингу. Эквивалентность различных теорий алгоритмов.
§ 35. Разрешимость и перечислимость множеств.
§ 36. Неразрешимые алгоритмические проблемы.
Нумерация алгоритмов. Нумерация машин Тьюринга. Существование невычислимых по Тьюрингу функций. Проблемы распознавания самоприменимости и применимости. Алгоритмически неразрешимые проблемы в обшей теории алгоритмов. Теорема Раиса. Другие примеры алгоритмической неразрешимости.
§ 37. Теорема Гёделя о неполноте формальной арифметики.
Формальные аксиоматические теории и натуральные числа. Формальная арифметика и ее свойства. Теорема Гёделя о неполноте. Гёдель и его роль в математической логике XX в. .
Глава VIII. Математическая логика и компьютеры, информатика, искусственный интеллект.
* § 38. Математическая логика и программное обеспечение компьютеров.
Теория алгоритмов и математическая логика - фундаментальная основа программирования. Описание компьютерных программ с помощью математической логики. Описание программирования и анализ его концепций с помощью математической логики. Верификация (доказательство правильности) программ с помощью математической логики.
§ 39. Применение компьютеров для доказательства теорем математической логики.
Программа «Логик-теоретик» и программы, близкие к ней. Метод резолюций для доказательства теорем исчисления высказываний и исчисления предикатов.
§ 40. От математической логики к логическому программированию.
Возникновение языка ПРОЛОГ и его развитие. Общая характеристика языка ПРОЛОГ. Краткое описание языка ПРОЛОГ и примеры. Сферы применения языка ПРОЛОГ.
§41. Математическая логика и информатика.
Общее понятие о базе данных. Реляционная база данных и логика запросов в ней.
§ 42. Математическая логика и системы искусственного интеллекта История развития и предмет искусственного интеллекта как науки. Представление знаний в системах искусственного интеллекта. Экспертные системы. Язык ПРОЛОГ в системах искусственного интеллекта. Может ли машина мыслить.
Заключение: Всесильна ли логика в познании законов мышления?
Список литературы.

Логика и интуиция.
Мыслительная деятельность человека представляет собой сложный и многогранный процесс, происходящий как на сознательном, так и на бессознательном (подсознательном) уровнях. Это высшая ступень человеческого познания, способность к адекватному отражению предметов и явлений действительности, т.е. к нахождению истины.

Логика и интуиция -два противоположных и неразрывно связанных между собой свойства человеческого мышления. Логическое (дедуктивное) мышление отличается тем, что оно от истинных посылок всегда приводит к истинному заключению, не опираясь при этом на опыт, интуицию и другие внешние факторы. Интуиция (от лат. intuitio - «пристальное всматривание») представляет собой способность постижения истины путем прямого ее усмотрения без обоснования с помощью логически строгого доказательства. Таким образом, интуиция является своего рода антиподом, противовесом логики и строгости.

Логическая часть мыслительного процесса протекает на уровне сознания, интуитивная - на подсознательном уровне.
Развитие науки и особенно математики немыслимо без интуиции. Различают два вида интуиции в научном познании1: интуицию-суждение и интуицию-догадку. Интуиция-суждение (или философская интуиция-суждение) характеризуется тем, что в этом случае прямое усмотрение истины, объективной связи вещей осуществляется не просто без логически строгого доказательства, но такого доказательства для данной истины не существует и не может существовать в принципе. Интуиция-суждение осуществляется как единый (единовременный) синтетический целостный акт обобщающего характера. Именно такой характер логически недоказуемых утверждений носят рассматриваемые в теории алгоритмов тезисы Тьюринга, Чёрча и Маркова.

Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Математическая логика и теория алгоритмов, Игошин В.И., 2008 - fileskachat.com, быстрое и бесплатное скачивание.

11.1. Понятие об алгоритме и теории алгоритмов

Интуитивно под алгоритмом понимается процесс последовательного решения задачи, протекающей в дискретном времени так, что в каждый следующий момент времени система объектов алгоритма получается по определённому закону из системы объектов, имевшихся в предыдущий момент времени . Интуитивно потому, что, строго говоря, понятие алгоритма сродни понятию множества, которое неопределимо.

В соответствии с ГОСТ 19781-74 «Машины вычислительные. Программное обеспечение. Термины и определения» алгоритм – это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату. При этом предполагается наличие исполнителя алгоритма – такого объекта, который «умеет» выполнять эти действия.

Слово «алгоритм» происходит, как предполагают, от имени среднеазиатского (узбекского) математика XIII века Аль Хорезми (Абу Абдалла Мухаммед ибн Муса ал Хорезми ал Меджуси) – «Algorithmi» в латинской транскрипции, впервые сформулировавшего правила (процедуру) выполнения четырех арифметических действий в десятичной системе счисления.

Пока вычисления были несложными, особой необходимости в алгоритмах не было. Когда появилась потребность в многократных пошаговых процедурах, тогда и появилась теория алгоритмов. Но при еще большем усложнении задач, оказалось, что часть из них невозможно решать алгоритмическим путем. Таковы, например, многие задачи, решаемые «бортовым компьютером» человека – головным мозгом. Решение таких задач основывается на иных принципах – эти принципы использует новая наука – нейроматематика и соответствующие технические средства – нейрокомпьютеры. В этом случае применяются процессы обучения, проб и ошибок – то есть то, чем мы сейчас и занимаемся.

Качество алгоритма определяется его свойствами (характеристиками). К основным свойствам алгоритма относятся :

1. Массовость . Предполагается, что алгоритм может быть пригоден для решения всех задач данного типа. Например, алгоритм для решения системы линейных алгебраических уравнений должен быть применим к системе, состоящей из произвольного числа уравнений.

2. Результативность . Это свойство означает, что алгоритм должен приводить к получению результата за конечное число шагов.

3. Определенность . Предписания, входящие в алгоритм, должны быть точными и понятными. Эта характеристика обеспечивает однозначность результата вычислительного процесса при заданных исходных данных.

4. Дискретность . Это свойство означает, что описываемый алгоритмом процесс и сам алгоритм могут быть разбиты на отдельные элементарные этапы, возможность выполнения которых на ЭВМ у пользователя не вызывает сомнений.

Сегодня на дворе «цифровое тысячелетие» и может создастся впечатление, что алгоритмам подвластны любые задачи. Оказывается, многие задачи не могут быть решены алгоритмически. Это так называемые алгоритмически неразрешимые задачи.

Для доказательства алгоритмической разрешимости или неразрешимости задач необходимы математически строгие и точные средства. В середине 30-х годов прошлого века были предприняты попытки формализовать понятие алгоритма и были предложены различные модели алгоритмов : рекурсивные функции; «машины» – Тьюринга, Поста; нормальные алгорифмы Маркова.

Впоследствии было установлено, что эти и другие модели эквивалентны в том смысле, что классы решаемых ими задач совпадают . Этот факт носит название тезиса Черча. Сейчас это общепризнанно. Формальное определение понятия алгоритма создало предпосылки для разработки теории алгоритма ещё до разработки первых ЭВМ. Прогресс вычислительной техники стимулировал дальнейшее развитие теории алгоритмов. Помимо установления алгоритмической разрешимости задач, теория алгоритмов занимается еще и оценкой сложности алгоритмов в смысле числа шагов (временная сложность) и требуемой памяти (пространственная сложность), а также занимается разработкой эффективных в этом смысле алгоритмов.

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

Поэтому еще одна задача теории алгоритмов – решение вопроса исключения перебора вариантов в комбинаторных алгоритмах. Оценка сложности алгоритмов и создания так называемых эффективных алгоритмов – одна из важнейших задач современной теории алгоритмов.