1288
правок
Теория алгоритмов: различия между версиями
Материал из WikiGrapp
нет описания правки
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Теория алгоритмов''', раздел математики, изучающий общие свойства алгоритмов. Содержательные явления, приведшие к образованию понятия "алгоритм", прослеживаются в математике в течение всего времени её существования. Однако само это понятие сформировалось лишь в 20 в. и стало предметом самостоятельного изучения (по-видимому, впервые, хотя ещё в расплывчатом виде) лишь в 20-х гг. 20 в. в трудах представителей математического интуиционизма Л. Э. Я. Брауэра и Г. Вейля. Началом систематической разработки '''теории алгоритмов'''. можно считать 1936, когда А. Чёрч опубликовал первое уточнение понятия [[вычислимая функция|вычислимой функции]] (предложив отождествлять понятие всюду определённой вычислимой функции, имеющей натуральные аргументы и значения, с понятием [[общерекурсивная функция | общерекурсивной функции]]) и привёл первый пример функции, не являющейся вычислимой, а А. М. Тьюринг и Э. Л. Пост дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин, см. Тьюринга машина). В дальнейшем '''теории алгоритмов''' получила развитие в трудах С. К. Клини, Э. Л. Поста, А. А. Маркова и других. В частности, А. А. Марков предложил уточнять понятие алгоритма с помощью введённого им понятия [[нормальный алгоритм|нормального алгоритма]]. Наиболее общий подход к уточнению понятия алгоритма предложил А. Н. Колмогоров. | '''Теория алгоритмов''', раздел математики, изучающий общие свойства алгоритмов. Содержательные явления, приведшие к образованию понятия "алгоритм", прослеживаются в математике в течение всего времени её существования. Однако само это понятие сформировалось лишь в 20 в. и стало предметом самостоятельного изучения (по-видимому, впервые, хотя ещё в расплывчатом виде) лишь в 20-х гг. 20 в. в трудах представителей математического интуиционизма Л. Э. Я. Брауэра и Г. Вейля. Началом систематической разработки '''теории алгоритмов'''. можно считать 1936, когда А. Чёрч опубликовал первое уточнение понятия [[вычислимая функция|вычислимой функции]] (предложив отождествлять понятие всюду определённой вычислимой функции, имеющей натуральные аргументы и значения, с понятием [[общерекурсивная функция | общерекурсивной функции]]) и привёл первый пример функции, не являющейся вычислимой, а А. М. Тьюринг и Э. Л. Пост дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин, см. [[Машина Тьюринга|Тьюринга машина]]). В дальнейшем '''теории алгоритмов''' получила развитие в трудах С. К. Клини, Э. Л. Поста, А. А. Маркова и других. В частности, А. А. Марков предложил уточнять понятие алгоритма с помощью введённого им понятия [[нормальный алгоритм|нормального алгоритма]]. Наиболее общий подход к уточнению понятия алгоритма предложил А. Н. Колмогоров. | ||
| Строка 17: | Строка 17: | ||
== Алгоритмические проблемы == | == Алгоритмические проблемы == | ||
Проблема построения алгоритма, обладающего теми или иными свойствами, называется [[алгоритмическая проблема|алгоритмической проблемой]]. Как правило, свойство искомого алгоритма формулируется в терминах свойств того соответствия, которое должно иметь место между исходными данными и результатами алгоритма. Важные примеры алгоритмических проблем: проблема вычисления данной функции (требуется построить алгоритм, вычисляющий эту функцию): проблема разрешения данного множества (требуется построить алгоритм, разрешающий это множество относительно некоторого другого множества); проблема перечисления данного множества (требуется построить алгоритм, перечисляющий данное множество). [[Неразрешимая алгоритмическая проблема|Неразрешимость]] алгоритмической проблемы означает отсутствие соответствующего алгоритма; теоремы, устанавливающие неразрешимость таких проблем, относятся к числу наиболее важных теорем теории алгоритмов. | Проблема построения алгоритма, обладающего теми или иными свойствами, называется [[алгоритмическая проблема|алгоритмической проблемой]]. Как правило, свойство искомого алгоритма формулируется в терминах свойств того соответствия, которое должно иметь место между исходными данными и результатами алгоритма. Важные примеры алгоритмических проблем: ''проблема вычисления данной функции'' (требуется построить алгоритм, вычисляющий эту функцию): ''проблема разрешения данного множества'' (требуется построить алгоритм, разрешающий это множество относительно некоторого другого множества); ''проблема перечисления данного множества'' (требуется построить алгоритм, перечисляющий данное множество). [[Неразрешимая алгоритмическая проблема|Неразрешимость]] алгоритмической проблемы означает отсутствие соответствующего алгоритма; теоремы, устанавливающие неразрешимость таких проблем, относятся к числу наиболее важных теорем теории алгоритмов. | ||
== Метрическая теория алгоритмов == | == Метрическая теория алгоритмов == | ||
| Строка 27: | Строка 27: | ||
'''Теорию алгоритмов''' тесно связана с математической логикой, поскольку на понятие алгоритма опирается одно из центральных понятий математической логики — понятие исчисления и потому, например, теорема К. Гёделя о неполноте формальных систем может быть получена как следствие теорем теории алгоритмов. Наконец, '''теория алгоритмов''' тесно связана с основаниями математики, в которых одно из центральных мест занимает проблема соотношения конструктивного и неконструктивного, в частности '''теория алгоритмов''' даёт аппарат, необходимый для разработки конструктивного направления в математике; в 1965 А. Н. Колмогоров предложил использовать '''теорию алгоритмов''' для обоснования информации теории. '''Теорию алгоритмов''' образует теоретический фундамент для ряда вопросов вычислительной математики и тесно связана с кибернетикой, в которой важное место занимает изучение алгоритмов управления, в частности понятие алгоритма занимает центральное место в так называемом программированном обучении. | '''Теорию алгоритмов''' тесно связана с математической логикой, поскольку на понятие алгоритма опирается одно из центральных понятий математической логики — понятие исчисления и потому, например, теорема К. Гёделя о неполноте формальных систем может быть получена как следствие теорем теории алгоритмов. Наконец, '''теория алгоритмов''' тесно связана с основаниями математики, в которых одно из центральных мест занимает проблема соотношения конструктивного и неконструктивного, в частности '''теория алгоритмов''' даёт аппарат, необходимый для разработки конструктивного направления в математике; в 1965 А. Н. Колмогоров предложил использовать '''теорию алгоритмов''' для обоснования информации теории. '''Теорию алгоритмов''' образует теоретический фундамент для ряда вопросов вычислительной математики и тесно связана с кибернетикой, в которой важное место занимает изучение алгоритмов управления, в частности понятие алгоритма занимает центральное место в так называемом программированном обучении. | ||
==Литература== | |||
* Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965. | |||
* Марков А. А., Теория алгорифмов, М. — Л., 1954 (Тр. Матем. института АН СССР, т. 42). | |||
Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965. | * Колмогоров А. Н., Три подхода к определению понятия "количество информации", "Проблемы передачи информации", 1965, т. 1, в. 1. | ||
* Ершов Ю. Л. [и др.], Элементарные теории, "Успехи математических наук", 1965, т. 20, в. 4. | |||
* Марков А. А., О нормальных алгорифмах, связанных с вычислением булевых функций, "Известия АН СССР. Серия математическая", 1967, т. 31, в. 1. | |||
* Трахтенброт Б. А., Сложность алгоритмов и вычислений, Новосиб., 1967. | |||
* Успенский В. А. Алгоритмов теория, Большая советская энциклопедия: В 30 т., М.: "Советская энциклопедия", 1969-1978. | |||
[[Категория:Теория автоматов]] | |||
