.
Меню сайта
|
Алгоритмы и автоматыАлгоритмы и автоматыВопросы кодирования и декодирования, т.е. восстановления исходного вида информации по ее дискретному коду, и другие проблемы возникают в первую очередь при разработке вводных и выводных устройств управляющих систем. Теоретическую основу устройств для преобразования информации составляют другие разделы современной кибернетики теория алгоритмов и теория автоматов. Алгоритмом называется конечная система правил, по которым совершается преобразование дискретной информации. Множество разнообразных алгоритмов имеется в математике. Из школьного курса алгебры, например, вам хорошо известны алгоритмы для решения квадратных уравнений, систем линейных уравнений, для раскрытия скобок и приведения подобных членов в буквенных выражениях и т. п. Но алгоритмы широко распространены и за пределами математики. Если сформулировать все правила, которые употребляет опытный переводчик для переводов, скажем, с английского языка на русский, то получим не что иное, как алгоритм англо-русского перевода. Если элементарные правила шахматной игры дополнить системой стратегических правил, позволяющих в каждой позиции находить единственный, наилучший (с точки зрения данной системы правил) ход, то получится алгоритм игры в шахматы. Оказывается, чуть ли не всякий вид умственной деятельности человека может быть сведен к выполнению того или иного алгоритма. Но практически найти все правила, составляющие эти алгоритмы,— часто очень сложная и трудоемкая задача. Для кибернетики особенно важны два результата, полученные в теории алгоритмов. Первый результат — универсальность алгоритмических систем. Оказывается, для построения любого алгоритма достаточно уметь выполнять относительно небольшое число типов элементарных алгоритмических операций. Подобно тому как из одних и тех же элементарных частиц складываются молекулы самых различных веществ или как из одних и тех же букв складываются книги совершенно различного содержания, так и всякий алгоритм, независимо от его природы, можно составить в результате соответствующего комбинирования элементарных алгоритмических операций. Второй важный результат теории алгоритмов заключается в том, что существуют так называемые алгоритмически неразрешимые проблемы, т. е. такие классы задач, которые для своего решения требуют бесконечного числа различных приемов. А всякий алгоритм обязательно включает в себя лишь конечное число приемов, хотя, может быть, и очень большое. Так, например, можно построить алгоритм, который позволяет доказать любую теорему из элементарной геометрии (не использующей понятие предела). В то же время доказано, что для теории чисел (устанавливающей различные свойства целых чисел) подобного алгоритма не существует. Иначе говоря, для построения элементарной геометрии достаточно конечного числа приемов (методов доказательства), а для построения теории чисел число соответствующих приемов должно быть непременно бесконечным.
|
ПОИСК
Block title
|