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

  1. Реализовать программу для форматирования текстовых файлов. Базовая функциональность:
    • входной файл, состоящий из строк-параграфов (т.е. одна длинная строка — один параграф, как получается при экспорте из M$ Word в текстовой файл), преобразуется в файл, в котором длина каждой строки не превышает заданого числа (если это возможно), а каждый абзац начинается с задаваемой комбинации символов.
    • отсечение неправильных символов (список таких символов задаётся): если какой-то из заданых символов присутствует во входном файле, то он не принимается во внимание,
    • реализовать переформатирование конечного текста под другую длину строки и другую начальную комбинацию символов в начале параграфа (предыдущая комбинация может задаваться в качестве параметра программы, но можно попробовать сделать автоматическое распознавание этой комбинации).
    Дополнительная функциональность:
    • сделать проверку орфографии по словарю,
    • реализовать расстановку переносов.
  2. Реализовать программу для перекодировки между различными кириллическими кодовыми таблицами (CP866, CP1251, KOI8-R). Программа должна иметь опцию автоматического распознавания исходной кодировки файла (например, на основании частотной таблицы символов) и уметь отличать двоичные файлы от текстовых, не перекодируя первые (но иметь опцию форсированной перекодировки).
  3. Реализовать программу для форматирования исходных текстов программ на языке C. В качестве усложнённого варианта можно предусмотреть вывод отформатированного текста в формате RTF или HTML с выделением синтаксических элементов языка.
  4. Написать программу для упрощения символьных арифметических выражений и вычисления их значений. Например выражение «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)».
  5. Лысенко
    Написать программу под Windows, которая рисует графики функций. Функция задаётся в обычном виде, например 2*x + sin((1+x)/(1-x)) + 2^x. Программа должна уметь масштабировать график произвольным образом, задавать цвета фона, осей и графика, иметь функцию автомасштабирования по оси Y, уметь прогкручивать график по вертикали и горизонтали. Будет хорошо, если для неограниченных функций (например ctg(x) при x=0) программа рисовала в точке обращения в бесконечность вертикальную пунктирную линию.
  6. Не пользуясь никакими стандартными библиотеками для работы с трёхмерной графикой, реализовать программу визуализации трёхмерной сцены методом обратной трассировки лучей. Минимальные требования: наличие текстур и хотя бы одного источника цвета. Варианты расширения программы: добавление зеркал, преломляющих объектов, тумана и т.д.
  7. Ионов
    Реализовать программу для игры в «точки» с человеком.
  8. Написать программу, визуализирующую движение грузика, к которому прикреплены три пружинки различных жесткостей, закреплённые в вершинах произвольного треугольника. Исходными данными для программы являются начальное отклонение и скорость грузика. Вся система трёхмерна, т.е. начальное отклонение грузика может не лежать в плоскости треугольника, поэтому можно предусмотреть изменение точки и угла взгляда на систему.
  9. Визуализировать движение в системе трёх тел Солнце - Земля - Луна. Все тела взаимодействуют по закону тяготения, исходными данными являются начальные положения и скорости планет. Все тела имеют конечные массы.
  10. Левченко
    Задача от А. В. Кондратьева. Разработка программы для демонстрации сложения цилиндрических волн от двух источников и влияние когерентности источников на результат. Должна быть предусмотрена возможность задания начальных фаз источников и возможность «случайной» сбивки фазы какого-либо источника по запросу пользователя.
  11. Моделирование биологической системы хищник-жертва в модели Лотка-Вольтерра. Уравнения модели:
    x'=a1x - c1xz - b1x2,
    z'=-a2z + c2xz - b2z2,
    где x(t) — численность жертв, z(t) — численность хищников, a1(a2) — относительная скорость размножения жертв (гибели хищников), b1 и b2 — естественные скорости вымирания популяций жертв и хищников, c1(c2) — коэффициент гибели (прироста) популяции жертв (хищников) при взаимодействии хищников и жертв.
    Требуется написать программу для решения уравнений модели и визуализации поведения системы во времени и, варьируя коэффициенты при различных членах и начальные условия, установить возможные сценарии развития системы хищников и жертв.
  12. Написать HTTP/FTP/POP3-сервер. Конкретная спецификация сервера оговаривается при личной беседе.
  13. Волкова
    Написать программу для составления японского кроссворда по задаваемой пользователем картинке.
  14. Карпов
    Не привлекая никаких стандартных средств написать простой (или не очень простой) текстовой редактор.
  15. Марченков
    Реализовать архиватор или виртуальную файловую систему.
  16. Серебряная
    Смоделировать движение заряженной частицы в скрещенных постоянных электрическом и магнитном полях.
  17. Светогоров
    Реализовать программу, составляющую расписание занятий в школе. Заданы: список кабинетов и предметов, занятия по которым могут быть проведены в каждом из них, список учителей, у каждого из которых есть список дней и часов на неделе, в которые они могут проводить занятия и список классов, у каждого из которых есть фиксированный набор уроков. Требуется найти все варианты расписания на неделю.
  18. Реализовать препроцессор для языка «Small C», способный обрабатывать директивы #include, #define, #undef и конструкцию #if — #else — #endif.
  19. Ивашинин
    Реализовать программу поиска сочетания символов в строке. В сочетании символов могут входить метасимволы (wildcards) «?» и «*», означающее соответственно, один любой символ и любую последовательность символов.
  20. Написать программу, расставляющую заданную комбинацию пятнашек в нормальном порядке. Обратите внимание, что некоторые входные последовательности не являются разрешимыми.
  21. Реализовать программу, рассчитывающую сопротивление между двумя точками электрической схемы сопротивлений. Программа должны уметь визуализировать схему, и было бы хорошо, если бы она умела её строить и редактировать.
  22. Ионова
    Программа-календарь, рисующая календарь на любой месяц любого года. Месяц задаётся либо в виде месяц/год, либо день года/год, либо количеством дней, прошедших с определённой даты.
  23. Васильева
    Программа, визуализирующая движение в системе двух маятников, грузы которых связаны пружиной. Задаются: ускорение свободного падения, массы грузов, длина подвеса маятников, жесткость пружины, начальные положения и скорости грузов. Требуется визуализировать саму систему и нарисовать графики зависимости координат грузов от времени и зависимости энергий грузиков и полной энергии системы от времени.
  24. Реализовать игру в крестики-нолики на бесконечном поле. Для выигрыша необходимо зачеркнуть заданное количество символов по диагонали, вертикали или горизонтали. Программа должна играть против человека и желательно, чтобы она, как минимум, не проигрывала.
  25. Заболотский
    Написать программу визуализации фрактального множества Ньютона (множества притяжения корней схемы Ньютона) для любого заданного полинома. Сам полином задается с клавиатуры.
  26. Николаев
    Написать простой (или не очень) пискельный графический редактор. Минимальные требования:
    • рисование точками и ломаными линиями с возможностью выбора цвета и толщины пера,
    • рисование прямоугольников и эллипсов,
    • заливка областей равномерным цветом,
    • сохранение/загрузка шедевров в формат BMP.
  27. Написать простой (или не очень) векторный графический редактор. Минимальные требования:
    • набор примитивов: точка, линия, эллипс, многоугольник,
    • для примитивов дополнительно задаются: цвет и толщина линии, цвет заливки (может быть прозрачным),
    • сохранение/загрузка шедевров в собственный формат, экспорт шедевров в формат BMP.
  28. Написать программу, визуализирующую процесс сортировки массива чисел с помощью бинарного дерева. Должны быть предусмотрены режимы пошаговой сортировки и выполнение шагов сортировки через заданный интервал времени.
  29. Лазаренко
    Программа для игры в шашки с человеком.
  30. Карташов
    Программа-ежедневник: планирование собственного времени. Программа должна уметь:
    • создавать события произвольной длительности, у которых указывается начальное и конечное время, примечание, флаг и время напоминания,
    • изменять все характеристики событий,
    • удалять конкретные события или события, находящиеся в заданном интервале времени.
    • сохранять/загружать базу ежедневника.
  31. Написать HTML-чат — сервис, позволяющий людям общаться на Web-сервере в реальном времени. Точные условия задачи обговариваются лично.
  32. Написать программу для сжатия/распаковки звуковых файлов в (почти) реальном времени. Формат файла и алгоритм сжатия придумывается и реализуется автором. Возможно использовать уже существующие алгоритмы сжатия, но их реализация должна быть собственной. (Привет Тимуру Исходжанову!)
  33. Реализовать программу для визуализации падения точечных предметов заданной массы на поверхность жидкости. Считается, что предмет, соприкоснувшись с поверхностью воды, «исчезает», то есть исключается из рассмотрения. Коэффициент поверхностного натяжения должен задаваться пользователем. Для визуализации поверхности жидкости допустимо использовать стандартные библиотеки для работы с трехмерной графикой. (Привет Павлу Логинову!)
  34. Написать UN*X-интерпретатор (shell). Минимальные требования:
    • запуск команд,
    • реализация конвейера и перенаправления дескрипторов в файл и в другие дескрипторы,
    • возможность запуска программ в фоновом режиме.
    Дополнительные возможности:
    • использование переменных окружения: возможность задания их значений и подстановка значения переменных вместо конструкции $имя_переменной,
    • управляющие конструкции: if—elif—else, for—do—done, while—do—done.
    Для уяснения всего вышесказанного можно почитать man-страницу для команды sh. (Привет Владимиру Шашкину!)
  35. Одинцов
    Программа для решения классической задачи о ранце: есть ранец заданного объёма и набор предметов, у каждого из которых задан объём и ценность. Количество предметов одного типа неограничено. Требуется заполнить ранец предметами так, чтобы суммарная ценность находящихся предметов была максимальной. Рекурсивный алгоритм решения задачи не приветствуется.

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

  36. Написать программу, реализующую сервер передачи сообщений: есть много клиентов, которые хотят передавать друг другу сообщения через выделенный сервер, который предоставляет такую возможность. Клиенты общаются только с сервером, но не друг с другом напрямую. Общение клиента с сервером происходит с помощью протокола TCP/IP.
  37. Написать программу, подсчитывающую размерность Хаусдорфа-Безиковича для следующих фракталов: снежинка Коха, салфетка Серпинского, множество Жюлиа, множество Мандельброта.
  38. Арифметические операции в системе чисел Фибоначчи. Утверждение: любое неотрицательное число может быть представлено в виде суммы членов вида akCk, где ak может принимать значения 0 или 1, а Ck — k-е число Фибоначчи. Если наложить для всех k условие ak*ak+1=0, то разложение будет единственным.

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

  39. Пахомова
    Программа для вычисления площади и визуализации произвольного замкнутого многоугольника на плоскости. Вершины многоугольника задаются щелчком мыши, после добавления новой вершины многоугольник перерисовывается и его площадь пересчитывается. Вершины, находящиеся внутри многоугольника, должны отбрасываться.
  40. Программа для просмотра текстовых файлов. Программа должна уметь «листать» файл в прямом и обратном направлении. Должны быть реализованы функции прокрутки содержимого вверх и вниз на одну строку и на один экран. Эти функции могут быть назначены произвольным клавишам, что регламентируется файлом конфигурации следующего вида: 
    bind q	quit
bind f  line-forward
bind b	line-backward
bind n	screen-forward
bind p	screen-backward
    Если какая-то строка в файле слишком длинна для отображения в одной строке экрана, то эта строка должна быть размещена на нескольких экранных строках. Команды прокрутки на экран вверх/вниз оперируют с экранными строками.
  41. Реализовать базу данных ваших любимых фильмов/компакт-дисков/игр. У базы данных должна быть определённая структура, задающаяся в виде 
    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» при определении структуры базы.

  42. Игра «Тетрис». Фигуры трёхмерны, но падают в плоскости. Необходимо предусмотреть статическое вращение игровой плоскости в пространстве.
  43. Духовенский
    Космическая стратегия «Кто к нам с чем зачем, тот от того и того».
  44. Средневековая стратегия «Герои не нашего времени».
  45. Калейдоскоп.
  46. Романов
    Написать программу, моделирующую движение маятника Гюйгенса. Проверить изохронность маятника и визуализировать его движение.
  47. Не пользуясь сторонними библиотеками для работы с трехмерной графикой, написать программу, визуализирующую вращение платоновых тел. Сами платоновы тела являются тремерными объектами и обладают собственными текстурами. Программа должна уметь удалять невидимые грани, рисовать текстуры на объектах и отображать картинку плавно, без видимого мерцания.
  48. Аулов
    Пошаговая стратегия «Двигаем человечков на суше и на море». Игра предусматривает наличие нескольких команд, сражающихся друг с другом в пошаговом режиме на некоторой местности.

    Местность состоит из кусочков различного типа (обычная земля, болото, песок. вода, …), обладающих различными характеристиками с точки зрения скорости передвижения и защиты персонажа. На местности могут встречаться искуственные предметы типа стен, бочек (возможно, взрывающихся), боеприпасов и т.д.

    Наличие минимального искуственного интеллекта и игры с компьютером — приветствуется, наличие продвинутого интеллекта и звуков — по желанию.

    Также в программе должнен присутствовать графический редактор карт.

  49. Куличенко
    Написать программу-бот для игры в Bejeweled 2 с сайта king.com.