Математический аппарат инженера

Так, в нашем примере при воздействии 0 классы S'₀ и S'₁ переходят в {1, 5}, а S'₂ – в {3, 5}; при воздействии 1 класс S'₀ переходит в {4, 5}, S'₁ – в {5} и S'₂ – в {1, 5}. Следовательно, исходный автомат можно представить квазиэквивалентным ему автоматом, в котором классам совместимости S'₁, S₂,..., S'_w соответствуют состояния σ'₀, σ'₁

, ..., σ'_w . Однако такой автомат не всегда будет минимальным. Для получения минимальной формы автомата необходимо отобрать наименьшее число таких классов совместимости, которые образуют покрытие множества состояний S и в то же время включают множества состояний, следующих за состояниями каждого класса при всех незапрещенных воздействиях. Для рассматриваемого примера этим требованиям удовлетворяют классы S'₀ и S'₁, так как S'₀ ∪ S'₂ = S, и все множества последующих состояний {1, 5}, {3, 5}, {4, 5} и {5} являются подмножествами S'₀ и S'₂. Соответствующая минимальная форма показана на рис. 241, б, где состояния 0и 1

соответствуют классам S'₀ и S'₂.

Дальнейшие упрощения относятся не к числу состояний, а к структуре множеств, образующих минимальное покрытие S. Если из отобранных классов толерантности можно исключить некоторые состояния так, что полученные подмножества удовлетворяют приведенным выше требованиям, то эти подмножества также определяют другой вариант минимальной формы автомата. Так, из S'₀ или из S'₂ можно исключить состояние 4, поскольку оно входит только в множество последующих состояний {4, 5}. Тогда получим еще два варианта минимальных покрытий: {0, 1, 5}, {2, 3, 4, 5} и {0, 1, 4, 5}, {2, 3, 5}. Но состояние 5 нельзя исключить ни из одного класса, хотя оно и содержится в каждом из них, так как множества последующих состояний {1, 5} и {3, 5} показывают, что состояние 5 должно содержаться как в S'₀, так и в S'₂.

- !!!!!!!!!!!!!!!!!!!!! -

- Продолжение следует... -

- Содержание продолжения -

...

7. Многозначная логика 583

8. Логика высказываний 596

9. Логика предикатов 608

10. Алгоритмы

1. Что такое алгоритм? С давних времен в математике сложилось интуитивное представление об алгоритме как формальном предписании, которое определяет совокупность операций и порядок их выполнения для решения всех задач какого-либо типа.

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

Каждый встречается с алгоритмами со школьной скамьи. Правила, по которым выполняются арифметические действия с многоразрядными числами являются простейшими примерами алгоритмов. Сам термин "алгоритм" происходит от имени средневекового узбекского математика Мухаммеда бен Муса аль Хорезми, который еще в IX веке сформулировал такие правила. В своем развитии математика накопила огромное количество различных алгоритмов. Получая соответствующую интерпретацию в конкретных приложениях, они составляют значительную и наиболее существенную часть математического аппарата, используемого в технике.

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

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

2. Численные алгоритмы. Алгоритмы, которые сводят решение поставленной задачи к арифметическим действиям над числами, называются численными алгоритмами. Традиционным примером является известный алгоритм Евклида для нахождения наибольшего общего делителя двух заданных целых положительных чисел a и b.

Алгоритм Евклида состоит из следующей системы последовательных указаний:

1) обозревай a и b и переходи к следующему;

2) сравни обозреваемые числа (a = b, или a b, или ) и переходи к следующему;

3) если обозреваемые числа равны, то каждое из них дает искомый результат, если нет — переходи к следующему;

4) если первое обозреваемое число меньше второго, переставь

- 621 -

их местами и переходи к следующему;