Задачи по информатике

Здесь мы приводим 27 задач по информатике. Задачи будут как простые (для школьников 6-го класса и младше), так и сложные, уровень которых соответствует школьным и студенческим олимпиадам по программированию. Примерная сложность указана в круглых скобках после номера задачи - это число от 1 до 20. Можно считать, что сложность от 8 до 11 примерно соответствует номеру класса средней школы. Кроме того, после номера задач следуют буквы, определяющие раздел информатики:

Полный текст опубликован в Интернет-журнале "Потенциал" External link mark

И = Теория информации и кодирования. К этому разделу относятся задачи, связанные с преобразованием информации и оценкой количества информации. В частности, в этом разделе будут задачи по теории сжатия данных, помехоустойчивого кодирования и теории защиты информации.

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

П = Языки и технологии программирования. Информатика - наука, возникшая из необходимости решать конкретные практические задачи, и практическая часть науки о компьютерах велика и сильно востребована. Эту часть обычно называют технологии программирования, отделяя её от теории программирования (theoretical computer science). Буквой П мы будем помечать задачи, для решения которых необходимо что-то запрограммировать или задействовать какие-либо специальные компьютерные технологии.

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

В = Теория вычислений и вычислимых функции. Этот раздел посвящен вычислимости и невычислимости, а также различным абстрактным вычислительным машинам, конечным автоматам, машинам Тьюринга, алгорифмам Маркова и др. Кроме того, мы будем использовать буквы для обозначения типа задач: М - для решения задачи пригодятся математические знания, Ф - для решения задачи пригодятся физические знания, Т - задача подразумевает творческий подход, Г - задача связанна с компьютерной графикой. Мы будем стараться по возможности указывать авторов задач. В случае, если задача игралась на одной из олимпиад, мы будем давать соответствующую ссылку. В данном выпуске большая часть задач классические, и авторство определить сложно. Мы с удовольствием опубликуем ваши задачи. Присылайте яркие интересные задачи, по возможности, с простым, ясным условием и простым, но нестандартным или красивым и поучительным решением.

Удачи! Присылайте свои решения на problems@potential.org.ru. Конкурс решения первых 27 задач будет длиться до 30 сентября 2005 г. По итогам конкурса будут призы.