python.task 2012-2013

Преподаватели: Журавлев Николай, Корнев Дмитрий, Берсенев Александр, Азовсков Сергей
Студент берет задачу самостоятельно.
Максимальное число студентов на задачу: 8
Если задача не будет оценена в течении 30 дней, то заявка отменяется автоматически.
После автоматической отмены заявки задачу можно будет взять через 14 дней.
У каждого студента может быть не более 2 неоцененных задач.

Общие требования


1. Документация, декомпозиция, help.
2. Тестирование.
3. Пакетные режимы.
4. Не использовать готовые модули, решающие существенную часть задачи.

Допуск к зачёту: 10 баллов
Допуск к экзамену: 40 баллов

Отчетность по курсу


Аттестация 1 семестр:
- 10 баллов

Допуск 1 семестр:
- 10 за python.task

Допуск 2 семестр:
- 40 за python.task

Формула для 1 семестра:
min(100, 6,5*task + 35*homework/homework_max + activity)

где:
* task - баллы за python.task;
* homework - баллы за домашние задачи;
* homework_max - максимальный балл, который можно получить за домашние задачи;
activity - баллы за работу на парах по практикам [0, 15] (10 за практику, 5 за теорию)

python-task {0, ...} * 6,5 (если балл больше 10, то либо требования 2 семестра, либо задачи больше не принимаются, либо понижение приоритета) [max = 65]
Биллинг
14
Вход: лог файл web-сервера и файл, описывающий стоимость того или иного
ресурса (формат данного файла разработать самостоятельно).
Выход: счета для каждого из пользователей с возможностью детализации.
Колосов Александр 03.04.2013 7 03.02.2014
Обработка текстов программ

Вход: программа на некотором императивном языке программирования и файл,
описывающий данный язык (способ описания разработать самостоятельно).
Написать:
- форматтер кода (с поддержкой нескольких стилей расстановки скобок)
- транслятор в гипертекст [20]
- PEP8 валидатор [20]

форматтер 15
Соболев Илья 20.02.2014 1 23.02.2014

PEP8 валидатор 8

транслятор 20
Пары слов
11
Вход: текст на русском языке и файл, содержащий список "не слов".
Программа должна построить список наиболее частых пар слов,
употребляемых в одной фразе (предложении), при этом слова могут быть
расположены в любом порядке в предложении. Из рассматриваемых слов
необходимо исключить все слова, указанные в списке "не слов".
Леденев Арсений 17.05.2013 10 02.06.2013
Бучельников Станислав 20.05.2013 11 04.06.2013
Меньших Иван 23.05.2013 8 01.06.2013
Гасников Даниил 23.05.2013 8 01.06.2013
Гусева Зинаида 28.05.2013 10 06.06.2013
Менщиков Александр 09.09.2013 11 12.01.2014
Мокрушина Анна 24.11.2013 11 12.01.2014
Сироткин Дмитрий 08.12.2013 11 13.01.2014
Кузнецов Ярослав 07.01.2014 5 12.01.2014
Взлом шифра
18
Вход: текст, зашифрованный произвольным подстановочным шифром.
Выход: оригинальное сообщение (возможна неполная дешифрация... с потерей баллов:).
Сироткин Дмитрий 05.01.2014 18 13.01.2014
Кузнецов Владимир 28.03.2014 18 04.04.2014
Леденев Арсений 01.04.2014 14 03.04.2014
Gilimkhanov Denis 03.04.2014 14 04.04.2014
Перевод документации в другой формат

Вход: документ в одном из следующих форматов:
- man
- python doc strings
Выход: документ в одном из следующих форматов:
- HTML [12]
- RTF
- PDF [20]
- XML

man2html 12

man2rtf 14

man2pdf 20

man2xml 14

docstrings2html 12
Гасников Даниил 21.12.2013 12 10.01.2014
Сагоян Арсен 13.01.2014 6 13.01.2014
Смирнова Анна 13.01.2014 6 13.01.2014

docstrings2rtf 14

docstrings2pdf 20

docstrings2xml 14
Генератор отчетов
14
Вход: формат отчета (язык описания разработать самостоятельно),
данные для подстановки.
Выход: набор заполненных отчетов.
Гусева Зинаида 12.09.2013 11 08.10.2013
Небо
20
Вход: база данных с описанием небесной сферы, координаты наблюдателя, угол обзора.
Программа должна позволять вращать наблюдателя, менять угол наклона его головы и
выводить на экран то, что он видит.
Примечание: данная программа предполагает визуализацию.
Примечание 2: база данных - ftp://shannon.usu.edu.ru/perl/data/stars.zip
Непочатова Алёна 13.11.2013 20 17.12.2013
Лесенка
9
Вход: исходное слово (например МУХА), целевое слово (например СЛОН) и словарь.
Выход: цепочка однобуквенных преобразований, позволяющая получить из
исходного слова целевое, при этом каждый промежуточный шаг должен также
являться словом (т.е. присутствовать в словаре).
Примечание: словарь - ftp://shannon.usu.edu.ru/perl/data/runouns.zip
Гладких Максим 11.04.2013 7 11.04.2013
Селезнев Никита 25.04.2013 9 21.05.2013
Дубинин Роман 07.05.2013 7 02.06.2013
Меньших Иван 10.05.2013 5 19.05.2013
Менщиков Александр 10.05.2013 7 21.05.2013
Мокрушина Анна 12.05.2013 9 02.06.2013
Макаркин Александр 04.06.2013 9 05.11.2013
Соболев Илья 12.06.2013 8 18.02.2014
Непочатова Алёна 01.07.2013 8 19.12.2013
Многочлены
12
Вход: 2 многочлена от нескольких переменных, заданных в математической
форме (т.е. знаки некоторых операций могут отсутствовать).
Выход: Указание ошибки в записи, если таковая присутствовала, иначе
сообщение о совпадении или несовпадении введенных многочленов.
Гусева Зинаида 08.05.2013 12 29.05.2013
Непочатова Алёна 12.05.2013 12 23.05.2013
Мокрушина Анна 12.05.2013 8 14.11.2013
Кузнецов Ярослав 12.05.2013 4 05.06.2013
Добрунов Александр 01.12.2013 8 20.12.2013
Митрофанова Елена 28.02.2014 12 07.04.2015
Gilimkhanov Denis 06.03.2014 7 07.03.2014
Палиндромы
8
Вход: текст на русском языке.
Выход: все палиндромы, построенные из слов данного текста.
Сироткин Дмитрий 09.04.2013 5 11.05.2013
Дубинин Роман 01.05.2013 7 31.05.2013
Меньших Иван 02.05.2013 8 10.05.2013
Смирнова Анна 07.05.2013 8 01.06.2013
Гладких Максим 17.05.2013 6 19.05.2013
Колосов Александр 18.05.2013 2 02.06.2013
Гасников Даниил 19.05.2013 8 23.05.2013
Менщиков Александр 21.05.2013 6 25.05.2013
Кроссворд
15
Вход: список слов и геометрия (описание внешнего вида кроссворда).
Выход: заполненный кроссворд (сообщение об ошибке, если заполнить невозможно).
Примечание: словарь - ftp://shannon.usu.edu.ru/perl/data/ruwords.zip.
Тарасов Кирилл 02.12.2013 15 13.01.2014
Добрунов Александр 18.12.2013 15 13.01.2014
Симоненко Алёна 04.01.2014 15 15.01.2014
Садовничая Евгения 05.01.2014 15 13.01.2014
Кузнецов Владимир 28.03.2014 10 03.04.2014
Кропанцев Никита 02.04.2014 14 04.04.2014
Отладчик
25
Вход: программа на языке Python.
Отладчик должен предоставить интерфейс пользователя, который позволяет
проделывать стандартные операции: просмотр текста программы, установка/снятие
точек останова (breakpoints), просмотр значения переменных (watch), пошаговое
выполение программы (trace), просмотр стека вызовов (call stack).
Игра

Написать программу, позволяющую играть с компьютером в одну из следующих игр:
- поддавки
- реверси
- 100-клеточные шашки
- шахматы [21]
Примечание: от компьютерного оппонента не требуется игра на уровне
гроссмейстера, минимум - умение компьютером совершать непротиворечащие
правилам ходы, а также правильно реагировать на игровую ситуацию (шах, мат и т.п.)

поддавки 17

реверси 17
Кузнецов Владимир 27.05.2013 12 04.04.2014
Колосов Александр 02.06.2013 5 06.06.2013
Кожин Константин 05.07.2013 17 24.12.2013
Гладких Максим 01.02.2014 14 04.02.2014
Дудин Артём 14.03.2014 1 14.03.2014

100-клеточные шашки 17
Селезнев Никита 27.02.2013 15 11.04.2013
Копылов Евгений 08.12.2013 12 18.12.2013
Чичагин Артём 18.12.2013 4 18.12.2013

шахматы 21
Дементьев Дмитрий 08.03.2013 20 19.09.2013
Тарасов Кирилл 06.05.2013 15 02.06.2013
Gilimkhanov Denis 04.11.2013 16 04.11.2013
Добрунов Александр 25.11.2013 17 17.12.2013
Соболев Илья 28.12.2013 4 13.02.2014
Бучельников Станислав 27.02.2014 10 21.03.2014
Лабиринт
10
Вход: файл с описанием лабиринта, начальная позиция, позиция выхода из
лабиринта и число бомб.
Выход: кратчайший путь от входа до выхода.
Примечание: бомба способна уничтожить одну стенку (т.е. сделать
смежными две соседние клетки, разделенные стеной).
Меньших Иван 02.05.2013 8 10.05.2013
Кузнецов Ярослав 22.12.2013 7 30.12.2013
Менщиков Александр 06.01.2014 10 13.01.2014
Смирнова Анна 11.01.2014 9 13.01.2014
Гладких Максим 04.02.2014 4 11.02.2014
Дефрагментация
25
Вход: образ диска с файловой системой FAT32.

Выход: дефрагментированный образ диска с файловой системой FAT32.

Примечание: таблица FAT32 может содержать ошибки (потерянные
кластеры, пересекающиеся цепочки).
Сортировки
12
Реализовать несколько алгоритмов сортировки массивов (квадратичные, Шелла,
Хоара, пирамидальная, слиянием) и сравнить их (числа сравнений и перестановок,
устойчивость, время работы) между собой и со встроенной функцией sort.
Селезнев Никита 24.04.2013 6 22.05.2013
Смирнова Анна 08.05.2013 6 01.06.2013
Садовничая Евгения 09.05.2013 6 21.05.2013
Менщиков Александр 10.05.2013 6 01.06.2013
Кузнецов Ярослав 12.05.2013 6 02.06.2013
Сироткин Дмитрий 22.05.2013 6 06.06.2013
Гусева Зинаида 17.09.2013 4 30.09.2013
Макаркин Александр 05.11.2013 3 05.11.2013
Жизнь
15
Написать программу, позволяющую задать начальную позицию, прокрутить время вперед,
проверить на отсутствие предыдущей позиции (сад Семирамиды).
Примечание: данная программа предполагает визуализацию при помощи.
Вандышев Александр 30.03.2013 13 15.11.2013
Колесников Артем 03.04.2013 15 21.05.2013
Сагоян Арсен 05.05.2013 15 02.01.2014
Горохов Александр 11.09.2013 15 18.12.2013
Чичагин Артём 09.10.2013 15 28.11.2013
Кузнецов Ярослав 13.10.2013 12 14.11.2013
Кожин Константин 17.11.2013 15 20.12.2013
Тарасов Кирилл 02.12.2013 15 02.01.2014
Раскраска карты
16
Вход: описание стран на карте множеством отрезков (страна - многоугольник).
Выход: минимальное число цветов, необходимое для раскраски данной карты
(т.е. 2 соседних страны не могут быть одного цвета), и соответствующая раскраска.
Примечание: данная программа предполагает визуализацию.
Добрунов Александр 15.05.2013 10 25.05.2013
Садовничая Евгения 08.11.2013 16 13.01.2014
Симоненко Алёна 12.11.2013 16 12.01.2014
Гасников Даниил 22.11.2013 16 06.01.2014
Кропанцев Никита 04.01.2014 10 28.01.2014
Сетевые сервисы

Написать одну из следующих программ:
- клиент для получения почты (по протоколу POP3)
- клиент для отправки почты (по протоколу SMTP)
- FTP-клиент
- NTP-клиент [7]
- DNS-клиент [14]
- BitTorrent-клиент [25]

POP3 12
Соболев Илья 19.11.2013 4 16.12.2013
Горохов Александр 18.12.2013 12 13.01.2014

SMTP 12
Митрофанова Елена 24.02.2014 9 13.03.2014
Бучельников Станислав 07.03.2014 11 03.04.2014
Gilimkhanov Denis 03.04.2014 7 03.04.2014

FTP 12
Дементьев Дмитрий 15.05.2013 8 28.05.2013
Дубинин Роман 09.09.2013 4 30.09.2013
Сагоян Арсен 12.12.2013 6 16.12.2013

NTP 7
Сироткин Дмитрий 13.01.2014 7 13.01.2014

DNS 14

BitTorrent 25
Чат
15
Написать программу-чат для произвольного числа пользователей (децентрализованную).
Горохов Александр 05.04.2013 15 30.05.2013
Чичагин Артём 20.05.2013 13 14.10.2013
Кожин Константин 29.05.2013 10 29.05.2013
Ромашкин Леонид 06.06.2013 1 10.07.2013
Колесников Артем 07.12.2013 15 13.01.2014
Соболев Илья 15.05.2014 12 16.05.2014
Разбор графических файлов

Вход: файл(ы) в одном из следующих форматов:
- BMP (Windows) [15]
- GIF (в т.ч. с анимацией)
- JPEG [17]
- PNG
Выход: подробное описание внутренней структуры файла и изображение.
Примечание: данная программа предполагает визуализацию.

BMP 15
Меньших Иван 08.03.2013 5 03.02.2014
Копылов Евгений 15.01.2014 14 15.01.2014

GIF 14

JPEG 17

PNG 14
Копылов Евгений 25.05.2013 14 07.06.2013
Словари
15
Реализовать несколько способов организации словаря (массивы с линейным поиском, упорядоченные массивы с бинарным поиском, деревья, сбалансированные деревья, хеш-таблицы) и сравнить их (время выполнения операций со словарем, объем занимаемой памяти) между собой и со встроенным dict.
Гусева Зинаида 10.05.2013 8 02.06.2013
Кузнецов Ярослав 02.12.2013 1 25.12.2013
Меньших Иван 08.12.2013 15 13.01.2014
Колесников Артем 03.01.2014 10 13.01.2014
Адресная книга
15
Программа для экспорта контактных данных из двух социальных сетей на выбор (ВКонтакте, Facebook, Мой Круг, Одноклассники, LinkedIn, Twitter) в один из форматов, поддерживаемых Windows Contacts, Google Contacts или Mac OS X Contacts. Необходимо обеспечить поддержку операции слияния контактов.
Чичагин Артём 20.10.2013 8 24.10.2013
Соболев Илья 14.05.2014 4 16.05.2014
Интерактивные игры

Реализовать игру

pentix 11
Селезнев Никита 09.04.2013 11 07.05.2013
Кропанцев Никита 13.05.2013 10 28.05.2013
Добрунов Александр 15.09.2013 11 11.11.2013
Колесников Артем 11.01.2014 11 13.01.2014

arkanoid 13
Меньших Иван 19.02.2013 9 09.03.2013
Вандышев Александр 21.02.2013 13 28.04.2013
Дубинин Роман 04.04.2013 13 17.12.2013
Симоненко Алёна 14.05.2013 13 02.06.2013
Садовничая Евгения 15.05.2013 13 28.05.2013
Гусева Зинаида 01.12.2013 4 20.12.2013
Кузнецов Ярослав 30.12.2013 5 07.01.2014
Соболев Илья 02.04.2014 7 02.04.2014

pacman 15
Дементьев Дмитрий 31.03.2013 15 28.04.2013
Мокрушина Анна 17.12.2013 15 17.12.2013
Гладких Максим 11.02.2014 14 19.02.2014
Бучельников Станислав 27.03.2014 10 04.04.2014
Бредогенератор
11
Вход: тексты для обучения
Выход: сгенерированный связный согласованный текст
Вандышев Александр 16.12.2013 6 16.12.2013
Смирнова Анна 12.01.2014 11 13.01.2014
Меньших Иван 12.01.2014 11 13.01.2014
Кропанцев Никита 02.04.2014 6 04.04.2014
Митрофанова Елена 03.03.2015 11 24.03.2015
Разбор аудиоформатов

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

mp3 14

ogg 14

flac 14
Аудиоредактор
18
Вход: файл(ы) в формате wav.

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

Реализовать утилиту для стеганографии в одном из следующих форматов.

bmp 14
Вандышев Александр 03.04.2013 10 10.05.2013
Сагоян Арсен 04.12.2013 14 13.01.2014
Дубинин Роман 05.12.2013 12 26.12.2013

wav 14
Работа с файловыми системами

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

FAT32 17

ext4 21
Фотоальбом
20
Реализовать утилиту для поиска, просмотра и кластеризации фотографий, а также организации фотоальбомов. Кластеризация должна выделять и различать дубли, серии, схожие фотографии.
Где трамвай
20
Реализовать толстый клиент к сервису http://online.ettu.ru, используя скачанные карты Open Street Maps.