Темы курсовых работ по Информатике 2009

Материал из Кафедра АСОИУ
Перейти к: навигация, поиск

Темы курсовых работ по дисциплине «Информатика» группы ИВТ-347 (2009/2010 уч. год, осенний семестр).

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

Планируемые бонусы: реализация в виде веб-проекта OR реализация на C# или Java OR клиент-сервер с использованием SQL – оценка на балл выше.

Содержание

Обработка текста

Филиппов Андрей 3-5
Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения
Разработка метода ранжирования текстовых строк по похожести
Разработать и реализовать алгоритм поиска текстовых формулировок, похожих на заданную. Формулировки представляют собой короткие повествовательные предложения на русском языке. Найденные похожие формулировки должны быть ранжированы по степени похожести на основе некоторого критерия. Исследовать несколько критериев ранжирования. Для тестирования использовать заимствованные базы формулировок.
Еремеев Глеб 4-5 Байесовская фильтрация спама Получить байесовскую оценку того, что заданный текст является «спамом», на основе обучающей выборки текстов «спама» и «не спама». Описание метода: http://ru.wikipedia.org/wiki/Теорема_Байеса
ФИО 5 Оценка похожести текстов с помощью алгоритма Рабина–Карпа Разработать метод определения похожести текстов, основанный на проверке наличия в данном тексте ключевых строк, содержащихся в других документах. Для определения совпадения строк использовать алгоритм Рабина–Карпа (http://ru.wikipedia.org/wiki/Алгоритм_Рабина_—_Карпа). Результатом является гистограмма совпадений нового документа с эталонными документами, информация о которых собрана в базе данных.
ФИО 5 Построение суффиксного дерева Построить суффиксное дерево ограниченной глубины для произвольного заданного файла, рассматриваемого побайтно. Дополнительно реализовать утилиту по подсчёту байтов, следующих в контексте заданной строки, с помощью которой можно проверять полноту суффиксного дерева.
Гущин Александр 5 Построение суффиксного дерева на основе хэш-функции строки Разработать и реализовать хэш-функцию для построения частотного словаря всех повторяющихся подстрок байтов заданного файла (суффиксного дерева). Максимальная длина подстроки задаётся. Дополнительно реализовать простую утилиту для подсчёта частоты встречаемости заданной подстроки байтов в файле, с помощью которой можно проверить корректность построенного суффиксного дерева.
ФИО 5 Построение частотного словаря и проверка закона Ципфа Написать программу, которая обрабатывает текстовые файлы, пополняя базу данных встречающихся слов, сохраняя частоту встречаемости слов. По накопленному словарю построить гистограмму встречаемости слов разной длины и проверить закон Ципфа. Для хранения словаря использовать суффиксное дерево.
ФИО 5 Реализация алгоритма LIPT Разработать и реализовать упрощённую модификацию алгоритма LIPT (Length Index Preserving Transform) для текстов на русском языке. Пример реализации здесь: http://www.compression.ru/ds/, статьи здесь: http://www.compression.ru/download/text.html

Растровая графика

ФИО 3 Исследование методов уменьшения количества цветов точечного растра Привести обзор методов уменьшения количества цветов точечного растра (color quantization), в том числе использующих добавление шума (дизеринг, dither). Протестировать несколько методов и сравнить их по выбранным критериям оценки качества.
Программирование не требуется. Максимальная оценка – «удовл».
ФИО 3-4 Билинейное масштабирование растровых изображений Разработать ПО для билинейного масштабирования растровых изображений. Сравнить результаты с другими реализациями
Максимальная оценка – «хор». На «удовл»: реализация в SciLab без использования готовых функций интерполяции.
Куликова Евгения 3-5
Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения
Масштабирование изображения с учётом содержимого
Реализовать алгоритм изменения размеров цветного изображения, который учитывает содержимое изображения (англ. Seam Carving или Content-Aware Image Resizing Algorithm). На «отл»: для вычисления энергии пикселей использовать оператор Собеля.
ФИО 5 Восстановление растрового изображения по случайному набору пикселей Реализовать следующий метод восстановления растрового изображения по известным значениям некоторых случайно выбранных пикселей. По набору известных точек проводится триангуляция Делоне, после чего значения неизвестных пикселей вычисляются при помощи линейной интерполяции известных значений в вершинах треугольника, к которому принадлежит пиксель. Продемонстрировать динамику проявления изображения по мере поступлении информации о значении новой группы пикселей.

Обработка звука

ФИО 3-5
Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения
Изменение длительности звука без изменения его частотных свойств
Исследовать методы изменения длительности звука без изменения его частотных свойств (англ. stretch) и реализовать один из этих методов для обработки wav-файлов.

На «удовл»: только сокращение длительности звучания.

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

На «отл»: микширование при купировании, удобное приложение для редактирования wav-файлов.

ФИО 5
Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения
Деинтонирование звука
Разработать и реализовать метод понижения частоты высокочастотных составляющих звука до заданного порога без потери характеристик ритма. Практической целью преобразования является понижение частотных свойств записи человеческой речи без потери её разборчивости.

Сжатие данных

Турганов Рустам Муратович 3 Анализ временной стоимости сжатия LZ-методов Привести анализ временной стоимости сжатия словарных методов на основании зависимости степени сжатия от времени сжатия при использовании всех известных компрессоров и архиваторов семейства LZ (www.maximumcompression.com). Временная стоимость сжатия может быть определена как разница во времени сжатия при увеличении степени сжатия на определённый постоянный коэффициент.
Программирование не требуется. Максимальная оценка – «удовл».
Терентьева Любовь 3-5 Генерация случайного текста с помощью компрессора Случайный текст, подобный некоторому существующему тексту, может быть получен следующим образом. Имеющийся текст сжимается компрессором в поток двоичных данных со статистическими свойствами, близких к случайным числам. Если к этому потоку добавить случайные числа, то декомпрессор продолжит декодирование за пределы исходного текста, генерируя случайный текст со статистическими характеристиками исходного. Требуется подготовить большой объём текста на русском языке и на его основе сгенерировать случайный текст с использованием одного из современных компрессоров. Для добавления к архиву случайных чисел понадобится написать специальную программу.
На «удовл»: один компрессор; на «хор»: сравнение результатов нескольких компрессоров; на «отл»: использование PAQ8 (лидера в степени сжатия на сегодняшний день) и получение качественного результата.
ФИО 3-5 Исследование методов неискажающего сжатия монохромных изображений Привести обзор методов неискажающего сжатия монохромных изображений. Реализовать один из методов программно и оценить эго эффективность по сравнению с существующими аналогами.
На «удовл»: собственная реализация RLE и формата PCX для Win32/.NET; на «хор»/«отл» – любого более сильного алгоритма.
Купцов Анатолий 4-5 Динамическое марковское сжатие (DMC) Исследовать и реализовать метод динамического марковского сжатия (DMC).
На «удовл»: полноценное исследование и презентация работы DMC; на «хор»: реализация для двоичного алфавита; на «отл»: реализация для алфавита большей мощности.
ФИО 4-5 Реализация арифметического кодирования для алфавита большой мощности Арифметическое кодирование в отличии от кодов Хаффмана позволяет кодировать информацию дробным числом бит, достигая большей оптимальности. При этом кодер имеет простой и удобный интерфейс (не требующий работы с деревьями и другими сложными структурами данных). Основной проблемой использования арифметических кодеров является работа с распределением вероятностей дискретной величины, которая может принимать много значений (алфавит большой мощности). Требуется разработать алгоритм использования арифметического кодера для такого случая. Например, для простого статистического кодирования файлов, рассматриваемых не побайтно, а пословно (по два байта).
На «хор»: реализация обычного однобайтового подхода с оптимизацией для двухбайтового случая; на «отл»: универсальный алгоритм.
Жакиянов Ахан 5 Разработка LZP-компрессора Реализовать компрессор для сжатия произвольных файлов на основе одного из наиболее элегантных словарных методов – LZP. Сравнить результативность по степени и по времени сжатия с другими компрессорами, использующими LZP-подобные методы.

Прогнозирование

Кербель Ольга 3-5 Коррекция народного способа прогнозирования осадков Известен народный способ прогнозирования осадков, предполагающий повторение осадков с интервалом ровно в шесть месяцев. Например, если 1 января был снегопад, то 1 июля ожидается дождь и т.д. Требуется по накопленной статистике осадков за несколько лет проверить этот метод и выявить наиболее подходящий интервал повторения осадков. Затем требуется улучшить прогноз за счёт учёта фаз Луны. Известно, что если в начале фазы Луны осадков нет, то всю фазу (7 дней) осадков обычно не бывает; в первую фазу Луны осадков обычно не бывает никогда; если в первые дни первой фазы выпадают осадки, то осадки продолжатся всю первую фазу.
Хейфец Илья 5 Прогнозирование однозвучной мелодии Разработать метод контекстного прогнозирования однозвучной мелодии (т.е. содержащей только одну ноту в один момент времени). В качестве меры эффективности прогноза использовать суммарное количество информации, содержащееся в нотах, судя по полученным оценочным вероятностям. Мелодии могут быть заимствованы, например, из imy-файлов.
Крындач Егор 5 Прогнозирование ходов человека в игре «Чёт-нечёт» Разработать и реализовать алгоритм прогнозирования ходов человека в игре «Чёт-нечёт». Человек загадывает двоичное значение, компьютер пытается угадать, после чего человек сообщает правильный ответ. На основе истории загаданного и угаданного компьютер более точно прогнозирует то, что загадает человек. Сравнить результаты с более простыми прогнозирующими моделями.
На «удовл»: контекстное моделирование 3-го порядка с полным смешиванием (Microsoft Excel). На «хор» или «отл»: Win32/.NET-исполняемый проект с реализацией адаптивного смешивания прогнозов.

Переборные алгоритмы

Чешегоров Дмитрий 3-5 Двумерная упаковка Исследовать существующие подходы к решению задач упаковки и реализовать максимально плотную двумерную упаковку заданного набора различных прямоугольников в прямоугольный контейнер.
На «удовл»: реализовать полный перебор без оптимизаций.
ФИО 5 Генератор «сканвордов» Реализовать генератор «сканвордов» по базе слов и их кратких определений. Определение слова занимает одну клетку и располагается в соседней по вертикали или горизонтали клетке от первой буквы слова. Около определения ставится графическая стрелка, указывающая начало слова и его направление.
Мандронов Михаил 5
Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения
Нахождение наиболее информативной полной группы несовместных тегов
Разработать и реализовать алгоритм нахождения всех возможных полных групп несовместных тегов. Полной группой несовместных тегов (п.г.н.т.) будем называть подмножество тегов, покрывающих все помеченные тегами объекты, но таких, что каждый объект помечен только одним из этих тегов. Система фильтрации объектов с помощью тегов, снабжённая таким алгоритмом, действует следующим образом. Вместо облака тегов (которых может быть слишком много) пользователь видит одну из возможных п.г.н.т. и должен выбрать тот единственный из несовместных тегов, которым помечен искомый объект. После выбора первого тега, отбираются объекты, помеченные этим тегом, строится новое множество (меньшее по объёму) тегов, описывающих оставшиеся объекты, и алгоритм применяется заново к полученному множеству тегов. И так до получения необходимых результатов поиска: нахождения искомого объекта, либо существенного сужения выборки. Из возможных п.г.н.т. на каждом шаге должна выбираться наиболее выгодная в энтропийном смысле (выбор пользователя должен обеспечить наибольшее количество информации).

Имитационное моделирование

Сердюк Алексей 3-5
Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения
Имитационное моделирование загрузки парикмахерской
Реализовать имитационное моделирование обслуживания клиентов в парикмахерской. Время обслуживания – случайная величина с нормальным распределением вероятности. Поток клиентов пуассоновский. Найти минимальное количество парикмахеров, при котором очередь не превышает заданной величины.

На «удовл»: реализовать полный перебор без оптимизаций. На «отл»: полная автоматизация и отличный внешний вид.

ФИО 3-5
Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения
Имитационное моделирование загрузки театрального гардероба
Реализовать имитационное моделирование работы театрального гардероба перед началом спектакля. Предполагать, что зрители приходят в течение получаса до спектакля. Время обслуживания одного человека в гардеробе – случайная величина с нормальным распределением вероятности. Найти максимальную и среднюю длину очереди при заданном числе зрителей и работников гардероба.

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

Прочие

Журавлев Андрей 3-5 Генератор текста на основе марковского графа состояний Сгенерировать псевдослучайный текст с помощью марковского источника, заданного графом состояний с ветвями переходов между состояниями. Граф может быть задан таблицей с полями: индекс родительской вершины, индекс дочерней вершины, символ, вероятность перехода. Вероятность выхода из вершины (т.е. сумма вероятностей перехода к ко всем дочерним вершинам) должна быть равна единице.
На «отл» требуется графическое отображение графа.
Утянский Александр 3-5 Модификация игры «Пять в ряд» для трёх участников Разработать и реализовать алгоритм варианта игры «Пять в ряд» для трёх (!) играющих. Суть игры заключается в расстановке игроками по очереди своих знаков (например, «х», «о» и «#») в клетках безграничного поля с целью поставить пять своих знаков подряд (по горизонтали, вертикали или диагонали).
На «удовл»: программирование простейшей логики компьютерного игрока.
Ткаченко Ярослав 3-5
Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения
Реализация игры «Феодал»
Разработать искусственный интеллект для игры с компьютером в игру «Феодал». Игроки по очереди ставят отметки своего цвета в точках пересечения линий безграничного клеточного поля. Если получается окружить точки или государства противника, проводится замкнутая ломанная и образуется новое государство. Точнее: если после очередного хода игрока его точки можно соединить элементарными отрезками (длиной, не превышающей диагональ клетки) так, чтобы внутри оказалась хотя бы одна точка противника и чтобы получилась замкнутая ломанная, то замкнутая ломанная проводится, площадь многоугольника закрашивается, и противник не имеет больше возможности использовать оккупированные точки. Если в окружение попадает государство, оно теряет свой статус и перекрашивается вместе со всей оккупированной областью.
На «удовл»: программирование простейшей логики компьютерного игрока.
Вешкурцев Никита 3-5
Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения
Исследование алгоритмов преследования
Исследовать алгоритмы преследования (chasing algorithms), реализовать выбранные алгоритмы для разрабатываемой игры «Packman» и провести их сравнительный анализ.
Абакумов Дмитрий 4-5
Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения
Искусственный интеллект для игры «Blockus»
Разработать и реализовать искусственный интеллект для игры «Blockus» (уже реализованную для игрового плеера Microsoft Zune). Основное внимание при разработке алгоритма должно быть уделено исследованию численного критерия эффективности выбранного хода.
Ежков Павел 5 Автоматизированное тематическое хранилище файлов Разработать программное обеспечение для организации тематического хранилища файлов в структуре автоматически создаваемых папок по названию ключевых слов, описывающих файлы. Информация о файлах хранилища должна храниться в корневой папке хранилища в текстовом виде. Должна быть реализована функция объединения двух хранилищ, созданных независимо. Пример работы системы. Требуется добавить файл «Черновик плана мероприятия.doc», характеризуемые ключевыми словами: детство, творчество, мероприятия, методики, незаконченные материалы. Система копирует файл в подпапку \детство\методики\незаконченные материалы\творчество\мероприятия и обновляет файлы \filelist.txt и \tags.txt с информацией о файлах и словарём ключевых слов. Дерево каталогов строится автоматически по словарю ключевых слов. При соединении хранилищ или существенном изменении частот ключевых слов система папок должна быть полностью перестроена (критерий – минимально возможное количество подпапок).
Семёнов Роман 5
Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения
Построение трасс с огибанием препятствий
Разработать и реализовать алгоритм построения минимального остовного дерева трасс, соединяющих заданные точки карты с огибанием препятствий. Препятствия описаны выпуклыми многоугольниками, и огибающая должна проходить через одну или несколько вершин многоугольника по его граням. Продемонстрировать работу алгоритма на плане города (многоугольники с преимущественно прямыми углами) и картах местности (выпуклые многоугольники, описывающие озёра).
Башмаков Евгений 5
Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения
Реализация итеративного вероятностного поиска
Реализовать метод итеративного вероятностного поиска объектов по их свойствам.

Пользователю предлагается ранжированная выборка наиболее информативных свойств объектов, он выбирает одно из свойств и сообщает, обладает искомый объект этим свойством или нет. На основании ответа пользователя пересчитывается распределение вероятностей релевантности объектов. Исходной информацией является множество троек объект-свойство-коэффициент, где коэффициент имеет смысл оценки вероятности того, что, когда пользователь отвечает, что искомый объект обладает данным свойством, то ищется именно этот объект. При этом объекты не обязательно охарактеризованы по всем имеющимся свойствам (т.е. для некоторых возможных пар объект-свойство значение коэффициента неизвестно). Частоты востебованности объектов задают начальное распределение вероятностей. Пересчёт вероятностей производится по методу Е.Д. Шелвина.

Ссылки

Личные инструменты