Техника - молодёжи 1963-09, страница 38

когда стрелки кнопок дают сочетания ООО; 010; 011; 111; 101; 100, схема пропускает ток.

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

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

В 1956—1957 годах была создана геометрическая теория транспортных сетей. Она дала простой алгоритм¹ для нахождения наибольшего потока по сети с заданными пропускными способностями звеньев. Метод настолько эффективен, что в случае сетей с сотнями вершин и тысячами дуг задача легко решается «вручную», без помощи быстродействующих

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

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

АЗБУКА СЧЕТНОЙ ТЕХНИКИ

(Продолжение. Начало в № 1—8)

П рограммирование состоит из трех этапов: 1) определение ■ * порядка, в котором машина должна выполнять вычислительный процесс; 2) размещение в ячейках памяти исходных данных, команд, промежуточных и окончательных результатов; 3) составление самих команд. Второй и третий этапы тесно связаны между собой. Не зная номеров ячеек, хранящих исходные данные, не решив вопроса, в какие ячейки нужно помещать результаты, нельзя составлять команды. С другой стороны, не зная заранее количества команд программы, трудно решить вопрос о размещении данных в ячейках памяти.

Пример. Составить программу для решения системы уравнений (рис. 36). Нетрудно получить формулы решения (рис. 37). Порядок, в котором должен осуществляться вычислительный процесс, очевиден. Исходные данные задачи (числа А, В, С, D, Е, F) разместим в ячейки с номерами Ь+1; Ь+2 и т. д. (рис. 38). Команды будут «расквартированы» в ячейках а+1; а+2 и т. д. Рабочим ячейкам назначим номера с+1; с+2 и т. д. Для результатов отведем ячейки d+1; d+2. Теперь перейдем к составлению команд.

ф Ax-j-By = C,

| Dx + Ev = F §

©

CE — BF

AF — CD AE — BD '

@ Й+1)Л, b + 2)B, 6 + 3)C, b + A)D, b-\-b)E, 6 + 6)F.

Первая команда: перемножить (операцию умножения обозначим шифром 05) числа А и Е, произведение записать в рабочую ячейку с+1:

а+1) Ь+1 Ь+5 с+1 05 Вторая команда: перемножить числа В и D, произведение записать в ячейку с+2:

а+2) Ь+2 Ь+4 с+2 05 Третья команда: от числа АЕ=(с+1) отнять число BD=(c+2); разность записать в ячейку с+1: а+3) с+1 с+2 с+1 03

©а + 0) а+1)

I а + 2) I а + 3) I « + 4) | "+ 5) | я + 6)

| в+ 10) I а+П)

I а+ 13)

I а+14)

I а+15) | о+ 16) ^ а +17)

ь + \ 6 + 1

Ь + 2 с + 1

с + 1 £ + 3 Ь-г 2 с + 2 с+1 £+1 6+3 с 4-2 с + 1 аГ+1 d+1 0000

0005

6 + 5 6 + 4 с + 2 0000 6 + 5 6 + 6 с +3 с + 2 6 + 6 6 + 4 с + 3 с + 2 0001 0001 0000

6 + 1

с + 1 с+2 с + 1 с + 1 с +2 с +3 с+2 d + 1 С-+2

с +3 с+2 d + 2 d+1 0000 0000

72 05 05 03 62 05 05 03 05 05 05 03 05 70 44 40

Последняя команда — прекратить операции: а+17) 0000 0000 0000 40 Получаем программу в буквенном виде (рис. 39).

© 0020)

■а 0021)

I 0022)

I 0023) I 0024) I 0025) | 0026) I 0027) I 0030) I 0031) I 0032) I 0033) I 0034) I 0035) I 0036) ^ 0037)

0052) } °^{тветные ячейки}

0040) А

0041) В

0042) С

0043) D

0044) £

0045) F

0046)

0047) 0050)

Исходные данные

Рабочие ячейки

0052) } °^{тветные ячейки}

Теперь остается заменить буквы конкретными числами (скажем, а=20; Ь=37; с = 45; d=50) и получить программу в ее окончательном виде (рис. 40).

Чтобы выполнить программу, ее можно ввести в память машины вручную, набирая на пульте управления (рис. 41) каждую команду и вводя в соответствующую ячейку памяти.

ф Можно вводить программу в машину с помощью

34