Московский Государственный Университет Путей
Сообщения (МИИТ)
Проблемная задача
для студентов 2 курса (2 семестр) специальности
«Программное обеспечение вычислительной техники и автоматизированных систем» по
дисциплине «Теория вычислительных процессов»
«Разработка программы
фильтрации статей конференций RELCOM.»
Общее число часов: 20
В т.ч. лабораторных - 5
Самостоятельная работа студентов
– 15
Выполнил:
Аспирант Соболев А.В.
Москва 2001
Проблемная ситуация.
В органах снабжения
железнодорожного транспорта с целью ценового анализа рынка
материально-технических ресурсов проводится регулярная отработка предложений
от покупателей-продавцов, поступающих в коммерческие конференции сети RELCOM
(один из провайдеров Интернет)
Список статей представляет
собой текстовый файл (на дискете), содержащий в себе набор предложений
от организаций и частных лиц о покупке, продаже какого-либо материала и другую,
в том числе бесполезную информацию. Предложения могут повторяться
неоднократно. Регулярный просмотр этих предложений занимает много
рабочего времени и малоэффективен в связи с отсутствием программных средств.
Для снижения рутинного ручного труда по просмотру этой информации и отбора предложений
для дальнейшей отработки возникла
насущная потребность в программе автоматической фильтрации и сортировки
исходных данных.
Проблемные вопросы
1. Как определить общую
функциональность программы?
2. Как разработать внешний
интерфейс программы?
3. Как создать рабочую версию
программы (разработка внутренних интерфейсов межмодульных взаимодействий с
целью дальнейшего развития программы)?
4. Как усовершенствовать
программу с целью достижения максимального быстродействия?
Проблемная задача
Написать компьютерную
программу автоматической фильтрации и сортировки исходных данных,
удовлетворяющую следующим требованиям:
1. Для ручного анализа
программа должна оставлять только те предложения, которые содержат одно
из искомых слов.(«Купим», «Куплю», «Найти», «Преобрету»,
«Приобрету» и т.д.)
2. Предложения, содержащиеся в списках неоднократно,
должны попадать в результат лишь однажды.
3. Предложения, проанализированные в
предыдущий период, не должны больше предоставляться для отработки
(история).
4. Интерфейс программы должен
позволять простое изменение набора искомых слов.
Методические указания
Для решения
задачи студенты должны актуализировать знания одного из языков
программирования, курса «Теория вычислительных процессов» в части «Конечные
автоматы» и курса «Структуры данных». Для разработки внутренних интерфейсов
межмодульных взаимодействий потребуется актуализировать знания в области
объектно-ориентированного программирования. В качестве учебного пособия по этим
разделам компьютерного знания
преподаватель рекомендует учащимся использовать литературу, указанную в
конце данного документа.
Задача решается
последовательным ответом на проблемные вопросы и программной реализацией
найденных решений.
Для ответа на первый
проблемный вопрос целесообразно использовать требования к программе
(раздел «Проблемная задача») Исходя из определения функций системы,
формулируются требования к входным и выходным данным и способу их интерпретации
программой. Таким образом, формируется внешний интерфейс программы и появляется
ответ на второй проблемный вопрос. Третий проблемный вопрос
решается программной реализацией системы.
Наибольшую сложность
представляет собой решение четвертого проблемного вопроса. Здесь
подразумевается
1. Создание оптимальной
структуры данных для накопления уже имеющихся предложений с целью
исключения их из результата работы программы (вместо связного списка –>
упорядоченный список -> древовидная структура -> что-то еще?)
2. Оптимальный алгоритм поиска
сразу нескольких слов в одном предложении с целью определения наличия
хотя бы одного из них (вместо последовательного перебора каждого из слов с
выяснением его наличия в предложении (многопроходная схема) ->
автоматическое построение конечного автомата по заданному набору слов и его
использование для однопроходного просмотра предложения.)
3. Возможна дополнительная
функциональность – разработка алгоритма определения похожести двух предложений
(одни и те же по смыслу) при физическом (по количеству и расположению слов) их
различии.
Цель работы
1. Создание реально работающей
системы помощи в информационном анализе.
2. Актуализация ранее усвоенных
и новых знаний по:
·
объектно-ориентированному программированию,
·
конечным автоматам,
·
структурам данных,
·
оптимизации процессов;
3. На основе вышеуказанных
знаний формирование навыков и умений:
·
анализа исходных данных для дальнейшего их программного преобразования,
·
формулировки задачи,
·
разбиения задачи на подзадачи,
·
применения теоретических знаний по программированию в практическом
аспекте,
·
разработки легко модифицируемых программ,
·
работы с выбранной средой программирования,
·
отладки сложных многомодульных программ,
4. В результате у студентов
формируется творческое мышление, и настойчивость в достижении поставленной
цели.
Литература
1. Яблонский С.Б. «Дискретная
математика»
2. Бьярн Строуструп
«Язык программирования С++»
3. Дейкстра «Алгоритмы + Структуры
данных = Программы»
4. Допускается использование
любой другой литературы, позволяющей выполнить цель работы.
Приложение
Дискета с исходными текстами программы и кратким
описанием (для преподавателя), исходными данными (для студентов).