Практика

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

Симулятор морских боев

Руководитель: Е. М. Линский

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

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

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

Возможные расширения:

1. увеличение числа игроков
2. возможность автоматического проведения турниров между стратегиями

Каталог библиотеки статей

Руководитель: Е. М. Линский

Есть большая библиотека документов в формате PDF. Требуется создать приложение для работы с каталогом библиотеки. Каталог хранит описание документа (авторы, название, год и т. д.) и путь до него на диске. Для удобства просмотра каждому документу может быть присвоена категория, характеризующая область знаний к которой он относится. Категории образуют иерархию в виде дерева. Одному документу может быть присвоено несколько категорий.

Приложение должно поддерживать следующую минимальную функциональность:

1. Редактирование описаний документов из библиотеки.
2. Редактирование дерева категорий.
3. Редактирование привязки категорий к документам.
4. Просмотр каталога по дереву категорий.
5. Поиск по каталогу: по отдельным полям, по всем полям. Поддержка масок *,?.
6. При просмотре элемента каталога все поля должны быть представлены как ссылки. Нажатие на ссылку приводит к поиску по значению поля, т.е. если нажать на имя автора, то должны быть выданы все статьи этого автора.

Возможные расширения:

1. Из некоторых PDF можно извлечь текст. Сделать полнотекстовой поиск по тексту. Автоматическое извлечение описания документа (имя автора, название) при добавлении документа в каталог.
2. Добавление ключевых слов в дополнение к категориям. Ключевые слова не образуют иерархий.
3. Синхронизация нескольких каталогов. Экспорт каталога в текстовый файл, импорт из файла. Поиск различий в двух файлах.
4. Автоматическая проверка целостности ссылок на документы (т. е. действительно ли указан правильный путь к файлу).
5. Экспорт элементов каталога в формате bibtex.

Определитель плагиата в рефератах

Руководитель: Е. М. Линский

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

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

В качестве базовой может быть использована следующая идея. Текст документа хэшируется с некоторым шагом. Текст разбивается на блоки с перекрытием. Например, пусть длина блока равна 20, а шаг равен 2. Тогда первый блок находится на позициях 1..20, второй блок — 3..22 и т.д. От каждого блока вычисляется хэш-функция. Из набора получившихся значений выбирается часть (например, 15 максимальных), эти значения вместе со ссылкой на документ сохраняются. При анализе на плагиат хэш-значения рассматриваемого документа последовательно сравниваются со всеми записями в базе. Если некоторое число хэшей анализируемого документа (например, 7 из 15) совпало с хэшами какого-то документа из базы, то выносится решение о плагиате.

Возможные расширения:

1. в целях быстродействия база данных является распределенной, т.е. находится на нескольких компьютерах.
2. веб-интерфейс вместо графического клиента (см. тему #2 для требований к разработчикам веб-интерфейсов).

Игры с искусственным интеллектом

Руководитель: Е. М. Линский

1. Хексагон
2. Шашки
3. Шахматы
4. Нарды
5. Го (игра в точки)

FBReader Translator

Руководитель: Н. М. Пульцин

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

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

Время от времени авторы переводов берутся добавить недостающие строки, и перед ними возникает проблема — найти, какие строки были добавлены в английском варианте, и в соответствующие места добавить строки на языке перевода.

Предлагается написать программу, позволяющую

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

Словарь

Руководитель: Н. М. Пульцин

Написать программу-словарь, позволяющую пользоваться словарями в формате

1. bedic
2. sdictionary

Примерные возможности, которые хотелось бы увидеть в программе, можно посмотреть, например, у Lingvo ;).

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

Интерфейс для архиватора

Руководитель: А. А. Бреслав

Написать программу-оболочку для работы с архивами, поддерживающую следующие функции:

1. Просмотр содержимого архива (файлы и папки)
2. Создание нового архива
3. Добавление файлов в архив
4. Удаление файлов из архива

В качестве формата архивов можно выбрать формат, основанный на алгоритме Хаффмана (написанном в первом семестре), или стандартный Zip, реализованный в библиотеке Java.

Просмотр изображений в формате SVG

Руководитель: А. А. Бреслав

SVG (Scalable Vector Graphics) — стандартный формат для хранения векторных изображений, основанный на XML.

Необходимо написать программу для просмотра SVG-документов, позволяющую

1. Масштабировать изображение
2. Прокручивать изображение
3. Просматривать изображения с диска в режиме слайд-шоу

Японские кроссворды

Руководитель: А. А. Бреслав

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

Кроссворд хранится на диске в виде

1. текстового файла с картинкой в стиле ASCII-art
   
2. файла, содержащего информацию о количестве закрашенных клеток в каждой строке и каждом столбце

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

Есть вариант этой задачи про цветные японские кроссворды.

Обыкновенные кроссворды

Руководитель: А. А. Бреслав

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

Кроссворд хранится на диске в вид файла с вопросами и? положениями слов. Программа отображает кроссворд на экране и позволяет пользователю вписывать буквы в клетки.

Есть варианты этой задачи про "сканворды" или "филворды".

Векторная анимация

Руководитель: А. А. Бреслав

Векторное изображение состоит из геометрических объектов: точек, многоугольников, эллипсов, отрезков прямых и кривых и т.д.

Если задать начальное изображение и указать, каким образом оно изменяется со временем (объекты могут перемещаться, изменять цвет и размеры и т. д.), получится анимация.

С этим может быть связаны следующие задачи:

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

Логические схемы

Руководитель: А. А. Бреслав

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

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

Задача: написать программу, позволяющую создавать схемы, подавать на их входы данные и получать результат.

Блок-схемы

Руководитель: А. А. Бреслав

Блок схемы используются для наглядного представления небольших программ и алгоритмов.

Задача: написать редактор и интерпретатор блок-схем.

Конечные автоматы

Руководитель: А. А. Бреслав

Конечные автоматы широко используются в компиляторах и программах, управляющих различными автоматическими системами (от кофеварок до подводных лодок). Автомат можно представить в виде графа, вершинами которого являются состояния, а ребрами — переходы из одного состояния в другое. Подробнее см. статью в Википедии.

Задача: написать редактор и интерпретатор конечных автоматов.

Синтаксические диаграммы

Руководитель: А. А. Бреслав

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

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

Роботы

Руководитель: А. А. Бреслав

Создать маленький язык программирования для управления "роботом", двигающимся по экрану.
Возможные варианты сюжета:

1. рисующий робот (как черепашка в LogoWriter)
2. робот на поле с преградами и призами (лабиринт)
3. робот-строитель

Зависимости в программах на Java

Руководитель: А. А. Бреслав

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

В случае Java такими частями будут классы и пакеты: практически каждому классу для работы нужны классы стандартной библиотеки, но многим классам этого недостаточно: они обращаются к другим классам в том же проекте.

Нужно написать программу, позволяющую по скомпилированному коду построить граф, вершинами в котором будут классы и пакеты, а ребрами — зависимости.
Входными данными для программы будет корневой пакет (в виде папки на диске или jar-архива).

Надстройка над Google Calendar

Руководитель: А. А. Бреслав

Google Calendar — это веб-приложение, позволяющее пользователю планировать свое время: назначать события на определенные часы и просматривать календарь в виде удобно скомпонованной таблицы.

Для планирования встреч со студентами преподавателю требуется следующая функция: определить фиксированные промежутки времени, в которые происходят встречи (например, первая встреча с 13.20 до 14.00, вторая — с 14.00 до 14.40, третья — с 15.00 до 16.40 и т.д.) так, чтобы можно было создать событие, не определяя время его начала и конца, а просто выбирая один из заранее определенных промежутков времени. Кроме того, данные студента (фамилию, имя и группу) тоже хотелось бы выбирать из заранее определенного списка.

Эту функциональность можно интегрировать с Google Calendar следующим образом: настольное Java приложение позволяет пользователю определять промежутки времени, список студентов и назначать встречи. Когда назначается встреча, данные отсылаются в Google Calendar через Google Data API. Также необходимо уметь считывать из календаря уже внесенные туда данные.

Инструмент для составления расписаний

Руководитель: А. А. Бреслав

Составление расписания занятий — очень сложная задача, которую не удается эффективно решать автоматически. Однако программа может помочь пользователю составлять расписание, проверяя за него отсутствие накладок, предлагая возможные варианты изменений и представляя данные в удобном виде.

Нужно написать программу, позволяющую редактировать расписание в одном из трех представлений

1. Расписание студентов
2. Расписание преподавателей
3. Расписание аудиторий

Программа должна позволять задавать ограничения и проверять, что они выполняются, например

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

Редактор графов с поддержкой шаблонов

Руководитель: А. А. Бреслав

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

Предлагается написать редактор с поддержкой "шаблонов" для графов.

Например, шаблон "вершина двоичного дерева" позволяет создать не более трех вершин, связанных с данной, причем две из них будут располагаться ниже данной (на равном расстоянии от нее по горизонтали), а третья — выше.

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

Инструмент переводчика

Руководитель: А. А. Бреслав

Необходимо написать инструмент для CAT (Computer Assisted Translation), то есть программу, которая помогает переводчику в его работе.

Программа должна поддерживать следующие функции

1. Одновременное отображение оригинального текста и перевода на экране
2. Выделение части оригинального текста для сопоставления ей перевода
3. Хранение истории замен: какие слова были заменены какими
4. Поиск и замена с поддержкой специальных символов
5. Автоматический поиск в тексте фрагментов, которые не нужно переводить
6. Хранение базы данных переводов слов и выражений