Комплект оценочных средств для проведения промежуточной аттестации по программе учебной дисциплины Теория алгоритмов

БУ «НИЖНЕВАРТОВСКИЙ ПОЛИТЕХНИЧЕСКИЙ КОЛЛЕДЖ»
Утверждаю
Заместитель директора по УР
___________ В.В. Геталова« » ____________ 201__г
Комплект оценочных средств
для проведения промежуточной аттестации
по программе учебной дисциплины
ОП.08 ТЕОРИЯ АЛГОРИТМОВ
программы подготовки специалистов среднего звена по специальности
230115 программирование в компьютерных системах
Нижневартовск, 2016
Комплект оценочных средств для проведения промежуточной аттестации по учебной дисциплине ОП.08 «Теория алгоритмов» разработан в соответствии с требованиями федерального государственного образовательного стандарта (ФГОС) по специальности/профессии 230115 Программирование в компьютерных системах.
Организация-разработчик: бюджетное учреждение среднего профессионального образования Ханты-Мансийского автономного округа - Югры «Нижневартовский политехнический колледж».
Разработчик:
Шалыгина Т.С., преподаватель бюджетного учреждения среднего профессионального образования Ханты-Мансийского автономного округа - Югры «Нижневартовский политехнический колледж».
Рассмотрено на заседании
__________________________________________,
протокол от _______________________________
Заведующий кафедрой _______________________
ПАСПОРТ КОМПЛЕКТА ОЦЕНОЧНЫХ СРЕДСТВ
Общие положения
Результатом освоения УД ОП.08 «Теория алгоритмов» являются, подлежащие проверке
умения:
разрабатывать алгоритмы для конкретных задач;
определять сложность работы алгоритмов;
знания:
основные модели алгоритмов;
методы построения алгоритмов;
методы вычисления сложности работы алгоритмов;

Формой промежуточной аттестации по УД является экзамен.

Матрица логических связей между видами аттестации, формами, методами оценивания и объектами, предметами контроля по дисциплине ОП.08 «Теория алгоритмов»
предметы оценивания
(ПК, ОК, знания, умения – заданные ФГОС)
объекты оценивания вид аттестации формы и методы оценивания критерии и показатели оценки вид оценочных средств
ОК 1. Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.
ОК 2. Организовывать собственную деятельность, определять методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.
ОК 3. Решать проблемы, оценивать риски и принимать решения в нестандартных ситуациях.
ОК 4. Осуществлять поиск, анализ и оценку информации, необходимой для постановки и решения профессиональных задач, профессионального и личностного развития.
ОК 5. Использовать информационно-коммуникационные технологии для совершенствования профессиональной деятельности.
ОК 6. Работать в коллективе и команде, обеспечивать ее сплочение, эффективно общаться с коллегами, руководством, потребителями.
ОК 7. Ставить цели, мотивировать деятельность подчиненных, организовывать и контролировать их работу с принятием на себя ответственности за результат выполнения заданий.
ОК 8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.
ОК 9. Быть готовым к смене технологий в профессиональной деятельности.
ОК 10. Исполнять воинскую обязанность, в том числе с применением полученных профессиональных знаний (для юношей).
ПК 1.1. Выполнять разработку спецификаций отдельных компонент.
ПК 1.2. Осуществлять разработку кода программного продукта на основе готовых спецификаций на уровне модуля. уметь:
разрабатывать алгоритмы для конкретных задач;
определять сложность работы алгоритмов
знать:
основные модели алгоритмов;
методы построения алгоритмов;
методы вычисления сложности работы алгоритмов
Требования к уровню подготовки квалифицированного рабочего в соответствии со стандартами Экзамен Балльное
Дифференцированное
Наблюдение
Устный индивидуальный опрос, фронтальный опрос
Письменный контроль
Тестовый контроль Знание материала содержание материала раскрыто в полном объеме, предусмотренным программой и учебником;
не полно раскрыто содержание материала, но показано общее понимание вопроса, достаточное для дальнейшего изучения программного материала;
не раскрыто основное содержание учебного материала
Последовательность изложения содержание материала раскрыто последовательно, достаточно хорошо продумано;
последовательность изложения материала недостаточно продумана;
путаница в изложении материала
Владение речью и терминологией материал изложен грамотным языком, с точным использованием терминологии;
в изложении материала имелись затруднения и допущены ошибки в определении понятий и в использовании терминологии;
допущены ошибки в определении понятий
Применение конкретных примеров показано умение иллюстрировать материал конкретными примерами;
приведение примеров вызывает затруднение;
неумение приводить примеры при объяснении материала
Знание ранее изученного материала продемонстрировано усвоение раннее изученного материала;
с трудом вспоминает раннее изученный материал;
незнание ранее изученного материала
Степень самостоятельности содержание материала изложено самостоятельно, без наводящих вопросов;
содержание материала излагалось с помощью наводящих вопросов и подсказок;
содержание материала излагалось с многочисленными подсказками, показавшими незнание или непонимание большей части учебного материала
Степень активности в процессе принимает активное участие в изложении или в обсуждении изучаемого материала;
малоактивное, эпизодическое участие в изложении или обсуждении изучаемого материала;
принимает роль пассивного слушателя
Выполнение регламента материал изложен в строго определенные рамки, ответы лаконичны;
изложение материала растянуто;
регламент выступления не соблюден
Тест
Перечень вопросов
II. Комплект оценочных средств по дисциплине
Для обучающегося:
Количество тестовых заданий для выполнения – 25 вопросов для каждого варианта.
Максимальное время выполнения тестовых заданий - 40 мин.
Ответы на тестовые задания заносятся в бланк тестового задания.
2.1 Задания в тестовой форме
I вариант
Как называется графическое представление алгоритма:
последовательность формул;
блок-схема;
таблица;
словесное описание
Свойство алгоритма записываться в виде упорядоченной совокупности отделенных друг от друга предписаний (директив):
понятность;
определенность;
дискретность;
массовость.
Свойство алгоритма записываться в виде только тех команд, которые находятся в Системе Команд Исполнителя, называется:
понятность;
определенность;
дискретность;
результативность.
Свойство алгоритма записываться только директивами однозначно и одинаково интерпретируемыми разными исполнителями:
дискретность;
понятность
определенность;
результативность
Свойство алгоритма, что при точном исполнении всех предписаний процесс должен прекратиться за конечное число шагов с определенным ответом на поставленную задачу:
понятность;
детерминированность;
дискретность;
результативность.
Свойство алгоритма обеспечения решения не одной задачи, а целого классазадач этого типа:
понятность;
определенность
дискретность;
массовость.
Что называют служебными словами в алгоритмическом языке:
слова, употребляемые для записи команд, входящих в СКИ;
слова, смысл и способ употребления которых задан раз и навсегда;
вспомогательные алгоритмы, которые используются в составе других алгоритмов;
константы с постоянным значением?
Рекурсия в алгоритме будет прямой, когда:
рекурсивный вызов данного алгоритма происходит из вспомогательного алгоритма, к которому в данном алгоритме имеется обращение;
порядок следования команд определяется в зависимости от результатов проверки некоторых условий;
команда обращения алгоритма к самому себе находится в самом алгоритме;
один вызов алгоритма прямо следует за другим.
Рекурсия в алгоритме будет косвенной, когда: алгоритма, к которому в данном алгоритме имеется обращение;
порядок следования команд определяется в зависимости от результатов проверки некоторых условий;
команда обращения алгоритма к самому себе находится в самом алгоритме;
один вызов алгоритма прямо следует за другим.
Команда машины Поста имеет структуру п Km, где:
п - действие, выполняемое головкой; К- номер следующей команды, подлежащей выполнению; т - порядковый номер команды;
п - порядковый номер команды; К - действие, выполняемое головкой; т - номер следующей команды, подлежащей выполнению;
п - порядковый номер команды; К- номер следующей команды, подлежащей выполнению; т - действие, выполняемое головкой;
п - порядковый номер команды; К - действие, выполняемое головкой; т - номер клетки, с которой данную команду надо произвести.
Сколько существует команд у машины Поста:
2;
4;
6;
8
В машине Поста останов будет результативным:
при выполнении недопустимой команды;
если машина не останавливается никогда;
если результат выполнения программы такой, какой и ожидался;
по команде «Стоп».
В машине Поста некорректным алгоритм будет в следующем случае:
при выполнении недопустимой команды;
результат выполнения программы такой, какой и ожидался;
машина не останавливается никогда;
по команде «Стоп»
В машине Тьюринга рабочий алфавит:
А = {а40 О, bА0 1, с40 2, ..., w40};
Л = {а40 0, а40 1, а40 2, ..., а40 };
Л = {а40 0, а41 0, о42 0, ..., а41 0};
Л = {а,0 0, а20 0, о3о 0, аb 0}.
В машине Тьюринга состояниями являются:
{a40 0, a40 1,a402, …,a40 t};
{q41, q42, q43, …, q4s};
{q41, q42, q43, …, q4s, a40 0, a40 1, a40 2,…,a40 t};
{q40, q41, q42, …, q4s}.
В машине Тьюринга предписание L для лентопротяжного механизма означает:
переместить ленту вправо;
переместить ленту влево;
остановить машину;
занести в ячейку символ.
В машине Тьюринга предписание R для лентопротяжного механизма означает:
переместить ленту вправо;
переместить ленту влево;
остановить машину;
занести в ячейку символ.
В машине Тьюринга предписание S для лентопротяжного механизма означает:
переместить ленту вправо;
переместить ленту влево;
остановить машину;
занести в ячейку символ.
В алгоритме Маркова ассоциативным исчислением называется:
совокупность всех слов в данном алфавите;
совокупность всех допустимых систем подстановок;
совокупность всех слов в данном алфавите вместе с допустимой системой подстановок;
когда все слова в алфавите являются смежными.
В ассоциативном счислении два слова называются смежными:
если одно из них может быть преобразовано в другое применением подстановок;
если одно из них может быть преобразовано в другое однократным применением допустимой подстановки;
когда существует цепочка от одного слова к другому и обратно;
когда они дедуктивны.
В алгоритме Маркова дана цепочка Р Р, Р2 ... Р„. Если слова P1f Р2Рк_! смежные, то цепочка называется:
ассоциативной;
эквивалентной;
индуктивной;
дедуктивной.
В алгоритме Маркова дана цепочка Р Р, Р2 ... Рк. Если слова Р,, Р2, ..., Рк_, смежные и цепочка существует и в обратную сторону, то слова Р\лРк называют:
ассоциативными;
эквивалентными;
индуктивными;
дедуктивными.
В алгоритмах Маркова дана система подстановок в алфавите Л = {а, b, с}:abc - сba - cbca - abПреобразуйте с помощью этой системы слово bacaabc:
cbc;
ccbcbbc;
cbacba;
cbabc.
В алгоритмах Маркова дана система подстановок в алфавите А = {а, Ь, с}:cb - abcbас - ас cab - b
Преобразуйте с помощью этой системы слово bcabacab:
ccb;
cab;
cbc;
bcaab.
Способ композиции нормальных алгоритмов будет суперпозицией, если:
выходное слово первого алгоритма является входным для второго;
существует алгоритм С, преобразующий любое слово р, содержащееся iпересечении областей определения алгоритмов А и В;
алгоритм D будет суперпозицией трех алгоритмов ABC, причем областьопределения D является пересечением областей определения алгоритмовА В и С, а для любого слова р из этого пересечения D(p) = А(р), еслиС(р) = е, D(p) = В(р), если С(р) = е, где е - пустая строка;
существует алгоритм С, являющийся суперпозицией алгоритмов А и Дтакой, что для любого входного слова р С{р) получается в результатепоследовательного многократного применения алгоритма А до тех пор,пока не получится слово, преобразуемое алгоритмом В.
II вариант
Способ композиции нормальных алгоритмов будет объединением, если:
выходное слово первого алгоритма является входным для второго;
существует алгоритм С, преобразующий любое слово р, содержащееся впересечении областей определения алгоритмов А и В;
алгоритм В будет суперпозицией трех алгоритмов ABC, причем областьопределения D является пересечением областей определения алгоритмовА В и С, а для любого слова р из этого пересечения D(p) - A(p), еслиС(р) = е, D(p) = В(р), если С(р) = е, где е - пустая строка;
существует алгоритм С, являющийся суперпозицией алгоритмов А и Дтакой, что для любого входного слова р С(р) получается в результатепоследовательного многократного применения алгоритма А до тех пор,пока не получится слово, преобразуемое алгоритмом В.
Способ композиции нормальных алгоритмов будет разветвлением, если:
выходное слово первого алгоритма является входным для второго;
существует алгоритм С, преобразующий любое слово р, содержащееся впересечении областей определения алгоритмов А и В;
алгоритм D будет суперпозицией трех алгоритмов ABC, причем областьопределения D является пересечением областей определения алгоритмовА В и С, а для любого слова р из этого пересечения D(p) = А(р), еслиС(р) = е, D{p) - В{р), если С(р) = е, где е - пустая строка;
существует алгоритм С, являющийся суперпозицией алгоритмов А и В,такой, что для любого входного слова р С{р) получается в результатепоследовательного многократного применения алгоритма А до тех пор,пока не получится слово, преобразуемое алгоритмом В.
Способ композиции нормальных алгоритмов будет итерацией, если:
выходное слово первого алгоритма является входным для второго;
существует алгоритм С, преобразующий любое слово р, содержащееся впересечении областей определения алгоритмов А и В;
алгоритм D будет суперпозицией трех алгоритмов ABC, причем областьопределения D является пересечением областей определения алгоритмовА В к С, а для любого слова р из этого пересечения D{p)= A(p), еслиС(р) = е, D(p) - В(р), если С(р) = е, где е - пустая строка;4) существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.
Команда машины Поста имеет структуру n Km, где:
n - действие, выполняемое головкой; K - номер следующей команды, подлежащей выполнению; m - порядковый номер команды
n - порядковый номер команды; K - действие, выполняемое головкой; m - номер следующей команды, подлежащей выполнению
n - порядковый номер команды; K - номер следующей команды, подлежащей выполнению; m - действие, выполняемое головкой
n - порядковый номер команды; K - действие, выполняемое головкой; m - номер клетки, с которой данную команду надо произвести.
Сколько существует команд у машины Поста?
2
4
6
8
В машине Поста останов будет результативным:
При выполнении недопустимой команды
Если машина не останавливается никогда
Если результат выполнения программы такой, какой и ожидался
По команде «Стоп»
В машине Поста некорректным алгоритм будет в следующем случае:
При выполнении недопустимой команды
Результат выполнения программы такой, какой и ожидался
Машина не останавливается никогда
По команде «Стоп»
В машине Тьюринга предписание L для лентопротяжного механизма означает:
Переместить ленту вправо
Переместить ленту влево
Остановить машину
Занести в ячейку символ
В машине Тьюринга предписание R для лентопротяжного механизма означает:
Переместить ленту вправо
Переместить ленту влево
Остановить машину
Занести в ячейку символ
В машине Тьюринга предписание S для лентопротяжного механизма означает:
Переместить ленту вправо
Переместить ленту влево
Остановить машину
Занести в ячейку символ
В алгоритме Маркова ассоциативным исчислением называется:
Совокупность всех слов в данном алфавите
Совокупность всех допустимых подстановок
Совокупность всех слов в данном алфавите вместе с допустимой системой подстановок
Когда все слова в алфавите являются смежными
В ассоциативном исчислении два слова называются смежными:
Если одно из них может быть преобразовано в другое применением подстановок
Когда существует цепочка от одного слова к другому и обратно
Когда они дедуктивныЕсли одно из них может быть преобразовано в другое однократным применением допустимой подстановки
В алгоритме Маркова дана цепочка Р Р1, Р2,..., Рn. Если слова Р1, Р2,..., Рn смежные, то цепочка называется:
Ассоциативной
Эквивалентной
Индуктивной
Дедуктивной
В алгоритме Меркова дана цепочка Р Р1, Р2,...Рк. Если слова Р1, Р2,...,Рк смежные и цепочка существует и в обратную сторону, то слова Р1 и Рк называют:
Ассоциативными
Эквивалентными
Индуктивными
Дедуктивными
В алгоритмах Маркова дана система подстановок в алфавите Л={a,b,c}: abc - c; ba - cb; ca - ab. Преобразуйте с помощью этой системы слово bacaabcCbcccbcbbccbacbacbabcВ алгоритмах Маркова дана система подстановок в алфавите A={a, b, c}: cb - abc; bac - ac; cab - b. Преобразуйте с помощью этой системы слово bcabacab:
ccbcabcbcbcaabСпособ композиции нормальных алгоритмов будет суперпозицией, если:
Существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В
Выходное слово первого алгоритма является входным для второго
Алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов A B и C, а для любого слова р из этого пересечения D(p)= A(p), C(p)=e, D(p)=B(p), если C(p)=е, где е - пустая строка
Существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В
Способ композиции нормальных алгоритмов будет объединением, если:
Входное слово первого алгоритма является входным для второго
Существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В
Алгоритм В будет суперпозицией трех алгоритмов АВС, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(р)=А(р), C(p)=e, D(p)=B(p), если С(р)=е, где е - пустая строка
Существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В
Способ композиции нормальных алгоритмов будет разветвлением, если:
Выходное слово первого алгоритма является входным для второго
Существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В
Алгоритм Д будет суперпозицией трех алгоритмов АВС, причем область определения Д является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения Д(р)=А(р), если С(р)=е, Д(р)=В(р), если С(р)=е, где е - пустая строка
Существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В
Способ композиции нормальных алгоритмов будет итерацией, если:
Выходное слово первого алгоритма является входным для второго
Существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В
Алгоритм Д будет суперпозицией трех алгоритмов АВС, причем область определения Д является пересечением областей определения алгоритмов А В С, а для любого слова р из этого пересечения Д(р)=А(р), если С(р)=е, Д(р)=В(р), если С(р)=е, где е - пустая строка
Существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В
В машине Тьюринга предписание L для лентопротяжного механизма означает:
переместить ленту вправо;
переместить ленту влево;
остановить машину;
занести в ячейку символ.
В машине Тьюринга предписание R для лентопротяжного механизма означает:
переместить ленту вправо;
переместить ленту влево;
остановить машину;
занести в ячейку символ.
В машине Тьюринга предписание S для лентопротяжного механизма означает:
переместить ленту вправо;
переместить ленту влево;
остановить машину;
занести в ячейку символ.
В алгоритме Маркова ассоциативным исчислением называется:
совокупность всех слов в данном алфавите;
совокупность всех допустимых систем подстановок;
совокупность всех слов в данном алфавите вместе с допустимой системойподстановок;
когда все слова в алфавите являются смежными.
В ассоциативном счислении два слова называются смежными:
если одно из них может быть преобразовано в другое применением подстановок;
если одно из них может быть преобразовано в другое однократным применением допустимой подстановки;
когда существует цепочка от одного слова к другому и обратно;
когда они дедуктивны.
2.2 Ситуационные задания (или компентностно-ориентированные задания/задачи)
Нет заданий
2.3 Руководство для экзаменатора
Таблица эталонов правильных ответов комплекта тестовых заданий
№ п/п I вариант II вариант
1 a b
2 b c
3 c b
4 d a
6 a b
7 b b
8 c c
9 b b
10 a b
11 b c
12 c b
13 d a
14 a b
15 b b
16 c c
17 b b
18 a a
19 b b
20 b c
21 c b
22 b a
23 a b
24 b a
25 b a
Критерии оценивания заданий:
За каждое правильно выполненное тестовое задание (верный ответ) ставится 1 балл, за неверный ответ - 0 баллов.
«5» - 24-25
«4» - 22-23
«3» - 20-21
«неудовл» - 19 и меньше.
Время выполнение заданий: 40 мин.
Количество вариантов: 2.
Критерии оценивания выполнения практического задания
например
рациональное распределение времени по этапам выполнения задания
обращение в ходе задания к информационным источникам
знание терминологии
скорость выполнение
способность нестандартно мыслить
количество предложенных вариантов решения поставленной задачи.