Процесс подготовки высококвалифицированных специалистов, прежде всего, направлен на формирование их профессиональных навыков. Уровень владения навыками напрямую определяется степенью сформированности общих, общепрофессиональных и профессиональных компетенций. В подготовке математика-программиста это, прежде всего, такие компетенции, как:
- способность решать стандартные задачи профессиональной деятельности на основе информационной и библиографической культуры с применением информационно-коммуникационных технологий и с учетом основных требований информационной безопасности;
- способность использовать знания основных концептуальных положений функционального, логического, объектно-ориентированного и визуального направлений программирования, методов, способов и средств разработки программ в рамках этих направлений;
- готовность к разработке моделирующих алгоритмов и реализации их на базе языков и пакетов прикладных программ моделирования;
- способность к самоорганизации и самообразованию;
- способность работать в команде, толерантно воспринимая социальные, этнические, конфессиональные и культурные различия.
В этой связи рассмотрение олимпиадных задач по программированию с определением их сущностных характеристик, выделением способов решения, изучением методик решения в обучении будущих специалистов способствует формированию и развитию указанных компетентностей в сфере программирования, моделируя будущую профессиональную деятельность. Олимпиадные задачи, традиционно выделяемые в особый класс задач повышенной сложности, требуют в своем решении не только фундаментальных знаний в предметной области, но и нестандартных подходов, самостоятельности, творческого начала [1], – всего того, что связывается с определением хорошего программиста.
В соответствии с данным подходом формирование профессиональных способностей обучающихся рассматривается как процесс построения и изучения моделей алгоритмов и объектов для определения или улучшения их характеристик, реализации способов их построения, управления ими и т.п.
Решение олимпиадных задач предполагает эффективное применение навыков, приобретённых в ходе обучения, таких как:
- выполнение декомпозиции (разбиение задачи на более мелкие подзадачи);
- оптимизация (поиск наилучших структур и объектов для реализации более быстрого и надежного алгоритма решения);
- визуализация решения (использование программных продуктов для графического отображения алгоритмов);
- работа в команде (совместная генерация общих идей с последующим разделением функций и решаемых задач).
Наряду с обучающей функцией олимпиадные задачи с успехом могут выполнять функции контроля и оценки знаний и умений обучающихся. Поскольку умения – это способность человека применять знания в практической деятельности в изменяющихся условиях, следовательно, данные функции также служат основой подготовки студентов к профессиональной деятельности.
Рассмотрим сформулированные положения на примере решения олимпиадной задачи «Метро» в рамках занятий по дисциплине «Структуры и алгоритмы компьютерной обработки данных» учебного плана направления подготовки Математическое обеспечение и администрирование информационных систем.
Условие задачи:
«В некотором городе есть метро, состоящее из N (1£N£1000) станций и M линий, соединяющих их. Каждая линия обеспечивает проезд между какими-то двумя станциями в обе стороны. Между любой парой станций проведено не более одной линии. Сеть метро построена таким образом, чтобы с каждой станции можно было проехать на каждую (возможно, через промежуточные станции). Назовем это свойство связностью метро. В связи с изобретением принципиально нового вида транспорта метро стало убыточным, и его работу решили прекратить. На заседании мэрии города было постановлено закрывать каждый год по одной станции, но так, чтобы связность метро каждый раз сохранялась. При закрытии какой-либо станции, линии, ведущие из этой станции в другие, естественно, тоже перестают функционировать.
Требуется по введенной информации о сети метро разработать какой-либо порядок закрытия станций, при котором метро всегда будет оставаться связным».
Решением стало приложение, разработанное в среде MS Visual Studio, посредством языка программирования С# и технологии WPF.
В ходе решения поставленной задачи были выполнены следующие этапы:
1) постановка задачи:
а) определён входной набор данных:
- количество станций;
- связи между станциями;
б) определён выходной набор данных:
- последовательность удалённых станций с их порядковыми номерами
2) исследование задачи с целью составления и анализа модели:
а) при разработке математической модели было выяснено, что данная задача сводится к решению задачи из области дискретной математики. Исходный набор станций представляет собой связанный граф, вершинами которого являются станции, а рёбрами – линии метро, соединяющие станции. Решение задачи заключается в постепенном удалении вершин графа с условием того, что при последующем удалении вершины граф останется связанным;
б) в ходе анализа математической модели было принято решение использовать:
- расширенные структуры данных для оптимизации операций при работе с исходным набором данных, в которой в качестве полей a и b указываются две связные вершины:
public struct apex
{
int a;
int b;
};
- массивы с динамическим выделением памяти.
3) разработка алгоритма, схема которого сводится к следующим шагам:
- Выбираем произвольную станцию.
- Проверяем, останутся ли все станции, смежные с выбранной в шаге 1, связанными между собой при её удалении.
- Если пункт 2 выполняется, то записываем номер выбранной станции в результирующий массив и исключаем её из рассмотрения. Переходим в шагу 1.
- Иначе, выбираем другую станцию и переходим к шагу 2.
- Продолжаем алгоритм до тех пор, пока не исключим все станции из рассмотрения.
Основной сложностью данного алгоритма являлось обнаружение связи между парой произвольных станций, т.е. проверка возможности попадания из одной станции на другую. Для этого был реализован вспомогательный рекурсивный алгоритм поиска пути, который представлен следующей функцией:
int SEARCH(int s1, int s2, int n, int *metki, int m, apex *edges)
{
for(int i=0; i<m; i++)
{
if ((edges[i].a==s1 && edges[i].b==s2)||(edges[i].a==s2 && edges[i].b==s1)) return 1;
else
{
if (edges[i].a==s1 && metki[edges[i].b]!=0)
{
metki[edges[i].b]=0;
if (SEARCH(edges[i].b, s2, n, metki, m, edges)==1)
return 1;
}
if (edges[i].b==s1 && metki[edges[i].a]!=0)
{
metki[edges[i].a]=0;
if (SEARCH(edges[i].a, s2, n, metki, m, edges)==1)
return 1;
}
}
}
return 0;
}
Параметрами данной функции являются порядковые номера двух вершин s1 и s2, массив использованных вершин metki[] размера n, в котором номера вершин есть индексы его элементов, и массив связанных вершин edges[] размера m.
Функция работает до тех пор, пока существует связь между вершинами s1 и s2, причём хотя бы одна из этих вершина должна быть не отмечена в массиве metki[]. Результатом работы функции является возврат единицы, если путь между вершинами s1 и s2 существует, и нуля в противном случае.
4) программная реализация алгоритма, которая потребовала выполнения следующих шагов:
А) тестирование и отладка программной реализации алгоритма, которые показали верные результаты на различных наборах тестовых данных. Один из примеров тестовых вариантов расположения станций приведён на рисунке 1.
Рис. 1. Пример тестового варианта расположения станций
Потенциальной ошибкой данного теста, является случай, когда первой случайной станцией для удаления является станция под номером 4, так как после удаления нарушается связность графа. Рекурсивная проверка связанности смежных вершин (№3 и №5) показывает, что после удаления вершины №4 пути со станции №3 на станцию №5 не существует.
Б) графическая визуализации алгоритма.
Готовая программа была написана на языке C# с использованием WPF.
Интерфейс программы представляет собой окно с кнопкой для открытия исходного файла и канвы, на которой происходит прорисовка станций и соединяющих линий. При открытии текстового файла входных данных матрица смежности исходного графа сохраняется в массив структур, а координаты в двумерный вещественный массив, далее вступает в работу алгоритм, описанный выше. В результате получаются три массива – с полученной очередностью удаления станций (массив результата), массив координат и матрица смежности. Так как канва имеет фиксированные размеры в пикселях, а также начало отсчёта ведётся с левого верхнего угла, координаты нужно преобразовать. Для этого используется «коэффициент сжатия», который высчитывается по формуле (Высота_канвы)/(Максимальная_по_модулю_координата). Так как канва квадратная, не имеет значения использование высоты или ширины канвы в данной формуле.
Все станции представляют собой эллипсы с фиксированным радиусом. На первом этапе прорисовки берутся числа из массива координат, умножаются на «коэффициент сжатия» и используются как координаты эллипсов на канве с учётом экранной системы координат (к координате X прибавляется высота канвы в пикселях, а из координаты Y вычитается высота канвы и умножается на минус единицу). На этом этапе работает цикл, в теле которого эллипсы прорисовываются на канве, а внутри них ставится порядковый номер (от 1 до N) в виде текст-блоков. Затем прорисовываются отрезки, соединяющие станции. Так как в матрице смежности попарно указываются соединённые станции, обе координаты отрезка берутся из массива координат (с учётом преобразований), а сама матрица смежности нужна только для определения наличия данного отрезка.
На следующем этапе выполняется поэтапное удаление станций за счет того, что по канве не прорисовывается та станция, порядковый номер которой хранится в массиве результата под очередным индексом, начиная с нулевого. На последней итерации не остаётся ни одного эллипса и отрезка, канва очищается. Промежуточный результат работы программы показан на рисунке 2.
Рис. 2. Графический интерфейс приложения «Метро»
Существенным недостатком WPF, с которым пришлось столкнуться на практике – невозможность прорисовки элементов в реальном времени без использования нескольких потоков. Это означает, что интерфейс программы не обновится до тех пор, пока не выполнятся все вычисления (в данном случае на протяжении всей работы программы была видна только пустая канва). При этом, приоритет в одном потоке отдаётся вычислениям, а не прорисовке. Для решения данной проблемы использовался метод DoEvents из библиотеки WindowsForms.
При подобном комплексном решении задач повышенной сложности у студентов не только непосредственным образом формируются профессиональные навыки, помогающие достигать реальных целей, которые будут поставлены перед ними в их дальнейшей профессиональной деятельности, но и закладывается фундамент высокого профессионализма, конкурентоспособности, грамотного представления результатов своего труда.
Библиографический список
- Ванькова, В.С. Творческие задания в обучении информатике студентов педагогического вуза / В.С.Ванькова, Ю.М.Мартынюк. – Педагогическая информатика, 2005, № 1
Количество просмотров публикации: Please wait