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

1. Реализовать программу для форматирования текстовых файлов. В простейшем варианте она должна из входного файла, состоящего из строк-параграфов (т.е. одна длинная строка — один параграф, как получается при экспорте из M$ Word в текстовой файл), делать файл, в котором длина каждой строки не превышает заданого числа (если это возможно), а каждый абзац начинается с символа табуляции. Возможные усложнения: реализовать отсечение неправильных символов (список таких символов задаётся), сделать проверку орфографии по словарю, реализовать расстановку переносов, реализовать переформатирование конечного текста под другую длину строки.
2. Реализовать программу для перекодировки между различными кириллическими кодовыми таблицами (CP866, CP1251, KOI8-R). Программа должна иметь опцию автоматического распознавания исходной кодировки файла (например, на основании частотной таблицы символов) и уметь отличать двоичные файлы от текстовых, не перекодируя первые (но иметь опцию форсированной перекодировки).
3. Реализовать программу для форматирования исходных текстов программ на языке C. В качестве усложнённого варианта можно предусмотреть вывод отформатированного текста в формате RTF с подсветкой синтаксических элементов языка.
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) — численность жертв, y(t) — численность хищников, a₁(a₂) — относительная скорость размножения жертв (гибели хищников), b₁ и b₂ — естественные скорости вымирания популяций жертв и хищников, c₁(c₂) — коэффициент гибели (прироста) популяции жертв (хищников) при взаимодействии хищников и жертв.
    Требуется написать программу для решения уравнений модели и визуализации поведения системы во времени и, варьируя коэффициенты при различных членах и начальные условия, установить возможные сценарии развития системы хищников и жертв.
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. Написать программу визуализации фрактального множества Ньютона (множества притяжения корней схемы Ньютона) для любого заданного полинома. Сам полином задается с клавиатуры.