WWW.LIB.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Электронные материалы
 

«ТРУДЫ МАТЕМАТИЧЕСКОГО И Н С Т И Т У Т А ИМЕНИ В. А. СТЕКЛОВА 1951 г., том XXXVIII А. А. МАРКОВ ТЕОРИЯ АЛГОРИФМОВ 1. В математике принято понимать под «алгорифмом» вычислитель­ ный ...»

ТРУДЫ

МАТЕМАТИЧЕСКОГО И Н С Т И Т У Т А ИМЕНИ В. А. СТЕКЛОВА

1951 г., том XXXVIII

А. А. МАРКОВ

ТЕОРИЯ АЛГОРИФМОВ

1. В математике принято понимать под «алгорифмом» вычислитель­

ный процесс, совершаемый согласно точному предписанию и ведущий

от могущих варьировать исходных данных к искомому результату.

Типичным примером алгорифма является эвклидов алгорифм разы­

скания общего наибольшего делителя двух натуральных чисел. Роль исходных данных играет здесь пара натуральных чисел; предписание состоит в последовательном построении убывающего ряда чисел, из которых первое является большим из двух данных, второе—меньшим, третье получается, как остаток от деления первого на второе, четвер­ тое— как остаток от деления второго на третье, и т. д., до тех пор пока не будет совершено деление без остатка; тогда делитель в этом делении и будет искомым результатом алгорифма — общим наибольшим делителем двух данных натуральных чисел.

Мы отмечаем здесь три черты, которые считаем характерными для алгорифмов:

а) Наличие точного предписания, не оставляющего места произволу и в известном смысле общепонятного — дете рмини ров а нност ъ алго­ рифма.

б) Возможность исходить из могущих в известных пределах варьи­ ровать исходных данных — массовость алгорифма.

в) Направленность алгорифма на получение некоторого искомого результата, в конце концов и получаемого при надлежащих исходных данных,— результативность алгорифма.



2. Сделанное только что описание алгорифмов не претендует на математическую точность. До последнего времени математики, однако, довольствовались тем несколько расплывчатым понятием, которое соот­ ветствует этому описанию. Это было допустимо пока термин «алгорифм»

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

i Теория алгорифмов m 7 1Д 13

3. В последнее время рядом авторов | ~, ] были разработа­ ны теории, если и не занимающиеся непосредственно уточнением поня­ тия алгорифма, то во всяком случае естественно ведущие к такому уточнению.

Это дало возможность установить ряд важных отрицательных резуль­ татов—теорем невозможности алгорифмов. Сюда относится прежде всего теорема Черча [ ] о неразрешимости общей «проблемы разреши­ мости» исчисления предикатов. В качестве более конкретных резуль­ татов можно указать доказательство неразрешимости ряда проблем общей теории ассоциативных систем. f » ' ] и теории целочис­ ленных матриц [ ' ].

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

5. Элементарными знаками мы называем знаки, которые не рассмат­ риваем как имеющие части. Объем этого понятия зависит от принятых соглашений. Например, знак «a'» можно рассматривать и как элемен­ тарный и как состоящий из двух частей: «а» и «'», смотря по принятым на этот счет соглашениям.

6. При одновременном рассмотрении каких-нибудь двух элементарных знаков мы констатируем, что они одинаковы или что они различны.

Эти понятия также условны.

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

одинаковости.

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

8. Списки элешнтарных знаков называются алфавитами. Два алфа­ вита мы считаем равными, если всякий элементарный знак, входящий в первый алфавит, одинаков с некоторым элементарным знаком, вхо­ дящим во второй алфавит, и наоборот. Алфавиты, рассматриваемые с точностью до равенства, мы называем абстрактными алфавитами^ Абстрактный алфавит определяется теми абстрактными элементар­ ными знаками, представители которых входят в представителя абстракт* ного алфавита. Абстрактный алфавит можно поэтому рассматривать как конечное множество абстрактных элементарных знаков. Абстрактные 12 Труды Матем. ин-та, XXXVIII А. А. Марков элементарные знаки, принадлежащие в этом смысле данному абстракт­ ному алфавиту, мы называем буквами этого абстрактного алфавита.

В дальнейшем мы, говоря об «алфавитах», будем обычно подразу­ мевать «абстрактные алфавиты».

9. Ряды элементарных знаков мы называем словами. Если элемен­ тарные знаки, составляющие слово Р, суть представители букв алфавита то мы говорим, что Р есть слово в этом алфавите.

А, К написанию слов мы предъявляем ряд требований отчетливости.

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

Должны быть отчетливо указаны начало и конец слова.

Наконец, очень важное требование состоит в единственности пред­ ставления слова в виде ряда рассматриваемых элементарных знаков — в невозможности «разночтений». Чтобы обеспечить соблюдение этого тре­ бования, проще всего наложить на рассматриваемые алфавиты надле­ жащее ограничение. Достаточно, например, потребовать, чтобы элемен­ тарные знаки, представляющие буквы алфавита, не получались друг из друга путем дописывания чего-нибудь справа. Это ограничение мы и наложим.

10. Мы говорим о словах Р и Q, что они равны, если они состоят из одинаковых элементарных знаков, одинаково расположенных. Для распознавания равенства слов имеется общий эффективный метод — одновременный просмотр слов слева направо знак за знаком.

При рассмотрении слов мы также применяем абстракцию отожде­ ствления, состоящую в данном случае в том, что о двух равных словах % мы говорим как об одном и том же слове. Это ведет к построению понятия абстрактного слова, слова, рассматриваемого с точностью до равенства. Всякому абстрактному слову соответствует много конкретных слов, о которых мы говорим, что они представляют это абстрактное слово. Два конкретных слова тогда и только тогда равны, когда они представляют одно и то же абстрактное слово. Абстрактное слово можно считать построенным из абстрактных элементарных знаков — из букв этого слова.

11. Другой абстракцией, также все время применяемой в дальней­ шем, является абстракция потенциальной осуществимости, состоящая в том, что мы отвлекаемся от реальных границ наших конструктивных возможностей и начинаем рассуждать о сколь угодно длинных абстракт­ ных словах как об осуществимых. Их осуществимость потенциальная:.

их представители были бы практически осуществимы, если бы в нашем распоряжении было достаточно времени, места и материалов. Принимая эту абстракцию, мы будем в дальнейшем понимать под «словом» абстракт-, ное потенциально осуществимое слово. •

i Теория алгорифмов 179

12. Приписывая справа какого-нибудь представителя слова Q к какому-нибудь представителю слова Р, мы получим представителя неко­ торого нового слова. Оно не зависит от выбора этих представителей, определяясь вполне самими словами Р и Q. Мы называем его соеди­ нением слов Р и Q и обозначаем символом PQ. Аналогичным образом мы определяем соединение PQR трех слов P, Q и R и т. д.

Абстракция потенциальной осуществимости дает возможность утвер­ ждать существование соединения любых двух слов.

13. Удобно ввести «пустое слово» в рассматриваемом алфавите, слово, совсем не имеющее букв. Это может быть сделано так. Пусть алфавит А таков, что элементарный знак Д не представляет его букву.

Условимся называть соответствующий абстрактный элементарный знав!





пустым словом в алфавите А.

Расширяя понятие слова в алфавите А, мы будем теперь называть словом, во-первых, всякое слово в А в прежнем смысле, во-вторых, пу­ стое слово в А. На слова в А в новом смысле мы распространим опре­ деление соединения, положив РА^Р; ЛР = Р для всякого слова P s i *.

14. Мы говорим о слове Р, что оно начинается словом Q, если существует такое слово S, что P = QS;

–  –  –

вхождения Q в Р.

Нетрудно видеть, что при наличии вхождений Q в Р среди них имеется одно и только одно, предшествующее всем остальным. Мы назы­ ваем его первым вхождением Qв Р.

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

Пустое слово входит во всякое слово и первым вхождением пустого слова в слово Р является вхождение **Р.

15. Если T = R * Q * S — вхождение Q в P, U — какое-нибудь слово, то построение слова RUS мы будем называть подстановкой слова U вместо Q, само это слово — результатом этой подстановки.

Слово ЛР есть результат подстановки слова Л вместо первого вхо­ ждения пустого слова в слово Р.

При заданных Л m В подстановка слова В вместо какого-нибудь вхождения слова Л в произвольное слово Р есть «локальная» операция над Р в том смысле, что она затрагивает данного вида участок пре­ образуемого слова.

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

Нас интересует то слово, на котором обрывается этот ряд — результат процесса.

Соответственно этому условимся понимать под алгорифмом в алфа­ вите А общепонятное предписание, определяющее потенциально осущест­ вимый процесс над абстрактными словами в А, исходящий от любого слова в А Будем говорить, что алгорифм применим к слову Р, если, исходя из этого слова и применяя алгорифм, мы получим в конце кон

<

i Теория алгорифмов

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

Слово, в которое алгорифм 21 перерабатывает Р, будем обозначать символом 21 (Р).

Условимся далее понимать под алгорифмом над алфавитом А алго­ рифм в каком-нибудь алфавите, содержащем А. Если % и 25 — алгорифмы над А, то будем говорить, что они эквивалентны относительно А, если всякий раз, когда Ш перерабатывает какое-нибудь слово Р в А в другое слово также в А, 25 перерабатывает Р в то же самое слово и наоборот.

Будем говорить, что эти алгорифмы вполне эквивалентны относительно А, если всякий раз, когда 21 перерабатывает какое-нибудь слово ? в i, 25 перерабатывает Р в то же самое слово и наоборот.

17. Введенное только что понятие алгорифма в данном алфавите не является достаточно четким, чтобы определять объекты математической теории. Оно подлежит уточнению, к которому мы сейчас и перейдем.

Мы потребуем прежде всего в обеспечение общепонятности предписа­ ния, чтобы оно обусловливало разбиение процесса применения алгорифма на элементарные шаги локального характера — на подстановки данных слов вместо вхождений других данных слов. Должен при этом задаваться перечень типов таких шагов, причем каждый тип будет характеризо­ ваться парой слов в рассматриваемом алфавите: тем словом, вместо вхождения которого совершается подстановка, и тем словом, которое подставляется. Считая, что знак стрелки не есть буква нашего алфавита, условимся изображать формулой вида (2) Л-В подстановку слова В вместо вхождения слова Л. Существенная состав­ ная часть алгорифма будет тогда состоять в некотором перечне таких формул.

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

Далее, если мы даже знаем, что в данном случае надо применить под­ становку, выражаемую данной формулой (2), то ведь ее левая часть Л может несколько раз входить в слово, и, значит, должно быть указано, вместо которого ее вхождения следует подставлять правую часть В.

Возможны различные варианты таких указаний. Мы остановимся на следующем.

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

182 А. А. Марков Процесс последовательных подстановок, выполняемый на основании этого предписания, выглядит так. Будем исходить из какого-нибудь слова Q. В данном перечне формул (2) ищется первая из тех, левые части которых входят в Q. Ищется первое вхождение ее левой части в Q и, вместо этого вхождения, подставляется правая часть формулы, что дает новое слово Q. С ним делается то же, что делалось с Q x и т. д.

Процесс этот может оборваться на некотором слове Q, таком, что ни n одна из рассматриваемых операций не будет к нему применима, т. е.

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

Перечень так записанных формул мы будем называть схемой рас­ сматриваемого алгорифма. Сами алгорифмы описанного типа будем называть нормальными алгорифмами. Всякий нормальный алгорифм вполне определяется указанием алфавита, в котором он действует, и схемы.

Определение нормального алгорифма является достаточно четким.

Нормальные алгорифмы могут быть поэтому объектами математической теории.

18. Приведем два примера нормальных алгорифмов.

Пусть Шх — нормальный алгорифм в алфавите А = {а, Ь) со схемой

–  –  –

Нетрудно видеть, что ЧЦ(Р) = аР для всякого слова Р в А. Если бы мы здесь убрали точку, то получился бы нормальный алгорифм, не при­ менимый ни к какому слову.

Пусть 2i — нормальный алгорифм в алфавите {а, 6, с, cl, е) со схемой

–  –  –

в первую формулу одну из букв a, b вместо а и одну из этих букв вместо (3. Эти подстановки следует сделать всеми возможными способами, что даст четыре формулы. Их мы пишем в определенном порядке (без­ различном для дальнейшего). Далее пишутся две формулы, получаемые из второй формулы сокращенной схемы подстановкой а и b вместо а.

Всего схема содержит 10 формул подстановки и допускает 48 вариантов, Мы останавливаемся на одном из них.

В применении к слову Р = а. • • • а# в алфавите А (оц = а или Ь) г 0

–  –  –

т. е. % удваивает эти слова.

19. Теперь естественно спросить, в какой мере точное понятие нор­ мального алгорифма соответствует ранее формулированному общему и не совсем точному понятию алгорифма в данном алфавите. В качестве ответа на этот вопрос может быть выдвинут следующий п р и н ц и п н о р м а л и з а ц и и а л г о р и ф м о в : всякий алгорифм над алфавитом А эквивалентен относительно А некоторому нормальному алгорифму над А.

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

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

Другой важный довод в пользу принципа нормализации состоит в том, что различные комбинации нормальных алгорифмов дают алгоm A. A. Марков

–  –  –

х Принимая во внимание, что [Р = Р для всякого слова Р в А, полу­ чаем отсюда следующий результат.

Всякий нормальный алгорифм над алфавитом А эквивалентен отно­ сительно А некоторому нормальному алгорифму в алфавите A U {a, b где а и — элементарные знаки, не принадлежащие А.

2 2. Будем рассматривать нормальные алгорифмы в алфавите А.

До сих пор мы применяли для их задания «схемы» — столбцы формул подстановок. Теперь будет целесообразно перейти к другому способу задания нормальных алгорифмов. Введем для этого новые элементарны знаки а, и Y отличные друг от друга, от букв алфавита А и от зна­, ков «-» и «•». Условимся задавать всякий нормальный алгорифм 21 в алфавите А словом, получаемым следующим образом. Выписываются друг за другом в порядке очередности формул подстановок алгорифма 21 слова, получаемые из этих формул заменой стрелки знаком а, точки знаком и присоединением справа знака j. Так получаемое слово бу­ дем называть изображением алгорифма 2( и обозначать символом 21 • Изображение нормального алгорифма 2t в алфавите А есть слово в ал­ фавите Б = A (J {а,, 7}. Оно, как нетрудно видеть, определяет этот алгорифм. Следующая теорема может служить основой для многих доказательств невозможности алгорифмов.

Т е о р е м а об у н и в е р с а л ь н о м а л г о р и ф м е. Пусть о — знак, не являющийся буквой алфавита Б (см. выше). Может быть построен такой нормальный алгорифм 21 над Б (J {8}, что 21 (ШЩ ж 21 (Р) для слов Р в А и нормальных алгорифмов 21 в А.

А. А. Марков Для применения этой теоремы к доказательствам невозможности целесообразно перейти к заданию нормальных алгорифмов в А словами в алфавите А = {а, Ъ].

–  –  –

где n — число букв алфавита Б. Избирается определенное такое сопо­ ставление. Это дает возможность «переводить» слова в алфавите Б в алфавит А. Перевод слова Р в Б получается просто путем замены всякой буквы этого слова соответствующим словом из ряда (3). При­ меняя эту операцию к изображению % нормального алгорифма 21 в А, получаем слово в алфавите А, которое будем называть записью этого алгорифма. Запись алгорифма 21 будем обозначать символом 2Г.

Из теоремы об универсальном алгорифме легко следует существова­ ние такого нормального алгорифма $ над алфавитом A U {а, Ь, о}, что

–  –  –

Условимся говорить о нормальном алгорифме в А что он самопри­19 меним, если он применим к своей собственной записи.

Самоприменимые алгорифмы существуют. Например, нормальный алгорифм в А со схемой х

–  –  –

Допустим, в самом деле, что SQ является таким алгорифмом. Согласно теореме о переводе алгорифма, может быть построен нормальный алго­ рифм ff в алфавите А так же как и применимый к тем и только

–  –  –

несамоприменимых алгорифмов. ff имеет запись ff*, являющуюся словом в А. Исследуем, может ли ff быть самоприменимым, т. е. примени­ мым к ff*.

Если ff применим к ff*, то ff* есть запись не самоприменимого алго­ рифма, и потому ff несамоприменим, т. е. не применим к ff*. Таким образом, ff несамоприменим. Отсюда следует, однако, чтоff*есть запись несамоприменимого алгорифма, в силу чего ff применим к ff*, т. е.

самоприменим. Сделанное предположение о существовании алгорифма !Q с указанными выше свойствами ведет, таким образом, к противоречию.

Такой алгорифм, следовательно, невозможен, что и требовалось доказать.

Условимся теперь говорить о нормальном алгорифме над А, что он 0 распознает несамоприменимостъ {самоприменимость), если он применим к записи всякого нормального алгорифма в А и перерабатывает 21* 1 в пустое слово тогда и только тогда, когда алгорифм 21 несамоприменим (самоприменим).

Построение нормального алгорифма над А, распознающего несамо­ 0 применимостъ, очевидно, дало бы нам общий эффективный метод, посредством которого можно было бы по данной записи, т. е. в конеч­ ном счете по данной схеме нормального алгорифма в A узнавать, LF

–  –  –

нимость, невозможен.

В самом деле, допустим, что SQ есть такой алгорифм в алфавите А, содержащем А. Построим нормальный алгорифм 2 в А с сокращенно записанной схемой где I означает всякую букву алфавита А. Этот алгорифм, очевидно, применим к пустому слову и только к нему.

Применяя теорему композиции к алгорифмам § и, строим нормаль­ ный алгорифм ff над А такой, что 0

–  –  –

несамоприменим. Такой алгорифм ff, однако, невозможен согласно пре­ дыдущей теореме. Следовательно, невозможен и алгорифм @, распознаю­ щий несамоприменимостъ, что и требовалось доказать.

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

188 А. А. Марков Заметим теперь, что, согласно установленному выше условному равенству (Ш*еР) ж 21 (Р), нормальный алгорифм 21 в А тогда и только г тогда самоприменим, когда алгорифм g применим к слову 2i*e2l*. При­ нимая во внимание, что нормальный алгорифм над А, перерабатываю­ 2 щий 21* в 2Ре2Г, легко может быть построен, заключаем на основании предыдущего, что невозможен нормальный алгорифм, распознающий неприменимость (применимость) алгорифма %, т. е. нормальный алго­ рифм над А, применимый ко всякому слову в А и перерабатывающий

–  –  –

перерабатывающим всякое слово в в пустое слово и применяя теорему композиции к $ и g, а затем опять делая «перевод» в А, получаем, наконец, следующий результат:

Сугцествует такой нормальный алгорифм $ i в А, что невозможен

–  –  –

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

–  –  –

1. М а р к о в А. А. Невозможность некоторых алгорифмов в теории ассоциативных систем. «Докл. АН СССР», 1947, т. 55, № 7, стр. 587—590.

2. М а р к о в А. А. Невозможность некоторых алгорифмов в теории ассоциативных систем II. «Докл. АН СССР», 1947, т. 58, M 3, стр. 353—356.

3. М а р к о в А. А. О некоторых неразрешимых проблемах, касающихся матриц.

«Докл. АН СССР», 1947, т. 57, № 6, стр. 539—542.

4. М а р к о в А. А. Невозможность некоторых алгорифмов в теории ассоциативных систем. «Докл. АН СССР», 1951, т. 77, № 1, стр. 19—20.

5. М а р к о в А. А. Невозможность алгорифмов, распознающих некоторые свойства ассоциативных систем. «Докл.|АН СССР», 1951, т. 7, № 6, стр. 953—956.

6. М а р к о в А. А. Об одной неразрешимой проблеме, касающейся матриц. «Докл.

АН СССР», 1951, т. 78, № 6, стр. 1089—1092.

Теория алгорифмов

7. K l e e n e S. G. General recursive functions of natural numbers. «Math. Ann.», 1936, v. 112, p. 727-742.

8. K l e e n e S. C. Recursive predicates and quantifiers. «Trans. Amer. Math. Soc», 1943, v. 53, p. 4 1 - 7 3.

9. C h u r c h A. The calculi of X-conversion. «Ann. Math. Studies», 1941, № 6, Princeton Univ. Press.

10. C h u r c h A. An unsolvable problem of elementary number theory. «Amer.

J. Math.», 1936, v. 58, p. 345—363.

11. C h u r c h A. A set of postulates for the foundation of logic. «Ann. Math.», 1932, (2), 33, p. 346—366.

12. C h u r c h A. A note on the Entscheidungsproblem. «J. Symb. Logic», 1936, v. 1, p. 40—41; 101—102.

13. T u r i n g A. M. On computable numbers with an application to the Entscheidungs­ problem. «Proc. London Math. Soc», 1937, (2), v. 42, p. 230—265; (2), v. 43, p. 544.

14. P o s t E. L. Recursive unsolvability of a problem of Thue. «J. Symb. Logic»,

Похожие работы:

«ВЫРОЖДЕННОСТЬ В ЗАДАЧАХ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И. В. Агафонова В А. Даугавет ivagafonova@home.eltel.net vadaug@yandex.ru 11 декабря 2010 г. Рассматривается задача линейного программирования в канонической форме: (1) f (x) := c[N ] x[N ] min, x где = {x[N ] | A[M, N ] x[N ] = b[M ], x[N ] O}, M = {1, 2,..., m},...»

«Journal of Siberian Federal University. Engineering & Technologies 4 (2008 1) 377-386 ~~~ УДК 004.4:528.9 Формирование геоинформационного Интернет-портала для задач мониторинга состояния природной среды и ресурсов Алексей А. Кадочников, Владимир Г. Попов, Алексей А. Токарев, Олег Э. Якубайлик* Институт вычислите...»

«International Scientific Conference Proceedings, Volume 1 PIT 2015 “Advanced Information Technologies and Scientific Computing” Литература 1. Каханер Д., Моулер К., Нэш С. Численные методы и математическое обеспечение. Пер. с англ. – М.: Мир, 1998. – 575 с.2. Райс Дж. Матричные вычисления и математическое обеспечение....»

«М. И. ЖАЛДАК А. Н. КВИТКО ТЕОРИЯ ВЕРОЯТНОСТЕЙ С ЭЛЕМЕНТАМИ ИНФОРМАТИКИ ПРАКТИКУМ Под общ ей редакцией профессора М. И. ЯДРЕН КО Д оп ущ ено Министерством народного образования УССР в качестве учебного пособил д л я студентов физико-математических факульт...»

«Евгений Корнилов Санкт-Петербург "БХВ-Петербург" УДК 681.3.068 ББК 32.973 К67 Корнилов Е. Н. К67 Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. — 272 с.: ил. ISBN 5-94157-497-5 Рассмотрено программирование логических игр методом перебора на примере шахмат. Описываются стан...»

«Некоторые теоремы о распределении значений периодических дзета-функций Гурвица А. ЛАУРИНЧИКАС Вильнюсский университет (факультет математики и информатики), Литва e-mail: antanas.laurincikas@maf.vu.lt УДК 511.331 Ключевые слова: дзета-функция Гурвица, теоремы у...»

«TNC 620 Руководство пользователя Программирование DIN/ISO Версия ПО ЧПУ 817600-03 817601-03 817605-03 Русский (ru) 9/2015 Элементы управления ЧПУ Элементы управления ЧПУ Управление прогр...»

«1. Цели производственной практики Целями вычислительной практики являются: 1. Развитие профессиональных компетенций в области изучения и анализа систем в соответствии с требованиями ФГОС ВО по направлению подготовки "Информационные системы и технологии"2. Формирование у обуч...»










 
2017 www.lib.knigi-x.ru - «Бесплатная электронная библиотека - электронные материалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.