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

Поделись знанием:
Перейти к: навигация, поиск

Тео́рия алгори́тмов — наука, находящаяся на стыке математики и информатики, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п. Вместе с математической логикой теория алгоритмов образует теоретическую основу вычислительных наук.[1][2]





Возникновение теории алгоритмов

Развитие теории алгоритмов начинается с доказательства К. Гёделем теорем о неполноте формальных систем, включающих арифметику, первая из которых была доказана в 1931 году. Возникшее в связи с этими теоремами предположение о невозможности алгоритмического разрешения многих математических проблем (в частности, проблемы выводимости в исчислении предикатов) вызвало необходимость стандартизации понятия алгоритма. Первые стандартизованные варианты этого понятия были разработаны в 30-х годах XX века в работах А. Тьюринга, А. Чёрча и Э. Поста. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Чёрча оказались эквивалентными друг другу. Основываясь на работах Гёделя, С. Клини ввел понятие рекурсивной функции, также оказавшееся эквивалентным вышеперечисленным.

Одним из наиболее удачных стандартизованных вариантов алгоритма является введённое А. А. Марковым понятие нормального алгоритма. Оно было разработано десятью годами позже работ Тьюринга, Поста, Чёрча и Клини в связи с доказательством алгоритмической неразрешимости ряда алгебраических проблем.

Следует отметить также немалый вклад в теорию алгоритмов, сделанный Д. Кнутом, A. Ахо и Дж. Ульманом.

Одной из лучших работ на эту тему является книга «Алгоритмы: построение и анализ» Томаса Х. Кормена, Чарльза И. Лейзерсона, Рональда Л. Ривеста, Клиффорда Штайна.

Модели вычислений

  • Машина Тьюринга — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
  • Лямбда-исчисление — рассматривается пара: λ-выражение и его аргумент, — а вычислением считается применение, или апплицирование, первого члена пары ко второму. Это позволяет отделить функцию и то, к чему она применяется. В более общем случае вычислением считаются цепочки, начинающиеся с исходного λ-выражения, за которым следует конечная последовательность λ-выражений, каждое из которых получается из предыдущего применением β-редукции, то есть правила подстановки.
  • Комбинаторная логика — трактовка вычисления сходна с λ-исчислением, но имеются и важные отличия (например, комбинатор неподвижной точки Y имеет нормальную форму в комбинаторной логике, а в λ-исчислении — нет). Комбинаторная логика была первоначально разработана для изучения природы парадоксов и для построения концептуально ясных оснований математики, причем представление о переменной исключалось вовсе, что помогало прояснить роль и место переменных в математике.
  • Регистровые машины (англ.)
    • RAM-машина — абстрактная вычислительная машина, моделирующая компьютер с произвольным доступом к памяти. Именно эта модель вычислений наиболее часто используется при анализе алгоритмов.

Тезис Чёрча — Тьюринга и алгоритмически неразрешимые проблемы

Основные статьи: Тезис Чёрча — Тьюринга, Машина Тьюринга

Алан Тьюринг высказал предположение (известное как «тезис Чёрча — Тьюринга»), что любой алгоритм, — в интуитивном смысле слова, — может быть представлен эквивалентной машиной Тьюринга. Уточнение представления о вычислимости на основе понятия такой машины (и других эквивалентных ей понятий) открыло возможность строгого доказательства алгоритмической неразрешимости различных массовых проблем (проблем нахождения единого метода решения некоторого класса задач, условия которых могут варьироваться в известных пределах).

Простейший пример алгоритмически-неразрешимой массовой проблемы — проблема применимости алгоритма, проблема остановки, которая заключается в следующем: требуется найти общий метод, который позволял бы для произвольной машины Тьюринга (заданной посредством своей программы) и произвольного начального состояния ленты этой машины определить — завершится ли работа машины за конечное число шагов, или же будет продолжаться неограниченно долго?

В течение первого десятилетия истории теории алгоритмов, неразрешимые массовые проблемы были обнаружены лишь в ней самой (в том числе, описанная выше «проблема применимости») и в математической логике («проблема выводимости» в классическом исчислении предикатов). Поэтому считалось, что теория алгоритмов представляет собой «обочину» математики, не имеющую значения для таких её классических разделов, как «алгебра» или «анализ». Положение изменилось после того, как А. А. Марков и Э. Л. Пост в 1947 году установили алгоритмическую неразрешимость известной в алгебре проблемы равенства для конечнопорождённых и конечноопределённых полугрупп (так называемая «проблема Туэ»). Впоследствии, была установлена алгоритмическая неразрешимость и многих других «чисто математических» массовых проблем. Одним из наиболее известных результатов в этой области является доказанная Ю. В. Матиясевичем алгоритмическая неразрешимость десятой проблемы Гильберта.

Современное состояние теории алгоритмов

В настоящее время — теория алгоритмов развивается, главным образом, по трём направлениям:

Анализ трудоёмкости алгоритмов

Основная статья: Теория сложности вычислений

Цель анализа — нахождение оптимального алгоритма. Критерий — трудоёмкость (количество необходимых алгоритму элементарных операций). Функция трудоёмкости — соотношение трудоёмкости с входными данными.

На трудоёмкость могут в разной мере влиять свойства входных данных:

  • Объём;
  • Значения;
  • Порядок поступления.

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

Основной оценкой функции сложности алгоритма <math>f(n)</math> (где n — величина объёма данных, «длина входа») является <math>\boldsymbol{\Theta}</math>:

<math>f(n) = \boldsymbol{\Theta}(g(n))</math>

если при g > 0 при n > 0 существуют положительные с1, с2, n0, такие, что:

<math>c_1 \cdot g(n)\le \; f(n) \le \; c_2 \cdot g(n)</math>

при n > n0; иначе говоря, можно найти такие с1 и с2, что, — при достаточно больших n, — <math>f(n)</math> будет заключена между

<math>c_1 \cdot \;g(n)</math> и <math>c_2 \cdot \;g(n)</math>.

В таком случае говорят ещё, что функция <math>g(n)</math> является асимптотически точной оценкой функции <math>f(n)</math>, так как по определению функция <math>f(n)</math> не отличается от функции <math>g(n)</math> с точностью до постоянного множителя (см. асимптотическое равенство). Например, для метода сортировки «heapsort», оценка трудоёмкости составляет:

<math>f(n) = \boldsymbol{\Theta}(n \log n)</math>, то есть <math>g(n) = n \log n</math>.

Из <math>f(n) = \boldsymbol{\Theta}(g(n))</math> следует <math>g(n) = \boldsymbol{\Theta}(f(n))</math>.

Важно понимать, что <math>\boldsymbol{\Theta}(g(n))</math> представляет собой не функцию, а множество функций, описывающих рост <math>f(n)</math> с точностью до постоянного множителя.

<math>\boldsymbol{\Theta}</math> даёт одновременно верхнюю и нижнюю оценки роста функции. Часто бывает необходимо рассматривать эти оценки по отдельности. Оценка <math>\boldsymbol{O}</math> представляет собой верхнюю асимптотическую оценку трудоёмкости алгоритма. Мы говорим, что <math>f(n)=\boldsymbol{O}(g(n))</math>, если

<math>\exists \; c > 0, n_0 > 0 : 0 \le \; f(n) \le \; c g(n), \forall \; n > n_0 </math>.

Иначе говоря, запись <math>f(n) = \boldsymbol{O}(g(n))</math> означает, что <math>f(n)</math> принадлежит классу функций, которые растут не быстрее, чем функция <math>g(n)</math> с точностью до постоянного множителя.

Оценка <math>\boldsymbol{\Omega}</math> задает нижнюю асимптотическую оценку роста функции <math>f(n)</math> и определяет класс функций, которые растут не медленнее, чем <math>g(n)</math> с точностью до постоянного множителя. <math>f(n)=\boldsymbol{\Omega}(g(n))</math>, если

<math> \exists \; c > 0, n_0 > 0 : 0 \le \; c \, g(n) \le \; f(n), \forall \; n > n_0 </math>.

Например, запись <math>f(n)=\boldsymbol{\Omega} (n \, \log n) </math> обозначает класс функций, которые растут не медленнее, чем <math>g(n) = n \, \log n</math>; в этот класс попадают все полиномы со степенью большей единицы, равно как и все степенные функции с основанием большим единицы.

Равенство <math>f(n) = \boldsymbol{\Theta}(g(n))</math> выполняется тогда и только тогда, когда <math>f(n)=\boldsymbol{O}(g(n))</math> и <math>f(n)=\boldsymbol{\Omega}(g(n))</math>.

Асимптотический анализ алгоритмов имеет не только практическое, но и теоретическое значение. Так, например, доказано, что все алгоритмы сортировки, основанные на попарном сравнении элементов, отсортируют n элементов за время, не меньшее <math>\boldsymbol{\Omega}(n \, \log n)</math>.

Важную роль в развитии асимптотического анализа алгоритмов сыграли A. Ахо, Дж. Ульман, Дж. Хопкрофт.

Классы сложности

Основная статья: Класс сложности

В рамках классической теории, осуществляется классификация задач по их сложности (P-сложные, NP-сложные, экспоненциально сложные и другие):

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

Класс «P» содержится в «NP». Классическим примером NP-задачи является «Задача о коммивояжёре».

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

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

Математические приложения теории алгоритмов

  1. Исследование массовых проблем;
  2. Приложения к основаниям математики: конструктивная семантика;
  3. Приложения к математической логике: анализ формализованных языков логики и арифметики;
  4. Вычислимый анализ;
  5. Нумерованные структуры;
  6. Приложения к теории вероятностей: определения случайной последовательности;
  7. Приложения к теории информации: алгоритмический подход к понятию количества информации;
  8. Оценки сложностей решения отдельных задач;
  9. Влияние теории алгоритмов на алгоритмическую практику.[3]

См. также

Напишите отзыв о статье "Теория алгоритмов"

Литература

  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: Вильямс, 2006. — С. 1296. — ISBN 0-07-013151-1.
  • Дональд Кнут. Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: Вильямс, 2006. — С. 720. — ISBN 0-201-89683-4.
  • Колмогоров А. Н. Теория информации и теория алгоритмов. — М.: Наука, 1987. — 304 с.
  • Марков А. А., Нагорный Н. М. Теория алгорифмов. — 2-е изд.. — М.: ФАЗИС, 1996.

Ссылки

  • [th-algoritmov.narod.ru/ Теория алгоритмов]
  • [lib.custis.ru/Категория:Алгоритмы Миниэнциклопедия по теории сложности и комбинаторным алгоритмам]
  • [discopal.ispras.ru/ru.lectures.htm Лекции по теории сложности и комбинаторным алгоритмам]

Примечания

  1. ↑ Семёнов А. Л., Успенский В. А. Математическая логика в вычислительных науках и вычислительной практике. // Вестник Академии наук СССР, № 7, с. 93 — 103
  2. ↑ Успенский В. А., Семёнов А. Л. Решимые и нерешимые алгоритмические проблемы. // Квант, 1985, № 7, с. 9 — 15
  3. ↑ В. А. Успенский, А. Л. Семёнов Теория алгоритмов: основные открытия и приложения, М., Наука, 1987, 288 c.

Отрывок, характеризующий Теория алгоритмов


Следующий после театра день Ростовы никуда не ездили и никто не приезжал к ним. Марья Дмитриевна о чем то, скрывая от Наташи, переговаривалась с ее отцом. Наташа догадывалась, что они говорили о старом князе и что то придумывали, и ее беспокоило и оскорбляло это. Она всякую минуту ждала князя Андрея, и два раза в этот день посылала дворника на Вздвиженку узнавать, не приехал ли он. Он не приезжал. Ей было теперь тяжеле, чем первые дни своего приезда. К нетерпению и грусти ее о нем присоединились неприятное воспоминание о свидании с княжной Марьей и с старым князем, и страх и беспокойство, которым она не знала причины. Ей всё казалось, что или он никогда не приедет, или что прежде, чем он приедет, с ней случится что нибудь. Она не могла, как прежде, спокойно и продолжительно, одна сама с собой думать о нем. Как только она начинала думать о нем, к воспоминанию о нем присоединялось воспоминание о старом князе, о княжне Марье и о последнем спектакле, и о Курагине. Ей опять представлялся вопрос, не виновата ли она, не нарушена ли уже ее верность князю Андрею, и опять она заставала себя до малейших подробностей воспоминающею каждое слово, каждый жест, каждый оттенок игры выражения на лице этого человека, умевшего возбудить в ней непонятное для нее и страшное чувство. На взгляд домашних, Наташа казалась оживленнее обыкновенного, но она далеко была не так спокойна и счастлива, как была прежде.
В воскресение утром Марья Дмитриевна пригласила своих гостей к обедни в свой приход Успенья на Могильцах.
– Я этих модных церквей не люблю, – говорила она, видимо гордясь своим свободомыслием. – Везде Бог один. Поп у нас прекрасный, служит прилично, так это благородно, и дьякон тоже. Разве от этого святость какая, что концерты на клиросе поют? Не люблю, одно баловство!
Марья Дмитриевна любила воскресные дни и умела праздновать их. Дом ее бывал весь вымыт и вычищен в субботу; люди и она не работали, все были празднично разряжены, и все бывали у обедни. К господскому обеду прибавлялись кушанья, и людям давалась водка и жареный гусь или поросенок. Но ни на чем во всем доме так не бывал заметен праздник, как на широком, строгом лице Марьи Дмитриевны, в этот день принимавшем неизменяемое выражение торжественности.
Когда напились кофе после обедни, в гостиной с снятыми чехлами, Марье Дмитриевне доложили, что карета готова, и она с строгим видом, одетая в парадную шаль, в которой она делала визиты, поднялась и объявила, что едет к князю Николаю Андреевичу Болконскому, чтобы объясниться с ним насчет Наташи.
После отъезда Марьи Дмитриевны, к Ростовым приехала модистка от мадам Шальме, и Наташа, затворив дверь в соседней с гостиной комнате, очень довольная развлечением, занялась примериваньем новых платьев. В то время как она, надев сметанный на живую нитку еще без рукавов лиф и загибая голову, гляделась в зеркало, как сидит спинка, она услыхала в гостиной оживленные звуки голоса отца и другого, женского голоса, который заставил ее покраснеть. Это был голос Элен. Не успела Наташа снять примериваемый лиф, как дверь отворилась и в комнату вошла графиня Безухая, сияющая добродушной и ласковой улыбкой, в темнолиловом, с высоким воротом, бархатном платье.
– Ah, ma delicieuse! [О, моя прелестная!] – сказала она красневшей Наташе. – Charmante! [Очаровательна!] Нет, это ни на что не похоже, мой милый граф, – сказала она вошедшему за ней Илье Андреичу. – Как жить в Москве и никуда не ездить? Нет, я от вас не отстану! Нынче вечером у меня m lle Georges декламирует и соберутся кое кто; и если вы не привезете своих красавиц, которые лучше m lle Georges, то я вас знать не хочу. Мужа нет, он уехал в Тверь, а то бы я его за вами прислала. Непременно приезжайте, непременно, в девятом часу. – Она кивнула головой знакомой модистке, почтительно присевшей ей, и села на кресло подле зеркала, живописно раскинув складки своего бархатного платья. Она не переставала добродушно и весело болтать, беспрестанно восхищаясь красотой Наташи. Она рассмотрела ее платья и похвалила их, похвалилась и своим новым платьем en gaz metallique, [из газа цвета металла,] которое она получила из Парижа и советовала Наташе сделать такое же.
– Впрочем, вам все идет, моя прелестная, – говорила она.
С лица Наташи не сходила улыбка удовольствия. Она чувствовала себя счастливой и расцветающей под похвалами этой милой графини Безуховой, казавшейся ей прежде такой неприступной и важной дамой, и бывшей теперь такой доброй с нею. Наташе стало весело и она чувствовала себя почти влюбленной в эту такую красивую и такую добродушную женщину. Элен с своей стороны искренно восхищалась Наташей и желала повеселить ее. Анатоль просил ее свести его с Наташей, и для этого она приехала к Ростовым. Мысль свести брата с Наташей забавляла ее.
Несмотря на то, что прежде у нее была досада на Наташу за то, что она в Петербурге отбила у нее Бориса, она теперь и не думала об этом, и всей душой, по своему, желала добра Наташе. Уезжая от Ростовых, она отозвала в сторону свою protegee.
– Вчера брат обедал у меня – мы помирали со смеху – ничего не ест и вздыхает по вас, моя прелесть. Il est fou, mais fou amoureux de vous, ma chere. [Он сходит с ума, но сходит с ума от любви к вам, моя милая.]
Наташа багрово покраснела услыхав эти слова.
– Как краснеет, как краснеет, ma delicieuse! [моя прелесть!] – проговорила Элен. – Непременно приезжайте. Si vous aimez quelqu'un, ma delicieuse, ce n'est pas une raison pour se cloitrer. Si meme vous etes promise, je suis sure que votre рromis aurait desire que vous alliez dans le monde en son absence plutot que de deperir d'ennui. [Из того, что вы любите кого нибудь, моя прелестная, никак не следует жить монашенкой. Даже если вы невеста, я уверена, что ваш жених предпочел бы, чтобы вы в его отсутствии выезжали в свет, чем погибали со скуки.]
«Стало быть она знает, что я невеста, стало быть и oни с мужем, с Пьером, с этим справедливым Пьером, думала Наташа, говорили и смеялись про это. Стало быть это ничего». И опять под влиянием Элен то, что прежде представлялось страшным, показалось простым и естественным. «И она такая grande dame, [важная барыня,] такая милая и так видно всей душой любит меня, думала Наташа. И отчего не веселиться?» думала Наташа, удивленными, широко раскрытыми глазами глядя на Элен.
К обеду вернулась Марья Дмитриевна, молчаливая и серьезная, очевидно понесшая поражение у старого князя. Она была еще слишком взволнована от происшедшего столкновения, чтобы быть в силах спокойно рассказать дело. На вопрос графа она отвечала, что всё хорошо и что она завтра расскажет. Узнав о посещении графини Безуховой и приглашении на вечер, Марья Дмитриевна сказала:
– С Безуховой водиться я не люблю и не посоветую; ну, да уж если обещала, поезжай, рассеешься, – прибавила она, обращаясь к Наташе.


Граф Илья Андреич повез своих девиц к графине Безуховой. На вечере было довольно много народу. Но всё общество было почти незнакомо Наташе. Граф Илья Андреич с неудовольствием заметил, что всё это общество состояло преимущественно из мужчин и дам, известных вольностью обращения. M lle Georges, окруженная молодежью, стояла в углу гостиной. Было несколько французов и между ними Метивье, бывший, со времени приезда Элен, домашним человеком у нее. Граф Илья Андреич решился не садиться за карты, не отходить от дочерей и уехать как только кончится представление Georges.
Анатоль очевидно у двери ожидал входа Ростовых. Он, тотчас же поздоровавшись с графом, подошел к Наташе и пошел за ней. Как только Наташа его увидала, тоже как и в театре, чувство тщеславного удовольствия, что она нравится ему и страха от отсутствия нравственных преград между ею и им, охватило ее. Элен радостно приняла Наташу и громко восхищалась ее красотой и туалетом. Вскоре после их приезда, m lle Georges вышла из комнаты, чтобы одеться. В гостиной стали расстанавливать стулья и усаживаться. Анатоль подвинул Наташе стул и хотел сесть подле, но граф, не спускавший глаз с Наташи, сел подле нее. Анатоль сел сзади.
M lle Georges с оголенными, с ямочками, толстыми руками, в красной шали, надетой на одно плечо, вышла в оставленное для нее пустое пространство между кресел и остановилась в ненатуральной позе. Послышался восторженный шопот. M lle Georges строго и мрачно оглянула публику и начала говорить по французски какие то стихи, где речь шла о ее преступной любви к своему сыну. Она местами возвышала голос, местами шептала, торжественно поднимая голову, местами останавливалась и хрипела, выкатывая глаза.
– Adorable, divin, delicieux! [Восхитительно, божественно, чудесно!] – слышалось со всех сторон. Наташа смотрела на толстую Georges, но ничего не слышала, не видела и не понимала ничего из того, что делалось перед ней; она только чувствовала себя опять вполне безвозвратно в том странном, безумном мире, столь далеком от прежнего, в том мире, в котором нельзя было знать, что хорошо, что дурно, что разумно и что безумно. Позади ее сидел Анатоль, и она, чувствуя его близость, испуганно ждала чего то.
После первого монолога всё общество встало и окружило m lle Georges, выражая ей свой восторг.
– Как она хороша! – сказала Наташа отцу, который вместе с другими встал и сквозь толпу подвигался к актрисе.
– Я не нахожу, глядя на вас, – сказал Анатоль, следуя за Наташей. Он сказал это в такое время, когда она одна могла его слышать. – Вы прелестны… с той минуты, как я увидал вас, я не переставал….
– Пойдем, пойдем, Наташа, – сказал граф, возвращаясь за дочерью. – Как хороша!
Наташа ничего не говоря подошла к отцу и вопросительно удивленными глазами смотрела на него.
После нескольких приемов декламации m lle Georges уехала и графиня Безухая попросила общество в залу.
Граф хотел уехать, но Элен умоляла не испортить ее импровизированный бал. Ростовы остались. Анатоль пригласил Наташу на вальс и во время вальса он, пожимая ее стан и руку, сказал ей, что она ravissante [обворожительна] и что он любит ее. Во время экосеза, который она опять танцовала с Курагиным, когда они остались одни, Анатоль ничего не говорил ей и только смотрел на нее. Наташа была в сомнении, не во сне ли она видела то, что он сказал ей во время вальса. В конце первой фигуры он опять пожал ей руку. Наташа подняла на него испуганные глаза, но такое самоуверенно нежное выражение было в его ласковом взгляде и улыбке, что она не могла глядя на него сказать того, что она имела сказать ему. Она опустила глаза.
– Не говорите мне таких вещей, я обручена и люблю другого, – проговорила она быстро… – Она взглянула на него. Анатоль не смутился и не огорчился тем, что она сказала.
– Не говорите мне про это. Что мне зa дело? – сказал он. – Я говорю, что безумно, безумно влюблен в вас. Разве я виноват, что вы восхитительны? Нам начинать.
Наташа, оживленная и тревожная, широко раскрытыми, испуганными глазами смотрела вокруг себя и казалась веселее чем обыкновенно. Она почти ничего не помнила из того, что было в этот вечер. Танцовали экосез и грос фатер, отец приглашал ее уехать, она просила остаться. Где бы она ни была, с кем бы ни говорила, она чувствовала на себе его взгляд. Потом она помнила, что попросила у отца позволения выйти в уборную оправить платье, что Элен вышла за ней, говорила ей смеясь о любви ее брата и что в маленькой диванной ей опять встретился Анатоль, что Элен куда то исчезла, они остались вдвоем и Анатоль, взяв ее за руку, нежным голосом сказал:
– Я не могу к вам ездить, но неужели я никогда не увижу вас? Я безумно люблю вас. Неужели никогда?… – и он, заслоняя ей дорогу, приближал свое лицо к ее лицу.
Блестящие, большие, мужские глаза его так близки были от ее глаз, что она не видела ничего кроме этих глаз.
– Натали?! – прошептал вопросительно его голос, и кто то больно сжимал ее руки.
– Натали?!
«Я ничего не понимаю, мне нечего говорить», сказал ее взгляд.
Горячие губы прижались к ее губам и в ту же минуту она почувствовала себя опять свободною, и в комнате послышался шум шагов и платья Элен. Наташа оглянулась на Элен, потом, красная и дрожащая, взглянула на него испуганно вопросительно и пошла к двери.
– Un mot, un seul, au nom de Dieu, [Одно слово, только одно, ради Бога,] – говорил Анатоль.
Она остановилась. Ей так нужно было, чтобы он сказал это слово, которое бы объяснило ей то, что случилось и на которое она бы ему ответила.
– Nathalie, un mot, un seul, – всё повторял он, видимо не зная, что сказать и повторял его до тех пор, пока к ним подошла Элен.
Элен вместе с Наташей опять вышла в гостиную. Не оставшись ужинать, Ростовы уехали.
Вернувшись домой, Наташа не спала всю ночь: ее мучил неразрешимый вопрос, кого она любила, Анатоля или князя Андрея. Князя Андрея она любила – она помнила ясно, как сильно она любила его. Но Анатоля она любила тоже, это было несомненно. «Иначе, разве бы всё это могло быть?» думала она. «Ежели я могла после этого, прощаясь с ним, улыбкой ответить на его улыбку, ежели я могла допустить до этого, то значит, что я с первой минуты полюбила его. Значит, он добр, благороден и прекрасен, и нельзя было не полюбить его. Что же мне делать, когда я люблю его и люблю другого?» говорила она себе, не находя ответов на эти страшные вопросы.


Пришло утро с его заботами и суетой. Все встали, задвигались, заговорили, опять пришли модистки, опять вышла Марья Дмитриевна и позвали к чаю. Наташа широко раскрытыми глазами, как будто она хотела перехватить всякий устремленный на нее взгляд, беспокойно оглядывалась на всех и старалась казаться такою же, какою она была всегда.
После завтрака Марья Дмитриевна (это было лучшее время ее), сев на свое кресло, подозвала к себе Наташу и старого графа.
– Ну с, друзья мои, теперь я всё дело обдумала и вот вам мой совет, – начала она. – Вчера, как вы знаете, была я у князя Николая; ну с и поговорила с ним…. Он кричать вздумал. Да меня не перекричишь! Я всё ему выпела!
– Да что же он? – спросил граф.
– Он то что? сумасброд… слышать не хочет; ну, да что говорить, и так мы бедную девочку измучили, – сказала Марья Дмитриевна. – А совет мой вам, чтобы дела покончить и ехать домой, в Отрадное… и там ждать…
– Ах, нет! – вскрикнула Наташа.
– Нет, ехать, – сказала Марья Дмитриевна. – И там ждать. – Если жених теперь сюда приедет – без ссоры не обойдется, а он тут один на один с стариком всё переговорит и потом к вам приедет.
Илья Андреич одобрил это предложение, тотчас поняв всю разумность его. Ежели старик смягчится, то тем лучше будет приехать к нему в Москву или Лысые Горы, уже после; если нет, то венчаться против его воли можно будет только в Отрадном.
– И истинная правда, – сказал он. – Я и жалею, что к нему ездил и ее возил, – сказал старый граф.
– Нет, чего ж жалеть? Бывши здесь, нельзя было не сделать почтения. Ну, а не хочет, его дело, – сказала Марья Дмитриевна, что то отыскивая в ридикюле. – Да и приданое готово, чего вам еще ждать; а что не готово, я вам перешлю. Хоть и жалко мне вас, а лучше с Богом поезжайте. – Найдя в ридикюле то, что она искала, она передала Наташе. Это было письмо от княжны Марьи. – Тебе пишет. Как мучается, бедняжка! Она боится, чтобы ты не подумала, что она тебя не любит.


Источник — «http://wiki-org.ru/wiki/index.php?title=Теория_алгоритмов&oldid=80749296»