КОСы по УД ОП.08 "Теория алгоритмов" специальности 09.02.03 "Программирование в компьютерных системах"

МЕТОДИЧЕСКИЕ  РЕКОМЕНДАЦИИ  ДЛЯ   СТУДЕНТОВ	Ульяновский авиационный колледж
	ПРОФЕССИОНАЛЬНЫЙ  ЦИКЛ
	ТЕОРИЯ АЛГОРИТМОВ ОЦЕНОЧНЫЕ СРЕДСТВА для проведения промежуточной аттестации на специальности СПО базовой подготовки 230115  Программирование в компьютерных системах Форма проведения оценочной процедуры - ЭКЗАМЕН Ульяновск  2014

ОДОБРЕНЫ на заседании ЦМК Программирования и ИТ Протокол № 2 от «10» сентября  2014 г. Председатель ЦМК: _________________ Шарифуллина А.А.	УТВЕРЖДАЮ Зам. директора по учебной работе _______________ Г.В.Знаенко     «     »                       2014 г.
РАЗРАБОТЧИК: Шарифуллина А.А.  преподаватель высей категории Ульяновского авиационного колледжа.

СОДЕРЖАНИЕ

			стр.
I  ПАСПОРТ КОМПЛЕКТА ОЦЕНОЧНЫХ СРЕДСТВ
1.1	Контроль и оценка результатов освоения учебной дисциплины……………..		4
1.2	Предмет и объект оценивания ……………………………………………………		6
1.3	Организация контроля и оценки освоения программы учебной дисциплины		6
II  КОМПЛЕКТ ОЦЕНОЧНЫХ СРЕДСТВ
2.1		Структура экзаменационного билета……………………………………………	7
2.2		Задания для подготовки обучающихся  к экзамену…………………………….	7
2.3		Критерии оценивания заданий………………………………………………….	10
ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА………………………………………………….			12

I. ПАСПОРТ КОМПЛЕКТА ОЦЕНОЧНЫХ СРЕДСТВ

1.1.Контроль и оценка результатов освоения учебной дисциплины

Результаты обучения (освоенные умения, усвоенные знания)	Основные показатели оценки результата
1	2
УМЕНИЯ:
У1- разрабатывать алгоритмы для конкретных задач;	- правильная поставка задачи; - правильное построение математической модели задачи; - определение использования базовых алгоритмических конструкций для разработки алгоритма задачи;  - правильная запись алгоритмических конструкций на языке блок-схем; - составление теста для проверки правильности работы составленного алгоритма.
У2- определять сложность работы алгоритмов;	- выбор критерия для оценки сложности алгоритма; - выполнение расчета сложности по одному из методов оценки сложности (метод Кирхгофа, метод Маркова);  - правильная оценка сложности по результатам расчетов.
ЗНАНИЯ:
З1 - основные модели алгоритмов;	- изложение определений терминов: алгоритм, линейный алгоритм, ветвление, выбор, цикл; - изложение правил исполнения и свойств алгоритма; - изображение алгоритмических конструкций: следование, ветвление, выбор, цикл на языке блок-схем; - изображение вспомогательного алгоритма на языке блок-схем;
З2 - методы построения алгоритмов;	- изложение основных положений структурного подхода в разработке алгоритмов; - изложение модульного подхода в разработке алгоритмов; - изложение нисходящего метода разработки алгоритмов; - изложение восходящего метода в разработке алгоритмов.
З3 - методы вычисления сложности алгоритмов;	- изложение метода Кирхгофа для оценки сложности алгоритма; - изложение метода Маркова для оценки сложности алгоритма.
ОБЩИЕ КОМПЕТЕНЦИИ
ОК1 – понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.
ОК2 – Организовывать собственную деятельность, выбирать типовые методы и способы выполнения профессиональных задач, оценивать из эффективность и качество.	- организует собственную деятельность; - осуществляет выбор типового метода решения задачи; - решает задачу выбранным методом; - оценивает эффективность и качество выпяленного решения.
ОК3 – принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.	- определяет задачу как стандартную или нестандартную; - выполняет постановку нестандартной задачи;
ОК4 – Осуществлять поиск и использование информации, необходимой для эффективного выполнения профессиональных задач, профессионального и личностного развития.	-   владение методами и способами поиска информации; -   осуществление оценки значимости информации для выполнения профессиональных задач; -   классифицирует и обобщает информацию; -          оценивает полноту и достоверность информации
ОК5 – Использовать информационно – коммуникационные технологии в профессиональной деятельности	-   владение персональным компьютером; -   осуществление поиска информации в сети интернет и различных электронных носителях -   использование программного обеспечения в решении профессиональных задач; -   использование средств ИТ для обработки и хранения информации; -          создание  презентации в различных формах.
ОК8 – Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.
ОК9 – Ориентироваться в условиях частой смены технологий в профессиональной деятельности.	- использует актуальный ГОСТ на разработку блок-схем алгоритмов;
ОК10 – Исполнять воинскую обязанность, в том числе с применением полученных профессиональных знаний.
ПРОФЕССИОНАЛЬНЫЕ КОМПЕТЕНЦИИ
ПК 1.1 Выполнять разработку спецификаций отдельных компонент.	- определяет необходимость использования базовых алгоритмических конструкций для разработки спецификаций отдельных компонент; - записывает алгоритмы работы отдельных компонент на языке блок-схем.
ПК 1.2 Осуществлять разработку кода программного продукта на основе готовых спецификаций на уровне модуля.	-   устанавливает соответствие спецификации  базовых алгоритмических конструкций  требованиям разработки.

1.2.Предмет и объект оценивания

Предмет оценивания	Объект оценивания
З1-З3, ОК3, ОК4, ОК5	Вопрос 1. ТЕОРЕТИЧЕСКОЕ ЗАДАНИЕ
У1, У2, ОК1, ОК2, ОК7, ОК8, ОК9, ОК10, ПК 1.1, ПК 1.2	Вопрос 2. ПРАКТИЧЕСКОЕ ЗАДАНИЕ А) Составление алгоритма решения задачи В) Оценка алгоритмической сложности составленного алгоритма

 

1.3.Организация контроля и оценки освоения программы учебной дисциплины

№	Форма итогового контроля	Критерии положительной аттестации
5 семестр	ЭКЗАМЕН	Условием допуска к промежуточной аттестации является положительная текущая аттестация. Экзаменационная отметка выставляется исходя  из демонстрации освоенных  умений, знаний и компетенций  по контролируемым показателям.

 

 

II. КОМПЛЕКТ ОЦЕНОЧНЫХ СРЕДСТВ

2.1.Структура экзаменационного  билета

Ø ЦЕЛЬ: проверить уровень сформированности  образовательных результатов обучающихся по учебной дисциплине

Ø ПРОВЕРЯЕМЫЕ ОБРАЗОВАТЕЛЬНЫЕ РЕЗУЛЬТАТЫ: У1,У2, З1-З3,

Ø СТРУКТУРА ИНДИВИДУАЛЬНОГО ЭКЗАМЕНАЦИОННОГО  БИЛЕТА

№ вопроса	Задание	К-во	Вопросы формируются из №№ заданий
1	ТЕОРЕТИЧЕСКОЕ ЗАДАНИЕ	1	1.1 - 1.24
2	ПРАКТИЧЕСКОЕ ЗАДАНИЕ Составление алгоритма решения задачи Оценка алгоритмической сложности составленного алгоритма	2	2.1 – 2.24

Ø ОБОРУДОВАНИЕ: чертежные принадлежности.    

Ø  ВРЕМЯ ДЛЯ ПОДГОТОВКИ: 45 мин.

Ø  ОЦЕНИВАНИЕ: 1 вопрос  -20 баллов;

2 вопрос - 40 баллов;

3 вопрос -40 баллов

Ø  КИТЕРИИ ОТМЕТОК: «5»         ³ 81%  правильных ответов

«4» = 61– 80%  правильных ответов    

«3» = 39 – 60% правильных ответов

«2» < 39%  правильных ответов

ПРИМЕЧАНИЕ:

1. Не разрешается пользоваться справочниками и таблицами, выходить из аудитории.

2. Отметка ставится только на основании правильных ответов; за  ошибочные ответы баллы не снимаются.

2.2.Задания  для подготовки обучающихся  к экзамену

Вопрос 1. ТЕОРЕТИЧЕСКОЕ ЗАДАНИЕ:

1.1.         Перечислите основные этапы решения задачи на ЭВМ. Каковы действия программиста на каждом из этапов.

1.2.         Дайте определение алгоритма решения задачи.

1.3.         Перечислите свойства алгоритмов. Поясните каждое из свойств. Приведите пример записи не являющейся алгоритмом, так как нарушено одно из свойств.

1.4.         Перечислите правила исполнения алгоритмов. Дайте определение линейного алгоритма.

1.5.         Перечислите алгоритмические языки. Приведите пример записи алгоритма на естественном – алгоритмическом языке.

1.6.         Назовите стандарт записи алгоритмов на графическом языке. Перечислите основные геометрические примитивы используемые для записи алгоритмов на языке блок-схем.

1.7.         Назовите стандарт записи алгоритмов на графическом языке. Перечислите правила записи алгоритмов на алгоритмическом языке блок-схем.

1.8.         Дайте определение алгоритмической конструкции ветвление Назовите формы записи ветвлений. Выполите запись на языке блок – схем ветвления каждой формы. Продемонстрируйте свойства ветвлений на примере решения задачи сравнения трех чисел.

1.9.         Дайте определение условия используемого в записи алгоритмических конструкций. Дайте определение составного условия. Укажите логические конструкции используемые в записи составных условий, приведите их таблицы истинности.

1.10.     Дайте определение алгоритмической конструкции цикл. Назовите виды циклов.

1.11.     Дайте определение алгоритмической конструкции цикл с предусловием. Выполните запись цикла с предусловием на языке блок – схем. Назовите правила исполнения цикла с предусловием. Дайте определение ситуации зацикливание. Как избежать зацикливания в циклах с предусловием.

1.12.     Дайте определение алгоритмической конструкции цикл с постусловием. Выполните запись цикла с постусловием на языке блок – схем. Назовите правила исполнения цикла с постусловием. Дайте определение ситуации зацикливание. Как избежать зацикливания в циклах с предусловием.

1.13.     Дайте определение алгоритмической конструкции цикл с параметром. Выполните запись цикла с параметром на языке блок – схем. Запишите закон изменения параметра, поясните его составляющие. Перечислите правила составления циклов с параметрами.

1.14.     Дайте определение алгоритмической конструкции выбор. Выполните запись выбора на языке блок – схем.

1.15.     Перечислите основные положения структурного подхода в разработке алгоритмов. Перечислите базовые структурные конструкции. Перечислите расширения базовых структурных конструкций.

1.16.     Назовите правила записи структурных алгоритмов в соответствии с методом Дамке.

1.17.     Назовите правила записи структурных алгоритмов в соответствии с методом структурограмм.

1.18.     Перечислите основные положения модульного подхода в разработке алгоритмов. Дайте определение модуля. Перечислите достоинства и недостатки модульного подхода.

1.19.     Назовите основные положения разработки алгоритмов в соответствии с методом нисходящего проектирования.

1.20.     Назовите основные положения разработки алгоритмов в соответствии с методом восходящего проектирования.

1.21.     Дайте определение понятия алгоритмическая сложность. Перечислите по каким критериям определяется алгоритмическая сложность.

1.22.     Перечислите правила построения операторной схемы. Поясните составляющие теоретико-множественного описания операторных схем.

1.23.     Перечислите правила оценки алгоритмической сложности в соответствии с методом Кирхгофа.

1.24.     Перечислите правила оценки алгоритмической сложности в соответствии со схемой Маркова.

Вопрос 2. ПРАКТИЧЕСКОЕ ЗАДАНИЕ (в каждом задании А и В)

A.    Составление алгоритма решения задачи

B.     Оценка алгоритмической сложности составленного алгоритма

2.1.         Дано число k (0 < k < 11) и таблица размера 4 x 10 заполненная целыми числами. Найти сумму и произведение элементов k - го столбца данной таблицы.

2.2.         Дана таблица размера 5 x 9 заполненная целыми числами. Найти суммы элементов в каждой четной строке и каждом четном столбце.

2.3.         Дана таблица размера 5 x 10 заполненная целыми числами. Найти минимальное и максимальное значение в каждой строке.

2.4.         Дана таблица размера 5 x 10 заполненная целыми числами. В каждой строке найти среднее арифметическое всех элементов этой строки.

2.5.         Дана таблица размера 5 x 10 заполненная целыми числами. Преобразовать эту таблицу, поменяв местами минимальный и максимальный элемент в каждой строке.

2.6.         Дана таблица размера 5 x 10 заполненная целыми числами. Найти минимальное  значение среди сумм элементов ее строк и столбцов и номер строки (столбца) с этим минимальным значением.

2.7.         Дана таблица размера 5 x 10 заполненная целыми числами. Найти минимальное значение среди максимальных элементов каждой строки и столбца.

2.8.         Дана таблица размера 6 x 10 заполненная целыми числами. Найти количество ее столбцов, все элементы которых различны.

2.9.         Дана таблица размера 4 x 9 заполненная целыми числами. Вывести номера строк, содержащих одинаковые элементы.

2.10.     Дана квадратная таблица порядка 5 заполненная целыми числами. Найти суммы элементов расположенных на главной и побочной диагонали.

2.11.     Дана квадратная таблица порядка 5 заполненная целыми числами. Заменить нулями элементы матрицы, лежащие ниже главной и выше побочной диагонали.

2.12.     Дана квадратная таблица порядка 5 заполненная целыми числами. Заменить нулями элементы, лежащие одновременно выше главной диагонали (включая эту диагональ) и выше побочной диагонали (также включая эту диагональ).

2.13.     Дана таблица размера 5 x 10 заполненная целыми числами. Вывести номера строк, элементы которых монотонно возрастают.

2.14.     Дана таблица размера 5 x 10 заполненная целыми числами. Найти минимальный среди элементов тех строк, которые упорядочены либо по возрастанию. Если такие строки отсутствуют, то вывести 0.

2.15.     Даны два числа k1 и k2 и таблица размера 4 x 10 заполненная целыми числами. Поменять местами строки таблицы с номерами k1 и k2.

2.16.     Дана таблица размера 5 x 10 заполненная целыми числами. Поменять местами строки, содержащие минимальный и максимальный элементы таблицы.

2.17.     Дана таблица размера 5 x 10 заполненная целыми числами. Поменять местами столбец с номером 1 и первый из столбцов, содержащих только положительные элементы.

2.18.     Дано число k и таблица размера 4 x 10 заполненная целыми числами. Удалить строку таблицы с номером k.

2.19.     Дана таблица размера 5 x 10 заполненная целыми числами. Удалить столбец, содержащий минимальный элемент таблицы.

2.20.     Дана таблица размера 5 x 10 заполненная целыми числами. Удалить первый столбец, содержащие только положительные элементы.

2.21.     Дано число k и таблица размера 4 x 9 заполненная целыми числами. Перед строкой таблицы с номером k вставить строку из нулей.

2.22.     Дана таблица размера 4 x 9 заполненная целыми числами. Продублировать строку таблицы, содержащий ее минимальный элемент.

2.23.     Дана таблица размера 5 x 9 заполненная целыми числами. Перед столбцом, содержащим минимальный элемент, добавить столбец, состоящий из единиц.

2.24.     Дана таблица размера 5 x 10 заполненная целыми числами. Вывести номера строк, элементы которых монотонно убывают.

2.3.Критерии оценивания заданий

Вопрос 1.ТЕОРЕТИЧЕСКОЕ ЗАДАНИЕ (max 20 баллов)

Ø  18-20 баллов (к= 0,9-1,0) ставится от максимального количества баллов, если студент:

ü полно раскрыл содержание материала в объеме, предусмотренном рабочей программой,

ü изложил материал грамотным языком в определенной логической последовательности, точно используя специальную терминологию;

ü правильно выполнил рисунки, чертежи, сопутствующие ответу;

ü отвечал самостоятельно без наводящих вопросов преподавателя. Возможны одна - две неточности при освещении второстепенных вопросов или в выкладках, которые студент легко исправил по замечанию преподавателя.

Ø  15-17 баллов (к=0,75-0,85) ставится, если ответ удовлетворяет  основным требованиям, но при этом имеет один из недостатков:

ü в изложении допущены небольшие пробелы, не исказившие содержание ответа;

ü допущены один – два недочета при освещении основного содержания ответа, исправленные по замечанию преподавателя;

ü допущена ошибка или имеется более двух недочетов при освещении второстепенных вопросов или в выкладках, легко исправленные по замечанию преподавателя.

Ø  10-14 баллов (к=0,5-0,7) ставится в следующих случаях:

ü неполно или непоследовательно раскрыто содержание материала, но показано общее понимание вопроса;

ü имелись затруднения или допущены ошибки в определении понятий, использовании терминологии и  выкладках (определениях), исправленные после нескольких наводящих вопросов преподавателя;

ü при знании теоретического материала выявлена недостаточная сформированность основных умений и навыков.

Ø  5-9 баллов (к=0,25-0,45) ставится в следующих случаях:

ü не раскрыто основное содержание учебного материала;

ü обнаружено незнание или непонимание студентом большей или наиболее важной части учебного материала;

ü допущены ошибки в определении понятий, при использовании терминологии, в выкладках, которые не исправлены после нескольких наводящих вопросов преподавателя.

Ø  меньше  5 баллов (к=0-0,25) ставится, если:

ü студент обнаружил полное незнание и непонимание изучаемого учебного материала или не смог ответить ни на один из по­ставленных вопросов по изучаемому материалу.

Вопрос 2 .ПРАКТИЧЕСКОЕ ЗАДАНИЕ.

(max 80 баллов: А – 40 баллов, В – 40 баллов)

Ø  36-40 баллов (к= 0,9-1,0) ставится если студент:

ü полностью выполнил все требования  индивидуального задания;

ü отвечал самостоятельно без наводящих вопросов преподавателя. Возможны одна - две неточности при освещении второстепенных вопросов или в выкладках, которые студент легко исправил по замечанию преподавателя.

Ø  31-35 баллов (к= 0,78 -0,88) ставится, если ответ удовлетворяет  основным требованиям, но при этом имеет один из недостатков:

ü в выполнении допущены небольшие неточности, не исказившие решение задания;

ü допущены один – два недочета при освещении основного содержания ответа, исправленные по замечанию преподавателя;

ü допущены ошибка или более двух недочетов при освещении второстепенных вопросов или в выкладках, легко исправленные по замечанию преподавателя.

Ø  26-30 баллов(к= 0,65-0,75)  ставится в следующих случаях:

ü допущены неточности в выполнении индивидуального задания, но показано общее понимание вопроса;

ü имелись затруднения или допущены ошибки в выполнении индивидуального задания, но осуществлены значительные  исправления после нескольких наводящих вопросов преподавателя;

Ø  20-25 баллов (к= 0,5-0,63)  ставится в следующих случаях:

ü не в полном объеме решена поставленная задача;

ü обнаружено значительные отклонения в выполнении индивидуального задания;

ü после нескольких замечаний преподавателя не исправлены неточности в выполнении индивидуального задания.

Ø  меньше 20 баллов (к= 0 - 0,49) ставится, если:

ü студент обнаружил полное незнание и непонимание изучаемого учебного материала или не смог выполнить задание.

 

 

ИСПОЛЬЗОВАННАЯ  ЛИТЕРАТУРА

1.      Математическая логика и теория алгоритмов: учеб. пособие для студ. высш. учеб. заведений/ В.И. Игошин. – 3-е изд., стер. – М.: Издательский центр «Академия», 2010. - 448 с.

2.      Теория алгоритмов: учеб. пособие для студ. сред. проф. учеб. заведений / В.И. Игошин. - М.: Издательский центр «Академия», 2013. - 320 с.

3.      Математическая логика и теория алгоритмов: учебное пособие / Гуц А.К. Изд. стер. – М.: Либроком, 2014. – 120 с.

ИНТЕРНЕТ-РЕСУРСЫ:

4.      Бесплатная библиотека стандартов и нормативов.[Электронный ресурс]. Режим доступа: www.docload.ru/Basesdoc.