Экзамен 2006 года, предлагаемые задачи

Реализовать программу для форматирования текстовых файлов. Базовая функциональность:

входной файл, состоящий из строк-параграфов (т.е. одна длинная строка — один параграф, как получается при экспорте из M$ Word в текстовой файл), преобразуется в файл, в котором длина каждой строки не превышает заданого числа (если это возможно), а каждый абзац начинается с задаваемой комбинации символов.
отсечение неправильных символов (список таких символов задаётся): если какой-то из заданых символов присутствует во входном файле, то он не принимается во внимание,
реализовать переформатирование конечного текста под другую длину строки и другую начальную комбинацию символов в начале параграфа (предыдущая комбинация может задаваться в качестве параметра программы, но можно попробовать сделать автоматическое распознавание этой комбинации).

Дополнительная функциональность:

сделать проверку орфографии по словарю,
реализовать расстановку переносов.

Реализовать программу для перекодировки между различными кириллическими кодовыми таблицами (CP866, CP1251, KOI8-R). Программа должна иметь опцию автоматического распознавания исходной кодировки файла (например, на основании частотной таблицы символов) и уметь отличать двоичные файлы от текстовых, не перекодируя первые (но иметь опцию форсированной перекодировки).

Реализовать программу для форматирования исходных текстов программ на языке C. В качестве усложнённого варианта можно предусмотреть вывод отформатированного текста в формате RTF или HTML с выделением синтаксических элементов языка.

Морозов

Написать программу для упрощения символьных арифметических выражений и вычисления их значений. Например выражение «2 + b - 5 / 2 - 3 * d» можно упростить до «b - 3 * d - 0.5», выражение «a + 0 + 2 * a» — до «3 * a», а «1 / (1 + x) + 1 / (1 - x)» — до «2 / (1 - x^2)».

Журавлев (А)

Написать программу под Windows, которая рисует графики функций. Функция задаётся в обычном виде, например 2*x + sin((1+x)/(1-x)) + 2^x. Программа должна уметь масштабировать график произвольным образом, задавать цвета фона, осей и графика, иметь функцию автомасштабирования по оси Y, уметь прогкручивать график по вертикали и горизонтали. Будет хорошо, если для неограниченных функций (например ctg(x) при x=0) программа рисовала в точке обращения в бесконечность вертикальную пунктирную линию.

Шуров

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

Реализовать программу для игры в «точки» с человеком.

Дубов

Написать программу, визуализирующую движение грузика, к которому прикреплены три пружинки различных жесткостей, закреплённые в вершинах произвольного треугольника. Исходными данными для программы являются начальное отклонение и скорость грузика. Вся система трёхмерна, т.е. начальное отклонение грузика может не лежать в плоскости треугольника, поэтому можно предусмотреть изменение точки и угла взгляда на систему.

Парфёнов

Визуализировать движение в системе трёх тел Солнце - Земля - Луна. Все тела взаимодействуют по закону тяготения, исходными данными являются начальные положения и скорости планет. Все тела имеют конечные массы.

Муратов

Задача от А. В. Кондратьева. Разработка программы для демонстрации сложения цилиндрических волн от двух источников и влияние когерентности источников на результат.

Петухов

Моделирование биологической системы хищник-жертва в модели Лотка-Вольтерра. Уравнения модели:

x'=a₁x - c₁xz - b₁x²,

z'=-a₂z + c₂xz - b₂z²,

где x(t) — численность жертв, z(t) — численность хищников, a₁(a₂) — относительная скорость размножения жертв (гибели хищников), b₁ и b₂ — естественные скорости вымирания популяций жертв и хищников, c₁(c₂) — коэффициент гибели (прироста) популяции жертв (хищников) при взаимодействии хищников и жертв.
Требуется написать программу для решения уравнений модели и визуализации поведения системы во времени и, варьируя коэффициенты при различных членах и начальные условия, установить возможные сценарии развития системы хищников и жертв.

Написать HTTP/FTP/POP3-сервер. Конкретная спецификация сервера оговаривается при личной беседе.

Написать программу для составления японского кроссворда по задаваемой пользователем картинке.

Не привлекая никаких стандартных средств написать простой (или не очень простой) текстовой редактор.

Ольшанский

Реализовать архиватор или виртуальную файловую систему.

Ляпин

Смоделировать движение заряженной частицы в скрещенных постоянных электрическом и магнитном полях.

Рапопорт

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

Реализовать препроцессор для языка «Small C», способный обрабатывать директивы #include, #define, #undef и конструкцию #if — #else — #endif.

Реализовать программу поиска сочетания символов в строке. В сочетании символов могут входить метасимволы (wildcards) «?» и «*», означающее соответственно, один любой символ и любую последовательность символов.

Кузнецов

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

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

Ищук

Программа-календарь, рисующая календарь на любой месяц любого года. Месяц задаётся либо в виде месяц/год, либо день года/год, либо количеством дней, прошедших с определённой даты.

Хасанова

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

Киселев

Реализовать игру в крестики-нолики на бесконечном поле. Для выигрыша необходимо зачеркнуть заданное количество символов по диагонали, вертикали или горизонтали. Программа должна играть против человека и желательно, чтобы она как минимум не проигрывала.

Янушевич

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

Смирнов

Написать простой (или не очень) пискельный графический редактор. Минимальные требования:

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

Коробченко

Написать простой (или не очень) векторный графический редактор. Минимальные требования:

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

Трефилов

Написать программу, визуализирующую процесс сортировки массива чисел с помощью бинарного дерева. Должны быть предусмотрены режимы пошаговой сортировки и выполнение шагов сортировки через заданный интервал времени.

Журавлёв (Л)

Программа для игры в шашки с человеком.

Программа-ежедневник: планирование собственного времени. Программа должна уметь:

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

Написать HTML-чат — сервис, позволяющий людям общаться на Web-сервере в реальном времени. Точные условия задачи обговариваются лично.

Написать программу для сжатия/распаковки звуковых файлов в (почти) реальном времени. Формат файла и алгоритм сжатия придумывается и реализуется автором. Возможно использовать уже существующие алгоритмы сжатия, но их реализация должна быть собственной. (Привет Тимуру Исходжанову!)

Реализовать программу для визуализации падения точечных предметов заданной массы на поверхность воды. Считается, что предмет, соприкоснувшись с поверхностью воды, «исчезает», то есть исключается из рассмотрения. Коэффициент поверхностного натяжения должен задаваться пользователем. Для визуализации поверхности воды допустимо использовать стандартные библиотеки для работы с трехмерной графикой. (Привет Павлу Логинову!)

Написать UN*X-интерпретатор (shell). Минимальные требования:

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

Дополнительные возможности:

использование переменных окружения: возможность задания их значений и подстановка значения переменных вместо конструкции $имя_переменной,
управляющие конструкции: if—elif—else, for—do—done, while—do—done.

Для уяснения всего вышесказанного можно почитать man-страницу для команды sh. (Привет Владимиру Шашкину!)

Грамматикати

Программа для решения классической задачи о ранце: есть ранец заданного объёма и набор предметов, у каждого из которых задан объём и ценность. Количество предметов одного типа неограничено. Требуется заполнить ранец предметами так, чтобы суммарная ценность находящихся предметов была максимальной. Рекурсивный алгоритм решения задачи не приветствуется.

Программа должна визуализировать заполненный ранец, например как последовательность параллелепипедов, высота которых отражает ценность предмета, а длина — объём предмета.

Написать программу, реализующую сервер передачи сообщений: есть много клиентов, которые хотят передавать друг другу сообщения через выделенный сервер, который предоставляет такую возможность. Клиенты общаются только с сервером, но не друг с другом напрямую. Общение клиента с сервером происходит с помощью протокола TCP/IP.

Галкин

Написать программу, подсчитывающую размерность Хаусдорфа-Безиковича для следующих фракталов: снежинка Коха, салфетка Серпинского, множество Жюлиа, множество Мандельброта.

Арифметические операции в системе чисел Фибоначчи. Утверждение: любое неотрицательное число может быть представлено в виде суммы членов вида a_kC_k, где a_k может принимать значения 0 или 1, а C_k — k-е число Фибоначчи. Если наложить для всех k условие a_k*a_k+1=0, то разложение будет единственным.

Задание: написать программу, которая преобразует пару введённых десятичных чисел в систему Фибоначчи и производит над ними 4 арифметических действия используя только коэффициенты разложения этих чисел. То есть нельзя произвести 4 действия над исходными числами, а после этого преобразовать их в систему Фибоначчи.

Себедаш

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

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

bind q	quit
bind f  line-forward
bind b	line-backward
bind n	screen-forward
bind p	screen-backward

Если какая-то строка в файле слишком длинна для отображения в одной строке экрана, то эта строка должна быть размещена на нескольких экранных строках. Команды прокрутки на экран вверх/вниз оперируют с экранными строками.

Ртищев

Реализовать базу данных ваших любимых фильмов/компакт-дисков/игр. У базы данных должна быть определённая структура, задающаяся в виде

field "name"		type "char[20]"	default ""
field "quantity"	type "int"	default "0"
field "mark"		type "int"	default "3"

База данных должна реализовывать операции добавления новой записи («insert name="doom ]I[" type="junk" quantity=1»), удаления записей с данными характеристиками (например, «delete where name="warcraft" and mark="4"»), выбора записей (например, «select», выбирающую все записи, или «select where name="puzzle" or name="quest"»).

База должна проверять типы полей: если, например, полю «quantity» попытаться присвоить строку «test» или полю «name» попытаться присвоить значение «a very long string that will not fit to the 20 characters», то программа должна выдать сообщение об ошибке. Не указанные поля заполняются значениями по-умолчанию, заданными директивой «default» при определении структуры базы.

Сотсков

Игра «Тетрис». Фигуры трёхмерны, но падают в плоскости. Необходимо предусмотреть статическое вращение игровой плоскости в пространстве.

Горобцов

Космическая стратегия «Наш ответ Цивилизации Ориона».

Свешников

Средневековая стратегия «Герои не нашего времени».

Тарасова

Калейдоскоп.