© 2016 МГТУ имени Н.Э. Баумана
Оглавление
Предисловие. 6
1. Введение. 6
1.1. Некоторые необходимые определения и понятия. 6
2. Задачи, алгоритмы.. 8
2.1. Задача. 9
2.2. Алгоритм. 16
3. Нормальные алгорифмы Маркова (НАМ). 21
4. Машины Тьюринга. 23
4.1. Одноленточная МТ. 23
4.2. Многоленточная МТ. 26
4.3. Недетерминированная МТ. 27
4.4. Оракульная МТ. 28
5. Равнодоступная адресная машина (РАМ) и некоторые другие подходы. 29
6. Сравнение различных формальных схем. 34
6.1. Кодировки входных данных. 34
6.2. О мерах сложности. 36
6.3. Теоремы сравнения. 40
6.4. Полиномиальные и неполиномиальные оценки сложности. 43
7. Сложность алгоритмов некоторых задач. 45
7.1. Задача нахождения максимального числа. 46
7.2. Задача сортировки. 46
7.3. Задача о камнях. 47
7.4. Простота числа. 47
7.5. Задача о кратчайшем (минимальном) остове (остовном дереве). 48
7.6. Задача коммивояжера. 50
7.7. Задача о комивояжере и динамическое программирование. 51
7.8. Задача о кратчайшем пути. 52
7.9. Задача о выполнимости КНФ (КНФ-выполнимость) 53
8. Схемы из функциональных элементов. Схемная сложность. 53
8.1. Схемы из функциональных элементов. 53
8.2. Оценки сложности СФЭ. 56
9. Теория NP-полноты.. 62
9.1. Классы P и NP. 62
9.2. Сводимость задач. 64
9.2.1. Смысл сводимости. 64
9.2.2. Полиномиальная сводимость. 66
9.2.3. Сводимость по Тьюрингу. 68
9.3. Теорема Кука. 70
9.4. Структура класса NP и некоторые выводы.. 77
10. Иерархия сложности 
. 81
10.1. Классы NP и co-NP. 81
10.2. Классы P-SPACE и NP-SPACE. 84
10.2.1. Классы сложности P-SPACE и NP-SPACE. 84
10.3. Логика предикатов и PSPACE –полные задачи. 92
10.4. Классы P и P/poly. 105
10.5. Некоторые результаты.. 109
11. Подходы к решению NP-полных задач. 109
11.1. NP-полнота в сильном смысле. Псевдополиномиальные алгоритмы 110
11.2. Приближенные алгоритмы.. 112
11.3. Полиномиально-разрешимые частные случаи NP-полных задач. 114
11.4. Методы направленного перебора. 115
12. Коммуникационная сложность. 118
Заключение. 123
13. Задачи и вопросы для самопроверки по курсу «Математическая логика и теория алгоритмов». 123
13.1. Задачи. 123
13.2. Вопросы. 126
14. Рекомендованная литература. 128
Предисловие.
Данный текст представляет собой конспект лекций по курсу «Математическая логика и теория алгоритмов», предусмотренного учебным планом МГТУ им. Н.Э.Баумана для студентов кафедры ИУ-8. Он содержит самые базовые классические результаты по теории сложности алгоритмов, а также необходимые для изложения материалы по математической логики, которые не вошли в читавшиеся ранее курсы дискретной математики и основ информатики. Представлены формальные модели алгоритмов, рассмотрены различные подходы к понятию сложность задачи. Описаны наиболее известные классы сложности задач. Приведены примеры исследования сложности известных задач.
Излагаемый материал необходим для последующих курсов, в особенности, курса «Алгоритмы и структуры данных» и «Теория принятия решений».
Введение
1.1. Некоторые необходимые определения и понятия.
При сравнении скорости роста двух неотрицательных функций f(n) и g(n) удобно использовать следующие обозначения.
Говорят, что функция g(n) f(n)-ограничена, если g(n)£f(n). Если f(n) - полином, то функция g(n) называется полиномиально ограниченной, а если экспонента – экспоненциально ограниченной.
Будем говорить, что f(n)= O(g(n)), если существуют такие положительные константы c и N, что f(n)≤c g(n)для всех n>N.
В этой же ситуации можно использовать и обозначение g(n)=Ω(f(n)). Например, справедливы соотношения log2 n = O(n), n = Ω(log2 n), n = O(2n).
Будем говорить, что f(n)= o(g(n)), если 
.
Если f(n)= O(g(n)) и O(f(n))= g(n) , то это будем обозначать через f(n)=Θg(n).
Для числа x целые числа [x] и ]x[ - это целые части числа с недостатком и с избытком.
Опр. Алфавит A – это конечный или бесконечный набор символов: A={a1,a2,…,an,…}.
Опр. Слово – это конечный упорядоченный набор символов алфавита.
Выделяется специальное пустое слово 
(слово, не содержащее символов).
Пусть 
– множество всех слов в алфавите 
.
Опр. Язык L – это подмножество 
. ( 
).
Опр. Конкатенация 
слов и .
.
Число сочетаний (без повторений) из n элементов по k элементов обозначим через 
. Число сочетаний с повторениями из n элементов по k элементов обозначим через 
.
Если не оговорено обратное, вместо log2n будем писать log n.
Простой граф с множеством вершин V, |V|=n, и множеством ребер E, |E|=m, будем обозначать через G=(V,E). Ориентированность графа будет оговариваться отдельно.
Булевы переменные - это переменные, принимающие значения из множества B={0,1}. Множество n-мерных векторов из нулей и единиц называется булевым кубом и обозначается Bn. Очевидно, что число вершин этого куба равно 2n.
Отображение f: Bn®B называется булевой функцией. Число булевых функций от n переменных равно
Примеры известных булевых функций: конъюнкция (&), дизъюнкция (È), отрицание (Ø), импликация (®), сложение по модулю «два» (Å), эквивалентность ( 
) и пр.
Табличный способ задания функции представляет собой таблицу размером 2nx(n+1). В последнем столбце таблице записаны значения функции на каждом из 2n возможных наборах значений переменных. Сами эти наборы записаны в первых n клетках каждой строки.
При работе с булевыми функциями мы иногда будем заменять значок логического умножения & значком 
, обычной точкой (произведением) или не писать его вовсе.
Задачи, алгоритмы
В любой математической дисциплине, которая претендует на наличие собственного взгляда на "математическую" проблематику, исходные понятия не определяются математическим языком. Обычно, речь идет об "интуитивных" объектах, сущность которых может обсуждаться за пределами математики.
В этом курсе мы тоже будем иметь дело с несколькими лишь интуитивно определяемыми понятиями. Важнейшие из них - задача и алгоритм. Сразу оговорим очевидное. Для описания базовых понятий раздела науки используются те же слова, которые применяются и на бытовом уровне. Но в науке они становятся терминами и приобретают особый смысл. В лекции иногда трудно избежать ситуации, когда одно и то же слово используется и в качестве термина, и в качестве обиходного. В тексте при подозрении на двусмысленное понимание для терминов будет использоваться курсив, а для обиходных – кавычки, а там, где двусмысленность при разумном понимании невозможна – обычный шрифт.
Задача
Начнем с обсуждения первого из упомянутых понятий – понятия задача. При описании базовых понятий или аксиоматики используется три способа: аналогия, пример и расчленение «менее элементарных» сущностей на совокупность «более элементарных». Пойдем и мы по этому пути.
Наш курс тесно связан с двумя математическими дисциплинами: математической логикой и дискретной математикой. Поэтому самая простая идентификация понятия может быть дана по аналогии. Вспомним то, что имелось в виду под задачей в этих дисциплинах. В нашем курсе мы будем иметь дело примерно с тем же самым.
Например, в [1] определение задачи вообще не дается, считается, что оно «интуитивно очевидно». В [2] под задачей понимается «некоторый общий вопрос, на который следует дать ответ». При этом «задача содержит несколько параметров или свободных переменных, конкретные значения которых не определены».
В [4] под задачей понимается «выбор наилучшей конфигурации или множества параметров для достижения некоторой цели». При этом задачи делятся на непрерывные и комбинаторные. «В непрерывных задачах обычно отыскивается множество действительных чисел или даже некоторая функция; в комбинаторных задачах – некоторый объект из конечного или возможно бесконечного счетного множества». Другими словами, задача оптимизации – это пара ( F, c) , где F – произвольное множество, область допустимых точек, а – c функция стоимости, отображающая элементы F на множество действительных чисел. Требуется найти такую x* точку из F, на которой значение функции c(x*) обладает определенным свойством, например, минимально, максимально и пр.
Теперь займемся «расчленением» сущностей, приведенных выше. Задачи, рассматриваемые в нашем курсе, это, в подавляющем большинстве, задачи комбинаторные или дискретные. Уже само слово комбинаторный относится к упомянутому выше множеству F. Вернее, к способу его задания. Мы видим, что при таком задании с задачей обычно связывается два объекта: множество параметров и структура связей между ними. Параметры – «язык» для описания условий задачи. Структура связей содержит нечто, позволяющее описать F , а также сформулировать вопрос (см. [2]) или требование к c(x*) трактуемое как вопрос, свойство функционала и пр. (См. [4]).
В теории сложности термин задача сразу же разбивается на два термина: индивидуальная задача и массовая задача. Это связаны со способом задания параметров. Массовая задача предполагает описание множества параметров, а индивидуальная задача возникает, при фиксации значений этих параметров.
Понятие формы задачи, грубо говоря, возникает в связи с возможностью "незначительно" модифицировать вышеупомянутые форму вопроса или свойство c(x*).
Поясним сказанное на примерах. Но эти примеры будут носить не только иллюстративный характер. В их тексте мы дадим и разъясним многие общие (выходящие за рамки примера) понятия, которые в дальнейшем будут использоваться.
Многие из этих примеров будут неоднократно упоминаться в дальнейшем, поэтому для упрощения ссылок на них мы дадим приведенным ниже задачам краткие названия.
Пример 1. (Поиск максимального числа). Заданы N целых чисел: a1,…aN. Требуется найти максимальное из них.
На примере этой простейшей задачи постараемся подробно проанализировать условие задачи.
Здесь параметрами являются числа: N и a1,…,aN. Правильнее представлять их в виде объектов, имеющих числовые значения. Это означает, что количество сущностей, между которыми при формулировке и решении задачи будут устанавливаться связи, равно 2N+2. Одна сущность предназначена для описания мощности множества сравниваемых чисел, другая – представляет собой числовое значение этой мощности (оно равно N), N сущностей предназначено для идентификации сравниваемых объектов. Эта идентификация достигается путем индексации: 1,…,N. Остальные N: a1,…aN – это веса (значения) проиндексированных объектов. В дальнейшем для сущностей, принимающих числовые значения, будем использовать понятие параметр, а для остальных – объект. Они не равноправны: сначала должны быть заданы объекты, а затем уже – параметры. Это означает, что задание параметра возможно после задания объекта. Можно также задать все объекты и лишь часть параметров или задать часть объектов, а затем определить параметры, с ними связанные.
В нашем примере связи на множестве объектов строятся через их параметризацию с использованием отношения сравнения чисел. Задание (свойство c(x*))в данном случае состоит в нахождении объекта, значение которого максимально. Если всем этим объектам и параметрам присвоены конкретные значения, то получается индивидуальная задача. В ситуации, когда речь идет о произвольных значениях объектов, мы имеем дело с массовой задачей. Заметим, что роли параметра N и параметров a1,…aN неодинаковы, т.е. можно говорить о множествах индивидуальных задач, получаемых из массовой задачи путем фиксации параметра N.
Уже такая простейшая задача позволяет проиллюстрировать понятие формы задачи. В данном случае можно говорить о задаче в форме оптимизации. Подобная форма возникает тогда, когда речь идет об экстремуме некоторого функционала на множестве исходных параметров задачи.
Задача в вычислительной форме получается при следующей модификации вопроса: "Требуется найти величину максимального из данных чисел". То есть здесь не нужно указывать сам объект, а только его числовое значение. Казалось бы, это условие не очень важное, но для ряда задач трудности решения их в оптимизационной и вычислительной формах различаются весьма существенно.
Другой распространенный тип задач - задачи в форме распознавания. В нашем случае для подобных задач добавляется еще один параметр B, а задание выглядит следующим образом. Требуется ответ на вопрос, существует ли среди объектов a1,…aN такой, значение которого не меньше, чем B? При этом, вообще говоря, не требуется ни указывать сам объект, ни его значение.
В последнем случае мы видим, что речь идет не только о форме задания, но и изменении множества параметров. То есть задача уже другая, но "близкая" к исходной. Это соответствует интуитивному представлению о том, что «незначительное» изменение в формулировке условия может приводить к «незначительному» изменению самой задачи.
Что значит незначительно? Как при этом меняется трудность решения? Этими вопросами мы тоже будем заниматься в нашем курсе.
Пример 2. (Разложение на множители). Дано натуральное число N. Требуется разложить его на простые множители.
Параметром здесь является само число (значение объекта). При его фиксировании возникает индивидуальная задача. Если говорить о форме задачи, то она явно не оптимизационная, да и вычислительной не является, хотя в широком смысле под вычислением в данной задаче можно понимать нахождение всех простых делителей с их кратностями. Близкая к данной задача в форме распознавания состоит в определении простоты числа (задача о простоте числа).
Пример 4. (Задача о гамильтоновом цикле). Дан простой неориентированный граф G c N вершинами. Требуется узнать, существует ли в нем гамильтонов цикл. (Гамильтоновым называется цикл в графе, который проходит через каждую вершину графа ровно по одному разу.)
Набор исходных параметров - это число N и множество ребер графа, задаваемых как пары разных чисел из множества 1,…,N. Понятие гамильтонова цикла задает связь на множестве параметров.
Задача представлена в форме распознавания. Вычислительную и оптимизационную форму здесь искать малоинтересно. Но возникает еще одна форма - перечислительная. В этой задаче требуется найти число различных гамильтоновых циклов графа.
В дальнейшем будем, как правило, называть эту задачу просто: "гамильтонов цикл".
Пример 5. (Задача о коммивояжере.) Дан граф G c N вершинами, ребрам которого приписаны веса cij. Требуется найти гамильтонов цикл экстремальной длины. (Длина гамильтонова цикла может задаваться по-разному. В большинстве случаев – это сумма длин входящих в цикл ребер. Если не оговаривается обратное, то именно эта ситуация и имеется в виду. Но за длину можно брать и максимальный (минимальный) вес входящего в него ребра, и более сложный функционал от длин ребер. Наиболее распространенный случай, когда под экстремумом понимается минимум. Если же экстремум трактуется как максимум, то это оговаривается отдельно. Такие задачи называются задачами коммивояжера на максимум).
Можно считать, что граф полный (отсутствующим ребрам приписать специальным образом выбранные «большие» значения). Тогда набор исходных параметров определяется числом N и матрицей весов ребер С=(cij). Индивидуальная задача получается из массовой фиксированием этих параметров.
В дальнейшем будем называть эту задачу просто "коммивояжер".
В формулировку задания входит понятие гамильтонова цикла, которое и задает связь на множестве параметров.
В вышеупомянутом варианте мы имеем задачу в форме оптимизации. Вычислительный вариант задачи состоит, например, в нахождении длины минимального гамильтонова цикла. В случае задачи на минимум в варианте распознавания задается еще число B и требуется ответить на вопрос, существует ли гамильтонов циклы с длиной, не превосходящей B.
Можно получить еще один вариант - перечислительный. Он состоит в нахождении количества минимальных гамильтоновых циклов.
Приближенный вариант без оценки точности состоит в нахождении гамильтонова цикла, который отличается от минимального "незначительно". При этом в понятие «незначительно» никакого формального смысла не вкладывается.
Приближенный вариант с оценкой точности может выглядеть следующим образом. Требуется для заданного числа k найти гамильтонов цикл, превосходящий минимальный не более чем в k раз.
Пример 6. (Задача о выполнимости КНФ.) Задана булевская функция F от N переменных в виде конъюнктивной нормальной формы K. Требуется определить, существует ли такой набор значений переменных, на котором функция обращается в единицу.
Здесь мы имеем задачу в форме распознавания. Исходными параметрами являются N и K. Что касается задания связей на множестве исходных параметров, то их можно проиллюстрировать следующим образом. Всех конъюнкций от N переменных 3N. Обозначим это множество через Q(N). Индивидуальная задача получается из массовой путем фиксирования числа N и подмножества M из Q(N).
В дальнейшем будем называть эту задачу просто "КНФ-выполнимость".
Задача о клике ("клика") состоит в нахождении максимального (по числу вершин) полного подграфа K заданного графа G. Задача о кратчайшем остове ("остов") состоит в нахождении минимального (например, по сумме длин входящих ребер) остовного дерева T графа G, ребрам которого приписаны веса. Само название Задача о кратчайшем пути ("кратчайший путь") между двумя фиксированными вершинами графа уже все определяет. Задача об изоморфизме графов ("изоморфизм графов") состоит в определении изоморфизма пары заданных графов.
Алгоритм
Если с понятием задачи все теперь более или менее понятно, то вот с понятием алгоритма дело обстоит сложнее. Работа в этом направлении породила не только теорию сложности или столь распространенные сейчас компьютеры, но и разделение математики, в которой на некоторое время остро стал вопрос о конструктивности. Но это тема отдельного большого разговора.
Итак, есть задача. Встает вопрос о ее решении. Какую бы форму задачи мы не взяли, решение задачи предполагает нахождение некоторого объекта или его свойства. В случае индивидуальной задачи по исходному набору параметров (объектов и их значений) требуется найти некоторый объект (если речь идет об оптимизационной форме), число (если речь идет о вычислительной или перечислительной форме), вариант (один из двух: "да" или "нет", если речь идет о задаче в форме распознавания).
В жизни мы отнюдь не всегда для решения задач используем "алгоритмы". (Скорее, почти никогда их не используем). Действительно, мы можем найти объект, угадав его или используя наш опыт.
В этих случаях процесс нахождения состоит из двух важных этапов. Сначала в результате угадывания или опыта мы в качестве предполагаемого решения выбираем некоторый объект. Затем мы убеждаемся, что данный объект является требуемым решением задачи. Назовем первый этап этапом предложения, а второй - этапом проверки.
Если мы имеем задачу в форме распознавания, то нам не важна "логика" действий на первом этапе. Действительно, мы просто строго проверяем объект на наличие требуемого свойства. Например, в задаче о камнях мы считаем сумму весов предложенного подмножества объектов, в задаче о гамильтоновом цикле проверяем предложенное подмножество ребер на "гамильтоновость".
В том случае, когда правильное предложение возникает в результате отгадки, интуиции, опыта и пр., принято объединять все эти процессы, вводя понятие оракула. То есть оракул- это абстрактная сущность, которая мгновенно, без затраты ресурсов (памяти, времени и т.п.) способна предоставить предложение, возможно, нуждающееся в проверке. Конечно, его можно проверить, но оракул на то и оракул, чтобы не ошибаться.
Для задач в форме оптимизации тоже может иметь место этап предложения, но этап проверки эквивалентен исходной задаче. В жизни мы можем его заменить верой или интуицией, но в математике требуется нечто иное. Требуется процедура, не зависящая от производящего ее субъекта, которая бы абсолютно достоверно позволяла находить (проверять) требуемый в условии задачи объект.
Это и есть интуитивное представление алгоритма. В [2] например, оно звучит так. Алгоритм - это общая, выполняемая шаг за шагом процедура решения задачи. Прилагательное "общая" отвечает за автоматизм, независимость от субъекта, использующего алгоритм. Требование выполнения работы "шаг за шагом" здесь не ограничивает тип алгоритма (например, не отбрасывает параллельные или вероятностные алгоритмы), а лишь указывает на предсказуемость и проверяемость самой процедуры решения.
Во многих попытках дать определение алгоритма используются понятия "искусство" и "автоматизм" (машинное исполнение). При этом первое как раз должно отсутствовать в этом самом "алгоритме", а второе должно его характеризовать.
Формализация понятия "алгоритм" необходима также из-за "несимметричности" ответа на вопрос, существует ли алгоритм для решения задачи Z?
Действительно, ответ "да" может быть получен путем построения некоторой процедуры решения, которая укладывается в "интуитивное" понятие алгоритма. Такие процедуры и строились в процессе всей истории математики, когда формальным построениям самого понятия алгоритм внимания не уделялось. Если для некоторой задачи не могли построить метода решения, то это списывалось на недостаток умения.
Имея лишь интуитивное представление об алгоритме, нельзя доказать, что этого самого алгоритма не существует.
В 30-е годы стали появляться первые формальные схемы алгоритма. Эти схемы были предназначены исключительно для теоретических исследований. С некоторыми из них мы познакомимся здесь. Речь пойдет, например, о машинах Тьюринга (МТ), нормальных алгорифмах Маркова (НАМ) и др.
Алгоритм производит некоторые "действия" с объектами и параметрами, начиная с исходных условий задачи (входные условия, вход). Во всех известных формальных схемах этот вход как-то задается. В самом общем случае можно считать, что это задание выглядит в виде слова в некотором алфавите.
Напомним, что множество (конечное или бесконечное) символов называется алфавитом A. Слово P в алфавите A - любая конечная последовательность символов алфавита.
Если множество символов одного алфавита является подмножеством символов другого, то первый называется подалфавитом второго. А второй - надалфавитом первого.
Пусть A - подалфавит некоторого алфавита B. Слово, состоящее из символов алфавита A, будем называть словом в алфавите A. Слово, состоящее из символов алфавита B, будем называть словом над алфавитом A.
Заметим, что достаточно ограничиться алфавитом из двух символов, например, 0 и 1. Любой символ ai алфавита A={a1,…,an,…} может быть закодирован следующим образом: ai =011...10, где 1 повторяется n раз.
В известных формальных схемах (формализмах) "алгоритм" можно представить как некоторое пошаговое преобразование одних слова в другие, начиная с входа x1,…,xn = X. В результате последнего шага таких преобразований получаем некоторое выходное слово Y. Его можно трактовать как результат работы алгоритма. Задавая буквы входного алфавита числовыми последовательностями, можно считать, что речь идет о вычислении функции f(x1,…,xn)=f(X)=Y.
Обратим внимание на употребление понятия эквивалентности в связи с наличием нескольких возможных представлений (кодировок, способов записи) входных объектов.
Два выражения (кодировки) B и C считаются эквивалентными B»C в двух случаях: либо оба выражения не определены (бессмысленны), либо определены и обозначают один и тот же объект.
Будем говорить, что алгоритм Á является алгоритмом в алфавите A, если он переводит слова x1,…,xn в алфавите A в слова f(x1,…,xn) в алфавите A.
Будем говорить, что алгоритм Á является алгоритмом над алфавитом A, если он переводит слова x1,…,xn над алфавитом A в слова f(x1,…,xn) над алфавитом A.
При этом алгоритм Á может работать не с любыми словами алфавита. Множество тех слов, к которым он применим, назовем областью действия алгоритма Á, а результат применения алгоритма Á к слову P обозначим через Á (P). При этом сам алгоритм не обязан распознавать слова из своей области действия.
Рассмотрим два алгоритма Á и Â над алфавитом A.
Если Á(P)»Â(P) для любого слова P в алфавите A, то эти алгоритмы называются вполне эквивалентными относительно A.
Если Á(P)»Â(P) для любого слова P в алфавите A такого, что хотя бы одно из выражений Á(P) или Â(P) определено и является словом в алфавите A, то эти алгоритмы называются эквивалентными относительно A.
Рассматриваемые ниже формальные подходы к понятию алгоритма заслужили внимание благодаря гипотезам типа тезиса Черча.
Этот тезис говорит об эквивалентности широкого неформально и смутного понятия "интуитивный алгоритм" узкому и весьма замысловатому на первый взгляд формализму типа алгорифма Маркова (МТ) или машины Тьюринга. Утверждается, что для любой задачи, для которой существует «интуитивный» алгоритм решения, можно, например, построить МТ, которая будет решать эту задачу.
Рассмотрим теперь данные формализмы подробно. Заметим, что алгоритм может предназначаться как для решения массовой, так и для решения индивидуальной задачи. (Например, алгоритм сложения двух чисел и алгоритм сложения 5 и 2). Конечно, мы изначально предполагаем, что алгоритм должен решать массовую задачу.
Сделаем одно замечание. Во всех перечисленных ниже формальных подходах алгоритм имеет дело с преобразованием одних слов в другие. То есть, условие задачи Z можно рассматривать как слово в некотором алфавите A. Обозначим все множество слов этого алфавита через A*. Подмножество слов алфавита назовем языком. Обратим внимание, что в содержательном смысле не все слова алфавита являются условиями индивидуальных задач из Z.
Особенно удобно ставить некоторый язык из A* в соответствие задачам в форме распознавания. В этих задачах в качестве решения возможно два варианта: 1 ("да") или 0 ("нет"). Таким образом, задаче Z в форме распознавания можно сопоставить язык LZ, содержащий в качестве слов все слова из A*, которые являются условиями индивидуальных задач с ответом "да".
Дата: 2019-07-30, просмотров: 207.
