Всего: 71 1–20 | 21–40 | 41–60 | 61–71
Добавить в вариант
Постройте схему, выполняющую умножение вводимого числа в четверичной системе на 3.
Данная схема состоит из вершин (называемых состояниями) и стрелок, символизирующих правила, по которым работает эта схема. Схема начинает работу в начальном состоянии S0, выделенном оранжевым. Поступающее на ход число анализируется посимвольно. При рассмотрении каждого символа мы переходим из текущего состояния по стрелочке, над которой написан этот символ.
В данной задаче мы записываем число от последней цифры к первой. Если количество цифр в произведении больше количества цифр в множителе, для правильной работы автомата к множителю спереди нужно добавить 0 (т. е. добавить 0 в конце вводимой строки).
Например, для строки 123 автомат выдаст строку 322, а для строки 1230 (соответствующей тому же самому четверичному числу 321) выдаст результат 3222 (соответствующий числу 2223).
Каким арифметическим операциям она соответствует? Мы считываем символ 3 и умножаем его на 3, получаем четверичное число 21. Добавляем единицу, которая была «в уме» (состояние S1) и получаем 22. Это число как раз и соответствует правой части команды. По такому же принципу строятся и остальные команды.Напишите логическую формулу, описывающую свойство, которым обладает комбинация фишек на левой картинке, но не обладает комбинация на правой. Постарайтесь, чтобы описание было как можно короче.
В формуле используются следующие обозначения:
Фишки обозначаются переменными x, y, z. Простые свойства описываются такими выражениями как «x синий», «y красный», «z желтый», «x сосед y» (последнее означает, что фишки стоят на различных клетках, у которых есть общая сторона или угол). Для записи более сложных свойств используются логические связки, которые соединяют простые свойства:
И, ИЛИ, НЕ ВЕРНО ЧТО, СЛЕДОВАТЕЛЬНО, ТОГДА И ТОЛЬКО ТОГДА, ДЛЯ ВСЕХ x, СУЩЕСТВУЕТ x ТАКОЙ, ЧТО (вместо x можно использовать y или z).
Для упорядочения связок используются круглые скобки. В качестве начального решения введена формула, которая не верна для обоих картинок.
Операция умножения требует существенно больше элементарных операций чем операция сложения (или вычитания), поэтому для повышения эффективности алгоритмов применяют алгебраические приемы, которые за счет увеличения числа операций сложения и вычитания используют меньше операций умножения.
Выражение 
легко можно вычислить используя 6 операций умножения: для возведения каждого числа в куб требуется две операции. Придумайте алгоритм вычисления этой суммы за меньшее число операций умножения. Чем меньше операций, тем выше будет оценка за задачу.
Для умножения на 3 операция умножения не нужна: она заменяется двумя сложениями.За круглым столом сидят четыре человека. Каждый из них либо рыцарь, либо лжец. Рыцари всегда говорят только правду, а лжецы всегда лгут. Постройте логическую схему, которая принимает значение истина тогда и только тогда, когда каждый из сидящих за столом может произнести фразу «Оба моих соседа лжецы».
На логической схеме входы соответствуют людям: нули обозначают лжецов, а единицы рыцарей. Соседние входы соответствуют соседним людям, кроме того, поскольку стол круглый, верхний вход будем считать соседним с нижним. Разрешается использовать логические элементы AND (и), OR (или), NOT (не) и XOR (исключающее или).
За круглым столом сидит n > 2 человек. Каждый из них либо рыцарь, либо лжец. Рыцари всегда говорят только правду, а лжецы всегда лгут. Опишите способ построения логической схемы c n входами, которая принимает значение истина тогда и только тогда, когда каждый из сидящих за столом может произнести фразу «Оба моих соседа лжецы».
На логической схеме входы соответствуют людям: нули обозначают лжецов, а единицы рыцарей. Соседние входы соответствуют соседним людям, кроме того, поскольку стол круглый, верхний вход будем считать соседним с нижним.
Разрешается использовать логические элементы AND (и), OR (или), NOT (не) и XOR (исключающее или).
На некоторых клетках квадратной клетчатой доски стоят рыцари, которые говорят только правду, а на некоторых — лжецы, которые всегда лгут. Некоторые клетки могут быть свободны; на каждой клетке стоит не более одного человека. Рыцари обозначены светлыми (голубыми) кружками, лжецы — тёмными (красными).
Составьте логическое выражение, которое истинно тогда и только тогда, когда каждый из стоящих на доске человек может произнести фразу «Все мои соседи лжецы».
На левой картинке изображён пример, удовлетворяющий условию задачи, на левой — не удовлетворяющий.
Рыцари, которые говорят только правду, и лжецы, которые всегда лгут, выстроились в ряд. (В ряду хотя бы один человек).Каждый из них произнёс фразу «Все мои соседи лжецы». Обозначим рыцаря буквой Р, а лжеца — буквой Л. Тогда каждой последовательности рыцарей и лжецов, для которой выполняется условие задачи, соответствует некоторое слово.
Опишите это слово, используя формулу, которая называется регулярным выражением. Такое выражение строится с помощью описываемых ниже операций «итерация», «умножение», «сложение».
Так для повторения блока из нескольких букв используйте операцию «звездочка» (итерация), например, (abb)* задает множество слов {пустое слово, abb, abbabb, abbabbabb, …}. Умножение множеств (эту операцию, как обычно в алгебре, изображают точкой приписыванием второго операнда вслед за первым, что мы и будем делать), описывает склейку всех слов первого множества со словами второго (третьего и т. д.), например a*cb* обозначает множество слов: {с, ac, cb, acb, aac,..., aaa...acb...b, ...}. Обратите внимание что слова, в которых нет букв a или b, получаются за счет того, что результат итерации может не содержать символов, то есть быть пустым словом.
Последней операцией, которая используется в формулах, является сложение. Сложение соответствует объединению множеств. Так, обозначение (a + b)*c + d(ac* + ) описывает множество всех последовательностей из букв a и b (обозначается (a + +b)*), к концу которых присоединена буква c, объединенного с множеством слов, начинающихся с буквы d, за которой следует буква a, а за ней любое число букв c и ещё одним однобуквенным словом (d умножить на пустое слово — это d).
Рыцари, которые говорят только правду, и лжецы, которые всегда лгут, выстроились в ряд. (В ряду хотя бы один человек). Каждый из них произнёс фразу «Все мои соседи лжецы». Обозначим рыцаря буквой Р, а лжеца — буквой Л. Тогда каждой последовательности рыцарей и лжецов, для которой выполняется условие задачи, соответствует некоторое слово.
Постройте схему, которая будет распознавать слова в алфавите {Л, Р}, соответствующие описанным в задаче последовательностям рыцарей и лжецов.
Данная схема состоит из вершин (называемых состояниями) и стрелок. Каждая стрелка соединяет два состояния и символизирует переход схемы из первого состояния во второе..
Схема начинает работу в начальном состоянии S0. Поступающее на вход слово анализируется посимвольно. При анализе каждого символа схема переходит из текущего состояния по стрелке, над которой написан этот символ.
После того, как всё слово проанализировано, схема заканчивает работу в одном из состояний.
Некоторые состояния необходимо пометить как конечные (жирная каёмка). Это те состояния, в которых схема оказывается, в случае, если поступившее на вход схемы слово соответствует условию.
Вдоль длинной улицы расположены дома, в каждом из которых живёт по одному человеку. Каждый из жителей улицы является сторонником одной из двух политических партий: 1 или 2. Каждый день каждый человек общается со всеми своими соседями (с одним соседом, если человек живёт в на краю улицы и с обоими соседями в остальных случаях). За ночь он обдумывает полученную от них информацию, и если оказывается, что двое его соседей являются сторонниками противоположной политической партии, к утру человек меняет свои взгляды.
На ленте записана произвольная последовательность единиц и двоек, соответствующая политическим взглядам жителей улицы в какой-то из дней. Постройте машину Тьюринга, которая преобразует эту строку в строку, соответствующую политическим взглядам жителей улицы на следующий день.
Вокруг круглой площади расположены 2017 домов, в каждом из которых живёт по одному человеку. Каждый из жителей площади является сторонником одной из двух политических партий: 1 или 2. Каждый день каждый человек общается с обоими своими соседями. За ночь он обдумывает полученную от них информацию, и если оказывается, что оба его соседа являются сторонниками противоположной политической партии, к утру человек меняет свои взгляды. Верно ли, что когда-нибудь политические взгляды жителей улицы стабилизируются?
раза.Вдоль длинной улицы расположены дома (хотя бы два), в каждом из которых живёт по одному человеку. Каждый из жителей улицы является сторонником одной из двух политических партий: 1 или 2. Каждый день каждый человек общается со всеми своими соседями (с одним соседом, если человек живёт в на краю улицы и с обоими соседями в остальных случаях). За ночь он обдумывает полученную от них информацию, и если оказывается, что двое его соседей являются сторонниками противоположной политической партии, к утру человек меняет свои взгляды.
На вход подаётся произвольная последовательность единиц и двоек, соответствующая политическим взглядам жителей улицы в какой-то из дней. Постройте схему, которая преобразует которая преобразует эту строку в строку, соответствующую политическим взглядам жителей улицы на следующий день.
Данная схема состоит из вершин (называемых состояниями) и стрелок. Каждая стрелка соединяет два состояния и символизирует переход схемы из первого состояния во второе..
Схема начинает работу в начальном состоянии S0. Поступающее на вход слово анализируется посимвольно. При анализе каждого символа схема переходит из текущего состояния по стрелке, над которой написан этот символ. При этом символ, написанный над стрелкой через запятую, подаётся на выход.
В некоторой компании у каждого человека по 3 друга. Каждый из них является сторонником одной из двух политических партий: красной или синей. Каждый день каждый человек общается со всеми своими друзьями. За ночь он обдумывает полученную от них информацию, и если оказывается, что большинство его друзей являются сторонниками противоположной политической партии, к утру человек меняет свои взгляды.
Постройте пример компании и исходного распределения политических симпатий, при котором стабилизации политических взглядов не происходит.
В некоторой компании у каждого человека по 3 друга. Каждый из них является сторонником одной из двух политических партий: красной или синей. Каждый день каждый человек общается со всеми своими друзьями. За ночь он обдумывает полученную от них информацию, и если оказывается, что большинство его друзей являются сторонниками противоположной политической партии, к утру человек меняет свои взгляды.
Докажите, что для любой компании существует исходное распределение политических взглядов при котором в дальнейшем стабилизации политических взглядов не происходит.
Опишите алгоритм возведения числа a в 255 степень с помощью только операции умножения:
1) За 14 операций умножения без использования дополнительной памяти (то есть разрешается использовать только исходное число и результат последней операции).
2) За 10 операций умножения с использованием любого количества дополнительной памяти.
3) За 10 операций умножения с использованием одной ячейки дополнительной памяти (то есть помимо исходного числа и результата последней операции, разрешается держать в памяти ещё одно число. Это число может меняться в процессе работы алгоритма).
Замечание: верное решение для 11.3 будет засчитываться и для 11.2.
Возведя её в квадрат и умножим затем на a, мы получим a в степени 
Таким образом, за 7 таких пар операций, 
превращается в 
(так 
на a, получим 
Поместим это число в ячейку памяти. 
в квадрат, получим 
на 
получим 
Запомним это число вместо 
на 
получим 
Постройте логическую схему с шестью входами и одним выходом.
На вход подаётся последовательность нулей и единиц (сверху вниз). Схема должна выдавать значение «1» («ИСТИНА») на тех (и только на тех) последовательностях, в которых для любого начального отрезка количество нулей не превосходит количество единиц.
Так, 101010 — подходящая последовательность, а 110001 — нет, так как среди первых пяти элементов три нуля и только две единицы.
автоматически означает и выполнение условия для отрезка длины 2n.На вход подаётся последовательность нулей и единиц (сверху вниз). Схема должна выдавать значение "1" ("ИСТИНА") на тех (и только на тех) последовательностях, в которых для любого начального отрезка количество нулей не превосходит количество единиц.
Так, 101010 — подходящая последовательность, а 110001 — нет, так как среди первых пяти элементов три нуля и только две единицы.
Докажите, что можно построить такую логическую схему для n > 100 входов, использовав не более 
логических элементов.
достаточно проверить выполнение условия только для всех начальных отрезков нечётной длины. Построим схему следующим образом. Во-первых, для каждой пары соседних входов с номерами 2k и 
кроме последней, соединим соответствующие входы при помощи как логического элемента AND, так и элемента ОR. Последние два входа соединим только при помощи элемента OR. Это даст нам 
логический элемент. Обозначим эти элементы AND[k] и OR[k] соответственно.
устраивающее нас количество единиц может принимать значение от 
Будем пытаться отслеживать все возможные значения этого количества при помощи логических элементов AND, и ОR. Часть схемы, проверяющую то, что количество единиц в первых 
мы уже построили части схемы, отслеживающие то, что количество единиц в первых 
и среди входов с номерами 
и 
и среди входов с номерами 
а значит её можно здесь не проверять. Таким обозом, для построения этой подсхемы достаточно соединить элемент OR[k] и подсхему A[k−1, k+1] при помощи элемента OR и для её построения нужен один новый элемент.
значит, условие задачи выполнено для всех последующих отрезков, поэтому подсхемы A[k, s] при 
нам не нужны. 
и 
то есть для 
То есть их количество не превосходит 
и для их построения требуется не более 
и для их построения требуется не 
То есть их количество равно 
и для их построения требуется не более 
дополнительных элементов. 
таких подсхем 
для каждого такого k. Всего их количество равно сумме чисел от 1 до целой части 
то есть не более 
и для их построения требуется не более 
дополнительных элементов.
таких подсхем 
для каждого такого k. Всего их количество равно сумме чисел от 1 до целой части 
то есть не более 
и для их построения требуется 
элементами AND, что как раз соответствует проверке утверждения задачи. Для этого потребуется m элементов. Таким образом, всего нам потребовалось не более 
Найдите количество таких последовательностей длины n из нулей и единиц, в которых для любого начального отрезка количество нулей не превосходит количество единиц.
Так, 101010 — подходящая последовательность, а 110001 — нет, так как среди первых пяти элементов три нуля и только две единицы.
При этом выполнение требуемого условия для последовательности соответствует тому, что данный путь никогда не опускается ниже прямой 
выше прямой 
или на ней, и вычтем из этого количество тех из этих путей, которые имеют участок ниже прямой 
(синий путь на рисунке) и рассмотрим новый путь, состоящий из старого начала, и нового окончания. Он также состоит из отрезков, идущих вправо или вверх, и содержит n таких отрезков, то есть заканчивается на прямой 
конец нового пути окажется строго ниже него. Любой путь такого вида можно также отразить относительно прямой 
после первого пересечения с ней, в результате чего получится интересующий нас путь, заканчивающийся не ниже диагонали. 
мы имеем всего 
путей, среди них 
путей заканчиваются на прямой прямой 
остальные делятся поровну между путями заканчивающимися выше этой прямой и ниже неё, причём все пути, заканчивающиеся ниже прямой 
мы имеем ровно половину путей заканчивающихся выше прямой 
и половину путей, заканчивающихся ниже неё. Среди путей, оканчивающихся ниже этой прямой, 
заканчиваются в точке пересечения прямых 
это и есть разность между количеством путей, заканчивающихся не ниже диагонали, и числом путей, заканчивающихся ниже прямой 
где квадратные скобки обозначают целую часть.
Опишите множество всех последовательностей из букв a и b таких, что в любом наборе подряд идущих символов (длины больше 1) букв a не меньше, чем букв b
Обратите внимание! В отличие от предыдущей задачи, рассматриваются не только начальные отрезки последовательности, а вообще любые!
Для описания используйте формулы, которые называются регулярными выражениями.
Так для повторения блока из нескольких букв используйте операцию "звездочка" (итерация), например, (abb)* задает множество слов {пустое слово, abb, abbabb, abbabbabb, ...} Умножение множеств (эту операцию, как обычно в алгебре, изображают точкой или вообще опускают, что мы и будем делать), описывает склейку всех слов первого множества со словами второго (третьего и т. д.), например a*cb* обозначает множество слов: {с, ac, cb, acb, aac, ..., aaa...acb.. b, ...}. Обратите внимание что слова, в которых нет букв a или b, получаются за счет того, что результат итерации может не содержать символов, то есть быть пустым словом.
Последней операцией, которая используется в формулах, является сложение. Сложение соответствует объединению множеств. Так обозначение (a + b) c + d(ac*+) описывает множество всех последовательностей из букв a и b (обозначается (a + b)*), к концу которых присоединена буква c, объединенного с множеством слов, начинающихся с буквы d, за которой следует буква a, а за ней любое число букв c и ещё одним однобуквенным словом (d умножить на пустое слово — это d).
Слева приведены примеры слов, которые удовлетворяют нашему условию, справа примеры слов, которые не удовлетворяют ему. Благодаря подсветке вы можете видеть, какие из этих примеров и контрпримеров удовлетворяют построенному вами выражению, а какие — нет.
Опишите множество всех последовательностей из букв a и b таких, что в любом наборе подряд идущих символов (длины больше 1) букв a не меньше, чем букв b.
Данная схема состоит из вершин (называемых состояниями) и стрелок, символизирующих правила, по которым работает эта схема. Схема начинает работу в начальном состоянии S0, выделенном оранжевым. Поступающее на ход слово анализируется посимвольно. При рассмотрении каждого символа мы переходим из текущего состояния по стрелочке, над которой написан этот символ.
После того, как всё слово проанализировано, мы заканчиваем работу в одном из состояний. Некоторые состояния необходимо пометить как конечные (жирная каёмка). Это те состояния, в которых мы оказываемся, проанализировав нужные слова.
Постройте машину Тьюринга, которая в любую последовательность из букв a и b добавляет буквы a так, чтобы между любыми буквами b было бы хотя бы две буквы a.
Например, последовательность babba должна превратиться в baabaaba Начальное состояние s, конечное f.
