Методические рекомендации по выполнению практических работ по междисциплинарному курсу
 Скачать 2.6 Mb.
|
|
(код и наименование специальности) Государственное бюджетное профессиональное образовательное учреждение «Кунгурский автотранспортный колледж» МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ ПРАКТИЧЕСКИХ РАБОТ по междисциплинарному курсу МДК 01.01 Разработка программных модулей по специальности: 09.02.07 Информационные системы и программирование 2020 Одобрено на заседании цикловой комиссии информационно-математических дисциплин Протокол №____ от «__» ________20___г. Председатель комиссии ______________________Е.А. Наговицына УТВЕРЖДАЮ Зам. директора ______________М.Г. Целищева «___» ___________ 20___г. Организация-разработчик: ГБПОУ КАТК СОДЕРЖАНИЕ 1 Пояснительная записка ................................................................................................................. 4 2 Перечень практических работ МДК 01.01 Разработка программных модулей ...................... 4 3 Инструктивно-методические указания по выполнению практических работ .......................... 6 4 Используемая литература и интернет источники ................................................................... 166 1 Пояснительная записка Данные методические рекомендации составлены в соответствии с содержанием рабочей программы МДК 01.01 Разработка программных модулей специальности 09.02.07 Информационные системы и программирование. МДК 01.01 Разработка программных модулей изучается в течение III и IV семестра. Общий объем времени, отведенный на практические занятия по УД, составляет в соответствии с учебным планом и рабочей программой – 101 час Практические работы проводятся после изучения соответствующих разделов и тем МДК 01.01 Разработка программных модулей. Выполнение обучающимися практических работ позволяет им понять, где и когда изучаемые теоретические положения и практические умения могут быть использованы в будущей практической деятельности. В результате выполнения практических работ, предусмотренных программой по МДК 01.01 Разработка программных модулей, обучающийся должен: уметь: осуществлять разработку кода программного модуля на языках низкого и высокого уровней; создавать программу по разработанному алгоритму как отдельный модуль; знать: основные этапы разработки программного обеспечения; основные принципы технологии структурного и объектно-ориентированного программирования; Вышеперечисленные умения, знания и практический опыт направлены на формирование следующих профессиональных и общих компетенций обучающихся: ПК 1.1 Формировать алгоритмы разработки программных модулей в соответствии с техническим заданием. ПК 1.2 Разрабатывать программные модули в соответствии с техническим заданием. ОК 1. Выбирать способы решения задач профессиональной деятельности, применительно к различным контекстам ОК 2. Осуществлять поиск, анализ и интерпретацию информации, необходимой для выполнения задач профессиональной деятельности ОК 4. Работать в коллективе и команде, эффективно взаимодействовать с коллегами, руководством, клиентами. ОК 5. Осуществлять устную и письменную коммуникацию на государственном языке с учетом особенностей социального и культурного контекста. ОК 9. Использовать информационные технологии в профессиональной деятельности 2 Перечень практических работ УД МДК 01.01 Разработка программных модулей Название практических работ Количество часов Тема 1.1.2 Структурное программирование Практическая работа №1 Оценка сложности алгоритмов сортировки. 2 Практическая работа №2 Оценка сложности алгоритмов поиска. 2 Практическая работа №3 Оценка сложности рекурсивных алгоритмов. 2 Практическая работа №4 Оценка сложности эвристических алгоритмов. 4 Тема 1.1.3Объектно-ориентированное программирование Практическая работа №5 Работа с классами. 2 Практическая работа №6 Перегрузка методов. 2 Практическая работа №7 Определение операций в классе. 1 Практическая работа №8 Создание наследованных классов 1 Практическая работа №9 Работа с объектами через интерфейсы. 2 Практическая работа №10 Использование стандартных интерфейсов. 2 Практическая работа №11 Работа с типом данных структура. 2 Практическая работа №12 Коллекции. Параметризованные классы. 2 Практическая работа №13 Использование регулярных выражений 1 Практическая работа №14 Операции со списками. 1 Тема 1.1.4Паттерны проектирования Практическая работа №15 Использование основных шаблонов. 2 Практическая работа №16 Использование порождающих шаблонов. 2 Практическая работа №17 Использование структурных шаблонов. 4 Практическая работа №18 Использование поведенческих шаблонов. 4 Тема 1.1.5. Событийно-управляемое программирование Практическая работа №19 Разработка приложения с использованием текстовых компонентов 2 Практическая работа №20 Разработка приложения с несколькими формами. 2 Практическая работа №21 Разработка приложения с не визуальными компонентами. 4 Практическая работа №22 Разработка игрового приложения. 4 Практическая работа №23 Разработка приложения с анимацией. 4 Тема 1.1.6 Оптимизация и рефакторинг кода Практическая работа №24 Оптимизация и рефакторинг кода. 16 Тема 1.1.7 Разработка пользовательского интерфейса. Практическая работа №25 Разработка интерфейса пользователя. 12 Тема 1.1.8 Основы ADO.Net Практическая работа №26 Создание приложения с БД 8 Практическая работа №27 Создание запросов к БД 4 Практическая работа №28 Создание хранимых процедур 7 Итого: 101 час 3 Инструктивно-методические указания по выполнению практических работ Практическая работа №1 Оценка сложности алгоритмов сортировки Цель работы: изучить основные алгоритмы внутренних сортировок и научиться решать задачи сортировок массивов различными методами (бинарная пирамидальная сортировка, метод Шелла, быстрая сортировка Хоара, сортировка слиянием). При выполнении лабораторной работы для каждого задания требуется написать программу на языке С++, которая получает на входе числовые данные, выполняет генерацию и вывод массива указанного типа в зависимости от постановки задачи. В каждой задаче необходимо выполнить сортировку данных и реализовать один из алгоритмов: бинарной пирамидальной сортировки, сортировки по методу Шелла, быстрой сортировки Хоара и сортировки слиянием в виде отдельных функций. Ввод данных осуществляется с клавиатуры или из файла с учетом требований к входным данным, содержащихся в постановке задачи. Ограничениями на входные данные является диапазон используемого числового типа данных в языке С++ и максимально допустимый размер объявляемого одномерного массива. Теоретические сведения. Ознакомьтесь с материалом лекции 42. Задания к лабораторной работе. Выполните приведенные ниже задания. 1. На основании приведенных в лекции 42 функций реализуйте алгоритмы внутренних сортировок. 2. Даны два целочисленных файла, упорядоченных по возрастанию. Сформировать третий файл на основе данных, который также упорядочен и представляет операцию с элементами исходных файлов: o объединение (содержит числа, принадлежащие хотя бы одному из множеств); o перечисление (числа, принадлежащие обоим множествам); o разность (числа, принадлежащие первому множеству, но не второму); o симметричную разность (объединение разностей множеств). 3. Заданы N (N<=5000) попарно различных длин отрезков. Вычислить количество способов, которыми из отрезков можно сложить треугольник. 4. Дана целочисленная квадратная матрица размером n. Упорядочить значения так, чтобы a 11 <=a 12 <=<=a 1n <=a 21 <=a 22 <=<=a 2n <=<=a n1 <=a n2 <=<=a nn 5. Дан целочисленный массив. Выполните проверку уникальности. Удалите из массива повторные вхождения чисел. Указания к выполнению работы. Каждое задание необходимо решить в соответствии с изученными алгоритмами внутренних сортировок: бинарной пирамидальной сортировки, сортировки по методу Шелла, быстрой сортировки Хоара и сортировки слиянием. Программные коды следует реализовать на языке С++. Рекомендуется воспользоваться материалами лекции 42, где подробно рассматриваются описание используемых в работе алгоритмов, примеры их реализации на языке С++. Программу для решения каждого задания необходимо разработать методом процедурной абстракции, используя функции. Этапы решения сопроводить комментариями в коде. В отчете следует отразить разработку и обоснование математической модели решения задачи и примеры входных и выходных файлов. Следует реализовать каждое задание в соответствии с приведенными этапами: изучить словесную постановку задачи, выделив при этом все виды данных; сформулировать математическую постановку задачи; выбрать метод решения задачи, если это необходимо; разработать графическую схему алгоритма; записать разработанный алгоритм на языке С++; разработать контрольный тест к программе; отладить программу; представить отчет по работе. Требования к отчету. Отчет по лабораторной работе должен соответствовать следующей структуре. Титульный лист. Словесная постановка задачи. В этом подразделе проводится полное описание задачи. Описывается суть задачи, анализ входящих в нее физических величин, область их допустимых значений, единицы их измерения, возможные ограничения, анализ условий при которых задача имеет решение (не имеет решения), анализ ожидаемых результатов. Математическая модель. В этом подразделе вводятся математические описания физических величин и математическое описание их взаимодействий. Цель подраздела – представить решаемую задачу в математической формулировке. Алгоритм решения задачи. В подразделе описывается разработка структуры алгоритма, обосновывается абстракция данных, задача разбивается на подзадачи. Схема алгоритма выполняется по ЕСПД (ГОСТ 19.003-80 и ГОСТ 19.002-80). Листинг программы. Подраздел должен содержать текст программы на языке программирования С++, реализованный в среде MS Visual Studio 2010. Контрольный тест. Подраздел содержит наборы исходных данных и полученные в ходе выполнения программы результаты. Выводы по лабораторной работе. Ответы на контрольные вопросы. Контрольные вопросы 1. Чем можно объяснить многообразие алгоритмов сортировок? 2. Почему на данный момент не существует универсального алгоритма сортировки? 3. Как соблюдение свойств устойчивости и естественности влияет на трудоемкость алгоритма сортировки? 4. За счет чего в алгоритмах быстрых сортировок происходит выигрыш при выполнении операций сравнения и перестановок? 5. Какие из перечисленных алгоритмов наиболее эффективны на почти отсортированных массивах: бинарная пирамидальная сортировка, сортировка слиянием, сортировка Шелла и сортировка Хоара? За счет чего происходит выигрыш? 6. Почему алгоритмы быстрых сортировок не дают большого выигрыша при малых размерах массивов? 7. В чем преимущества и недостатки по отношению друг к другу следующих алгоритмов сортировок: бинарная пирамидальная сортировка, сортировка слиянием, сортировка Шелла и сортировка Хоара? 8. Как определить, какому алгоритму сортировки отдать предпочтение при решении задачи? Практическая работа №2 Оценка сложности алгоритмов поиска Цель работы: изучить основные алгоритмы поиска Теоретические сведения Правильность — далеко не единственное качество, которым должна обладать хорошая программа. Одним из важнейших является эффективность, характеризующая прежде всего время выполнения программы для различных входных данных (параметра ). Нахождение точной зависимости для конкретной программы — задача достаточно сложная. По этой причине обычно ограничиваются асимптотическими оценками этой функции, то есть описанием ее примерного поведения при больших значениях параметра Иногда для асимптотических оценок используют традиционное отношение (читается "О большое") между двумя функциями , определение которого можно найти в любом учебнике по математическому анализу, хотя чаще применяют отношение эквивалентности (читается "тэта большое"). Его формальное определение есть, например, в книге [8], хотя нам пока достаточно будет понимания данного вопроса в общих чертах. В качестве первого примера вернемся к только что рассмотренным программам нахождения факториала числа. Легко видеть, что количество операций, которые должны быть выполнены для нахождения факториала ! числа в первом приближении прямо пропорционально этому числу, ибо количество повторений цикла (итераций) в данной программе равно В подобной ситуации принято говорить, что программа (или алгоритм) имеет линейную сложность (сложность или ). Можно ли вычислить факториал быстрее? Оказывается, да. Можно написать такую программу, которая будет давать правильный результат для тех же значений , для которых это делают все приведенные выше программы, не используя при этом ни итерации, ни рекурсии. Ее сложность будет , что фактически означает организацию вычислений по некоторой формуле без применения циклов и рекурсивных вызовов! Не менее интересен и пример вычисления -го числа Фибоначчи. В процессе ее исследования фактически уже было выяснено, что ее сложность является экспоненциальной и равна . Подобные программы практически не применимы на практике. В этом очень легко убедиться, попробовав вычислить с ее помощью 40-е число Фибоначчи. По этой причине вполне актуальна следующая задача. Задача 5.4. Напишите программу, печатающую -ое число Фибоначчи, которая имела бы линейную сложность. Вот решение этой задачи, в котором переменные j и k содержат значения двух последовательных чисел Фибоначчи. Текст программы public class FibIv1 { public static void main(String[] args) throws Exception { int n = Xterm.inputInt("Введите n -> "); Xterm.print("f(" + n + ")"); if (n < 0) { Xterm.print(" не определено\n"); } else if (n < 2) { Xterm.println(" = " + n); } else { long i = 0; long j = 1; long k; int m = n; while (--m > 0) { k = j; j += i; i = k; } Xterm.println(" = " + j); } } } Следующий вопрос вполне естественен — а можно ли находить числа Фибоначчи еще быстрее? После изучения определенных разделов математики совсем просто вывести следующую формулу для -ого числа Фибоначчи , которую легко проверить для небольших значений : Может показаться, что основываясь на ней, легко написать программу со сложностью , не использующую итерации или рекурсии. Текст программы public class FibIv2 { public static void main(String[] args) throws Exception { int n = Xterm.inputInt("Введите n -> "); double f = ( 1.0 + Math.sqrt(5.) ) / 2.0; int j = (int)( Math.pow(f,n) / Math.sqrt(5.) + 0.5 ); Xterm.println("f(" + n + ") = " + j); } } На самом деле эта программа использует вызов функции возведения в степень { Math.pow(f,n) }, которая не может быть реализована быстрее, чем за логарифмическое время ( ). Про алгоритмы, в которых количество операций примерно пропорционально (в информатике принято не указывать основание двоичного логарифма) говорят, что они имеет логарифмическую сложность ( ). Для вычисления -го числа Фибоначчи существует такой алгоритм, программную реализацию которого мы приведем без дополнительных комментариев, — иначе нужно объяснять слишком много (связь чисел Фибоначчи со степенями некоторой матрицы порядка два, использование классов для работы с матрицами, алгоритм быстрого возведения матрицы в степень). Задача 5.5. Напишите программу, печатающую -ое число Фибоначчи, которая имела бы логарифмическую сложность. Текст программы public class FibIv3 { public static void main(String[] args) throws Exception { int n = Xterm.inputInt("Введите n -> "); Xterm.print("f(" + n + ")"); if (n < 0) { Xterm.println(" не определено"); } else if (n < 2) { Xterm.println(" = " + n); } else { Matrix b = new Matrix(1, 0, 0, 1); Matrix c = new Matrix(1, 1, 1, 0); while (n>0) { if ((n&1) == 0) { n >>>= 1; c.square(); } else { n -= 1; b.mul(c); } } Xterm.println(" = " + b.fib()); } } } class Matrix { private long a, b, c, d; public Matrix(long a, long b, long c, long d) { this.a = a; this.b = b; this.c = c; this.d = d; } public void mul(Matrix m) { long a1 = a*m.a+b*m.c; long b1 = a*m.b+b*m.d; long c1 = c*m.a+d*m.c; long d1 = c*m.b+d*m.d; a = a1; b = b1; c = c1; d = d1; } public void square() { mul(this); } public long fib() { return b; } } Если попробовать посчитать десятимиллионное число Фибоначчи с помощью этой и предыдущей программ, то разница во времени счета будет вполне очевидной. К сожалению, результат будет неверным (в обоих случаях) в силу ограниченности диапазона чисел типа long. В заключение приведем сравнительную таблицу времен выполнения алгоритмов с различной сложностью и объясним, почему с увеличением быстродействия компьютеров важность использования быстрых алгоритмов значительно возрастает. Рассмотрим четыре алгоритма решения одной и той же задачи, имеющие сложности , , и соответственно. Предположим, что второй из этих алгоритмов требует для своего выполнения на некотором компьютере при значении параметра ровно одну минуту времени. Тогда времена выполнения всех этих четырех алгоритмов на том же компьютере при различных значениях параметра будут примерно такими, как в таблице 5.1. Таблица 5.1. Сравнительная таблица времен выполнения алгоритмов |