Том 11. Карты метро и нейронные сети. Теория графов - Клауди Альсина

a + b = c + d = p + q = 10.

Следовательно, существует множество различных вариантов, например:

а = 1, Ь = 9, с = 2, d = 8, р = 3, q = 7.

* * *

ТЕОРИЯ ИГР

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

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

Так как в общем случае число «игроков» (инвесторов, работников, банков) является конечным, так же как и число игр, стратегий и возможных вариантов, то при анализе задач теории игр часто применяется теория графов.

* * *

Теория графов в школе

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

Курс «Теория графов и ее применение» сегодня изучается как часть курса математики, исследования операций, дискретной математики, входит в программу различных инженерных специальностей (строительство, электроэнергетика, телекоммуникации) и, разумеется, в курс информатики.

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

Среди преимуществ теории графов применительно к образованию выделим следующие.

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

2. Графы — прекрасный пример использования математики в повседневной жизни. Они помогают увидеть, что математика постоянно присутствует в окружающем нас мире.

3. Изучение графов стимулирует индуктивное, комбинаторное и пространственное мышление, что имеет высокую образовательную ценность.

4. Графы помогают решать занимательные и прикладные задачи. Благодаря работам Дьёрдя Пойа мы знаем, что решение задач — один из двигателей обучения математике.

С учетом вышесказанного будет уместно привести цитату из «Алисы в стране чудес» Льюиса Кэрролла, где Алиса разговаривает с Котом:

«— Скажите, пожалуйста, куда мне отсюда идти?

— А куда ты хочешь попасть? — ответил Кот.

— Мне все равно… — сказала Алиса.

— Тогда все равно, куда и идти, — заметил Кот».

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

Графы и нейронные сети

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

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

Моделирование нейронов человеческого мозга и принципа их действия легло в основу новой теории, известной как теория искусственных нейронных сетей, или просто теория нейронных сетей.

Нейронная сеть состоит из единичных элементов, называемых нейронами, которые получают входные сигналы и выдают результат — выходной сигнал. Между нейронами существуют различные взаимосвязи, сами нейроны могут объединяться в слои. В нейронах могут использоваться функции распределения или веса, присваиваемые входным значениям (функции распределения могут изменяться и применяться только к определенным множествам значений). В классическом программировании конкретный алгоритм по очереди выполняет определенные действия и вычисляет результат на основе входных значений. Нейронная же сеть может «обучаться» автоматически на основе больших объемов данных, а затем обрабатывать новые входные данные на основе изученных. Заметим, что в этой теории не только проводится аналогия с нейронами человеческого мозга, но также используются те же понятия, что и при обучении людей: «обучение», «гибкость», «терпимость», «самоорганизация».

Анализ медицинских изображений, распознавание рукописных текстов и голоса, управление работой электростанций, принятие инвестиционных решений, интеллектуальный анализ крупных баз данных, контроль работы промышленных предприятий — теория нейронных сетей находит интересное применение в этих и многих других областях. Очевидно, что нейронные сети можно объединять с экспертными системами, генетическими алгоритмами и другими методами, например нечеткой логикой, в которой значения истинности лежат на интервале между 0 и 1.

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

Классификацию нейронных сетей можно выполнить по аналогии с графами, разделив нейронные сети на сети прямого распространения (такие сети не содержат циклов и связей между нейронами одного слоя) и рекуррентные, в которых существует минимум один цикл. Нейронные сети также можно классифицировать по типу «обучения» или ввести другие критерии, например тип обрабатываемой ими информации (изображение, речь и так далее).

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

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