Техника - молодёжи 2005-07, страница 31
Состояние I Состояние II Состояние III Таблица истинности Рис. 6. Логический элемент ИЛИ Xi QB I I Хг Х1 I ГП Хг Сброс L j Сброс Рис. 7. Логический элемент И М X t В F1 М Сброс Сброс Сброс Рис. 8. Логический элемент НЕ знание метода контурных токов («правило Кирхгофа»), который в школе может и не изучаться. Теперь представим, что не пять сопротивлений, а несколько их сотен соединены в виде мостиков и звездочек различной конфигурации. В принципе, понятно, как решать и эту задачу, но, ввиду сложности схемы, за приемлемое время это сделать будет очень непросто. В книге «Новый ум короля» Пенроуз ссылается на знаменитую задачу коммивояжера, поставленную еще в 1934 г., и которая является одной из важнейших в теории графов. В своей области (дискретных оптимизационных задач) задача коммивояжера служит своеобразным полигоном, на котором испытываются все новые методы. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в произвольном порядке города 2,3,4...п и вернуться в первый город. Расстояния между всеми городами известны. В каком порядке следует обходить города, чтобы замкнутый путь коммивояжера был кратчайшим? В терминах теории графов: найти в графе гамильто-нов цикл минимальной длины (рис. 3). С проблемами, подобными той, с которой столкнулся коммивояжер, мы встречаемся в реальной жизни довольно часто. А вместе с тем, несмотря на внешне кажущуюся простоту, эта задача относится к классу NP-сложных, точное решение которых, в общем случае, может быть получено только за экспоненциальное время. Уже при числе городов в несколько сотен решение такой задачи на самой совре Таблица истинности
менной ЭВМ методом полного перебора может затянуться на годы. Применение методов сокращенного перебора, типа «ветвей и границ», помогает в решении отдельных задач, но принципиально картины не меняет. Еще одним препятствием успешного использования ЭВМ является проблема вычислимости в физических процессах. Пенроуз иллюстрирует эту проблему примером из «ньютонианского бильярдного мира». На рис. 4 показан бильярдный стол с пятью шарами. Задача состоит в том, чтобы забить шар 5 в лузу А путем последовательного соударения всех шаров. Пользуясь механикой Ньютона, в принципе, можно вычислить траектории шаров 1,2,3,4, чтобы загнать шар 5 в лузу А. Желающие могут попробовать решить эту задачу на реальном бильярдном столе. Но усложним несколько эту задачу и предположим, что шары 1,2,3,4,5 будут иметь множественные столкновения (см. рис. 5). Шар 2 сталкивается не только с шаром 3, но и с шаром 3*, а шар 4 не только с шаром 5, но и шаром 5*. Задача вычисления траекторий шаров становится еще более трудной. Пенроуз высказывает предположение, что для бильярдной модели, в которой имеют место множественные столкновения, проблема вычислимости может сделать невозможным алгоритмическое описание поведения подобной системы, а следовательно, и невозможным моделирование ее поведения на ЭВМ. Предполагается, что для исследования объектов, систем, процессов, описание которых алгоритмически невозможно, должны существовать модели, построенные на иных физических принципах. Элементы автоматики на потоках сыпучей среды. В настоящей статье рассматриваются элементы автоматики на управляемых потоках сыпучей среды. Особенностью названных элементов является то, что отдельные частицы сыпучей среды в них совершают множественные столкновения, а сами элементы можно объединять в устойчивые динамические сети, подобные графу коммивояжера. Характерным является тот -факт, что на сыпучую среду не распространяются законы о сообщающихся сосудах и о равном давлении на стенки сосуда, как в жидкостях и газах, а также закон о выравнивании энергетических потенциалов (в отличие от пневмо-, гидро-, электросетей, где при соединении двух любых точек трубопроводом или, соответственно, электропроводом, энергетические потенциалы этих точек выравниваются (соответственно, давление и разность потенциалов). Но если построить сеть, в которой рабочим телом будет являться сыпучая среда, то при соединении двух точек сети выравнивания энергетических потенциалов не происходит. Но, несмотря на такие «нетрадиционные» свойства, оказалось возможным создание элементов автоматики, рабочим телом в которых является сыпучая среда (подобная той, что используется в песочных часах)1. Прежде чем познакомиться с указанными устройствами поближе, сделаем небольшой экскурс в историю математики. Представим знаменитого английского математика Джорджа Буля, который не только отец Этель Лилиан Войнич, но и создатель знаменитой булевой алгебры. В его алгебре переменные и функция принимают только значения, равные 0 или 1. При переборе всех возможных вариантов булевых функций Y = (Х1, Х2), общее их количество оказывается равным 16. Их изучение позволило определить функционально полные Подробное описание элементов автоматики на управляемых потоках сыпучей среды можно найти в А.С. СССР № 1126803, 1126729, 1578384, 1661803, авт. Рыппо В.Л. ТЕХНИКА- МОЛОДЕЖИ 7' 2 0 0 5 29 |
|||||||||||||||||||||||||||||||||||||||||
