Комплект контрольно-оценочных средств для оценки результатов освоения дисциплины ОП.08 Теория алгоритмов Для специальности 09.02.03 Программирование в компьютерных системах

Частное учреждение

профессиональная образовательная организация

ТЕХНИКУМ «БИЗНЕС И ПРАВО»

_____________________________________________________________________________

Комплект контрольно-оценочных средств

для оценки результатов освоения дисциплины

ОП.08 Теория алгоритмов

Для специальности

09.02.03 Программирование в компьютерных системах

Базовая подготовка

Автор:

Косяченко Н.П. – преподаватель ЧУПОО ТЕХНИКУМ «БИЗНЕС И ПРАВО»

Белореченск 2022г.

Комплект контрольно-оценочных средств разработан на основе рабочей программы учебной дисциплины ОП.08 Теория алгоритмов, разработанной на основе Федерального государственного образовательного стандарта по специальности среднего профессионального образования 09.02.03 Программирование в компьютерных системах, утвержденного приказом Министерства образования и науки РФ от 28.07.2014г. № 804

Разработчик:

Косяченко Н.П. – преподаватель ЧУПОО ТЕХНИКУМ «БИЗНЕС И ПРАВО»

СОДЕРЖАНИЕ

1.Паспорт комплекта оценочных средств

1.1 Область применения комплекта оценочных средств

1.2Результаты освоения учебной дисциплины, подлежащие проверке

2. Оценка освоения учебной дисциплины

2.1 Формы и методы оценивания

3. Контрольно- оценочные средства

3.1 Задания для проведения входного контроля

3.2 Задания для проведения текущего контроля

3.3 Задания для проведения промежуточной аттестации по дисциплине

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

Область применения комплекта оценочных средств

Контрольно-оценочные средства (КОС) предназначены для контроля и оценки образовательных достижений обучающихся, освоивших программу учебной дисциплины ОП.08 Теория алгоритмов.

КОС включают контрольные материалы для проведения входного, текущего контроля и промежуточной аттестации в форме дифференцированного зачета в первом семестре и экзамена – во втором.

Контрольно-оценочные средства разработаны в соответствии с документами:

ФГОС СПО 09.02.03 Программирование в компьютерных системах;

учебным планом и программой подготовки специалистов среднего звена специальности СПО 09.02.03 Программирование в компьютерных системах;

рабочей программой учебной дисциплины ОП.08 Теория алгоритмов;

учетом требований работодателей (представителей отрасли).

1.2 Результаты освоения учебной дисциплины, подлежащие проверке

В результате аттестации по учебной дисциплине осуществляется комплексная проверка следующих умений и знаний:

Таблица 1

ОЦЕНКА ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ

Формы и методы оценивания

Предметом оценки служат умения и знания, предусмотренные ФГОС по дисциплине ОП.08 Теория алгоритмов, направленные на формирование общих и профессиональных компетенций.

Критерии оценивания устных и письменных ответов

Отметкой "ОТЛИЧНО" оценивается ответ, который показывает прочные знания основных процессов изучаемого вопроса, отличается глубиной и полнотой раскрытия темы, давать аргументированные ответы, приводить примеры; свободное владение монологической речью, логичность и последовательность ответа.

Отметкой "ХОРОШО" оценивается ответ, который показывает прочные знания основных процессов изучаемого вопроса, отличается глубиной и полнотой раскрытия темы, давать аргументированные ответы, приводить примеры; свободное владение монологической речью, логичность и последовательность ответа. Однако, допускается одна - две неточности в ответе.

Отметкой "УДОВЛЕТВОРИТЕЛЬНО" оценивается ответ, свидетельствующий в основном о знании процессов изучаемого вопроса, отличающийся недостаточной глубиной и полнотой раскрытия темы; слабо сформированными навыками анализа явлений, процессов, недостаточным умением давать аргументированные ответы и приводить примеры; недостаточно свободным владением монологической речью, логичностью и последовательностью ответа. Допускается несколько ошибок в содержании ответа.

Отметкой "НЕУДОВЛЕТВОРИТЕЛЬНО" оценивается ответ, обнаруживающий незнание процессов изучаемого вопроса, отличающийся неглубоким раскрытием темы; незнанием основных вопросов теории, несформированными навыками анализа явлений, процессов; неумением давать аргументированные ответы, слабым владением монологической речью, отсутствием логичности и последовательности. Допускаются серьезные ошибки в содержании ответа.

Критерии оценивания тестирования

КОНТРОЛЬНО-ОЦЕНОЧНЫЕ МАТЕРИАЛЫ

Задания для проведения текущего контроля

Текущий контроль освоения обучающимися дисциплины ОП.08 Теория алгоритмов осуществляется преподавателем в процессе проведения практических занятий, тестирования, устного и письменного опроса различных форм, а также выполнения обучающимися индивидуальных заданий, проектов, исследований и др.

Задания для текущего контроля представлены в соответствии с логической последовательностью, выстроенной в рабочей программе дисциплины и календарно-тематическом плане.

3.1 Задания для проведения входного контроля

ВХОДНОЙ КОНТРОЛЬ: ТЕСТИРОВАНИЕ

Оцениваемые знания: остаточные знания по дисциплине

Инструкция

Внимательно прочитайте задание. Выберите правильные ответы из предложенных вариантов. Количество правильных ответов может быть 1, 2 или 3.

Максимальное время выполнения задания – 20 мин.

Вариант 1

Задание 1

Алгоритмом можно считать:

описание процесса решения квадратного уравнения

технический паспорт автомобиля

список класса в журнале

расписание уроков

Задание 2

Как называется свойство алгоритма, означающее, что данный алгоритм применим к решению целого класса задач?

Понятность

Определённость

Результативность

Массовость

Задание 3

Как называется свойство алгоритма, означающее, что он всегда приводит к результату через конечное, возможно, очень большое, число шагов?

Понятность

Дискретность

Результативность

Массовость

Задание 4

Система команд исполнителя ВЫЧИСЛИТЕЛЬ состоит из двух команд, которым присвоены номера:

1 - вычти 2

2 - умножь на 3.

Первая из них уменьшает число на 2, вторая увеличивает число в 3 раза. При записи алгоритма для краткости указываются лишь номера. Запишите алгоритм, содержащий не более пяти команд, с помощью которого из числа 11 будет получено число 13.

Задание 5

Наибольшей наглядностью обладают следующие формы записи алгоритмов:

Словесные

Рекурсивные

Графические

Построчные

Задание 6

Величиной целого типа является:

количество мест в зрительном зале

рост человека

марка автомобиля

площадь квартиры

Задание 7

Какое логическое выражение истинно, если х ϵ [-10, 10]?

(x > 10) и (x < -10)

(x > 10) или (x < -10)

(x <10) или (x >= -10)

(x >= -10) и (x <= 10)

Задание 8

Какая команда должна следовать за командами А:= А+В и В:= А-В, чтобы последовательное выполнение всех трёх команд привело к обмену значениями переменных А и В?

А:= А + В

А:= А - В

В:= А + В

В:= В - А

Задание 9

К какому виду алгоритмов можно отнести алгоритм, схема которого представлена ниже?

Линейный

Разветвляющийся

Циклический

Задание 10

К какому виду алгоритмов можно отнести алгоритм, схема которого представлена ниже?

цикл с параметром

цикл с предусловием

цикл с постусловием

цикл с заданным числом повторений

Задание 11

К какому виду алгоритмов можно отнести алгоритм, схема которого представлена ниже?

цикл с постусловием

цикл с заданным условием продолжения работы

цикл с предусловием

цикл с заданным числом повторений

Задание 12

Исполните следующий фрагмент алгоритма для a = x и b = y.

a:= a+b

b:= b - a

a:= a+b

b:= - b

Какие значения присвоены переменным a и b?

у, х

х+у, х-у

х, у

-у, х

Задание 13

Исполните алгоритм при a=2 и b=0.

Чему будут равны значения a и b по окончании работы алгоритма?

Задание14

Определите значение переменной s после выполнения фрагмента алгоритма.

s:=0

нц для i от 1 до 5

s:= s+i*i

кц

Вариант 2

Задание 1

Как называется свойство алгоритма, означающее, что он задан с помощью таких предписаний, которые исполнитель может воспринимать и по которым может выполнять требуемые действия?

Понятность

Определённость

Дискретность

Массовость

Задание 2

Как называется свойство алгоритма, означающее, что путь решения задачи разделён на отдельные части?

Дискретность

Определённость

Результативность

Массовость

Задание 3

Как называется свойство алгоритма, означающее, что путь решения задачи определен вполне однозначно, на любом шаге не допускаются никакие двусмысленности и недомолвки?

Дискретность

Определённость

Результативность

Массовость

Задание 4

Система команд исполнителя ВЫЧИСЛИТЕЛЬ состоит из двух команд, которым присвоены номера:

1 - вычти 2

2 - умножь на 3.

Первая из них уменьшает число на 2, вторая увеличивает число в 3 раза. При записи алгоритма для краткости указываются лишь номера. Запишите алгоритм, содержащий не более пяти команд, с помощью которого из числа 11 будет получено число 13.

Задание 5

Величина, значения которых меняются в процессе исполнения алгоритма, называются:

Постоянными

Константами

Переменными

Табличными

Задание 6

Укажите правильный вариант записи условия "х - двузначное число":

x div 10 <= 9

(x>=10) И (x<100)

x div 100 = 0

x mod 100 = 99

Задание 7

К какому виду алгоритмов можно отнести алгоритм, схема которого представлена ниже?

Линейный

Разветвляющийся с неполным ветвлением

Циклический

Разветвляющийся с полным ветвлением

Задание 8

К какому виду алгоритмов можно отнести алгоритм, схема которого представлена ниже?

цикл с постусловием

цикл с заданным условием продолжения работы

цикл с предусловием

цикл с заданным числом повторений

Задание 9

Дан фрагмент линейного алгоритма.

a:= 8

b:= 6+3*a

a:= b/3*a

Чему равно значение переменной а после его исполнения?

Задание 10

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

х:= 11

у:= 5

t:= y

y:= x mod y

x:= t

y:= y+2*t

x=11, y=5

x=5, y=11

x=10, y=5

x=5, y=10

Задание 11

Исполните алгоритм при х=10 и у=15.

-5, 10

5, 20

10, 15

5, 5

-5, 5

Задание 12

Исполните алгоритм при a=2 и b=0.

Чему будут равны значения a и b по окончании работы алгоритма?

Задание13

Операции div и mod выполняются ...

только над целыми величинами

только над вещественными величинами

над целыми и вещественными величинами

Задание 14

Кто (что) может быть исполнителем алгоритма?

Человек

Любое животное

Дрессированное животное

Техническое устройство

Пакет преподавателя

Показатели оценки результатов освоения программы учебной дисциплины:

3.2 Задания для проведения текущего контроля

ВОПРОСЫ ДЛЯ УСТНОГО ОПРОСА

Тема 1.1 Введение в теорию алгоритмов.

Проверяемые знания: З1

1. Сформулируйте определение алгоритма.

2. Перечислите виды алгоритмов.

3. Перечислите способы представления алгоритмов.

4. Сформулируйте определение линейного алгоритма.

5. Сформулируйте определение разветвляющего алгоритма.

6. Сформулируйте определения команд ветвления.

7. Сформулируйте определение блок-схемы алгоритма.

8. Перечислите основные блоки в блок-схеме алгоритма.

9. Перечислите основные свойства алгоритмов.

10.Сформулируйте определения циклического алгоритма.

Тема 2.1 Программирование в алгоритмах.

Проверяемые знания: З1, З2

1. Опишите алгоритм выполнение операций над большими числами.

2. Опишите алгоритм решение комбинаторных задач.

3. Опишите алгоритм сортировки методом грубой силы.

4. Опишите алгоритм сортировки слияния и быстрой сортировки.

5. Опишите алгоритмы на графах нахождение кратчайшего пути.

Тема 3.1 Введение в анализ алгоритмов.

Проверяемые знания: З1, З2, З3

1. Сформулируйте определение асимптотической оценки алгоритма.

2. Перечислите классы сложности алгоритмов.

3. Сформулируйте определение трудоемкости алгоритма.

4. Перечислите способы определение сложности работы алгоритма.

5. Ответьте на вопрос: как рассчитывается среднее время выполнения элементарной операции?

КОМПЛЕКТ ВАРИАНТОВ ПИСЬМЕННОГО ОПРОСА

количество вариантов 5

Тема 1.2: Модели вычислений.

Проверяемые знания: З2

Инструкция:

1. Внимательно прочитайте задания и дайте письменные ответы на вопросы варианта .

2. Максимальное время выполнения задания – 20 мин.

Вариант 1

Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1. Автомат в состоянии q₁ обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Вариант 2

Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q₁ обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Вариант 3

Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было “100”, то выходным словом должно быть “99”, а не “099”. Автомат в состоянии q₁ обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Вариант 4

На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножить это число на 2. Автомат в состоянии q₁ обозревает крайнюю левую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Вариант 5

На ленте машины Тьюринга находится десятичное число. Определить, делится ли это число на 5 без остатка. Если делится, то записать справа от числа слово “да”, иначе — “нет”. Автомат обозревает некую цифру входного числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

КОМПЛЕКТ ДЛЯ ПРОВЕДЕНИЯ ТЕСТИРОВАНИЯ

Тема 1.1 Введение в теорию алгоритмов

Проверяемые знания: З1,З2

Инструкция:

Выполните тестовое задание (компьютерное тестирование в программе MyTest).

Время выполнения: 15 минут.

1. Последовательность действий, допустимых для исполнителя, - это ...?

А. программа

Б. алгоритм

В. команда

Г. система команд

2. Выявление ошибок и их устранение называется ...?

А. отладкой задачи

Б. отладкой исполнителя

В. отладкой алгоритма

Г. отладкой программы

3. Отдельное указание исполнителю - это ...?

А. программа

Б. алгоритм

В. команда

Г. приказ

4. Программы, которые содержат команду повторения, называются ...?

А. линейными

Б. разветвляющими

В. циклическими

Г. вспомогательными

5. Форма организации действий, при которой один и тот же блок выполняется несколько раз, называется ...?

А. следованием

Б. циклом

В. телом цикла

Г. командой повторения

6. Составная команда, в которой одни и те же действия (команды) повторяются несколько раз, называются ...?

А. командой присваивания

Б. командой повторения

В. вспомогательной программой

Г. командой ветвления

7. Совокупность всех команд, которые может выполнить конкретный исполнитель, - это ...?

А. система программ

Б. система алгоритмов

В. система команд

Г. система задач

8. Вспомогательная команда - это ...?

А. цикл

Б. ветвление

В. процедура

Г. следование

9. Графический способ описания алгоритма - это ...?

А. программа

Б. блок-схема

В. алгоритм

Г. словесно-пошаговая запись

10. Сложные условия - это такие условия, которые содержат ...?

А. логическую связку И

Б. логическую связку ИЛИ

В. логическую связку НЕ

Г. логические связки И, ИЛИ, НЕ

Пакет преподавателя

Показатели оценки результатов освоения программы учебной дисциплины:

Тема 1.2 Модели вычислений.

Проверяемые знания: З1,З2

Инструкция:

Выполните тестовое задание (компьютерное тестирование в программе MyTest).

Время выполнения: 10 минут.

1. Из чего состоит машина Поста?

А. из ленты

Б. из ленты и каретки

В. из каретки

Г. из знаков

2. Лента в машине Поста...?

А. конечна

Б. бесконечна

В. ограничена

Г. может быть двух видов

3. Как нумеруются секции на ленте машины Поста?
А. не нумеруются

Б. относительно каретки

В. жестко пронумерованы

Г. нумеруются по желанию

4. Что записывается в секции на ленте в машине Поста?

А. 1 или 0

Б. 0

В. 1

Г. Vили ничего

5. Как называется число, стоящее в конце команды машины Поста?

А. отсылкой

Б. пересылкой

В. индексом

Г. постфиксом

6. Сколько команд у машины Поста?

А. 4

Б. 3

В. 6

Г. 5

7. Сколько команд у машины Тьюринга?

А. 4

Б. 3

В. 6

Г. 5

8. Информация о том, какие секции пусты, а какие отмечены и где стоит каретка в машине Поста?

А. позволяет считать число с ленты

Б. образует состояние ленты

В. образует состояние машины Поста

Г. неизвестно

Пакет преподавателя

Показатели оценки результатов освоения программы учебной дисциплины:

Тема 3.1 Введение в анализ алгоритмов.

Проверяемые знания:З1,З2

Инструкция:

Выполните тестовое задание (компьютерное тестирование в программе MyTest).

Время выполнения: 15 минут.

Общая эффективность алгоритма будет зависеть от:

Количества выполненных элементарных операций

Б. Количества памяти для хранения промежуточных ресурсов

Времени, затраченного разработчиком на построение алгоритма

Г. К другим

Алгоритм умножения матриц будет относиться:

К количественно-зависимым

Б. К параметрически зависимым

К количественно-параметрически зависимым

Г. К другим

Алгоритм поиска максимума в массиве будет относиться:

К количественно-зависимым

Б. К параметрически зависимым

К количественно-параметрически зависимым

Г. К другим

Данная функция трудоемкости отражает: 

лучший случай

Б. худший случай

В.средний случай

Г. обычный случай.

На рисунке изображена асимптотическая оценка

Оценка   (тетта)

Б.Оценка   (Омега)

Оценка О (О большое)

Г. 1

К элементарным операциям при оценке алгоритма относятся:

Простое присваивание

Б Арифметические операции: (*, /, -, +);

Конструкция «Цикл»

Г.ЛогическоеИЛИ

Дляалгоритма
SumM(A,N;Sum);
Sum:=0;
for i:=1 to N
for j:=1 to N
Sum:=Sum+A[i,j];
end for j
end for i
Return (Sum);
End;
асимптотическаясложностьбудетвыражаться

А.О(n²)

Б. О(n)

В. О(n²+2)

Г. О(n²)+2

Дляалгоритматрудоемкостьпри n=2 , будетравна
SumM(A,N;Sum);
Sum:=0;
for i:=1 to N
for j:=1 to N
Sum:=Sum+A[i,j];
end for j
end for i
Return (Sum);
End;

38

Б. 13

4

Г. Другое

Конструкция простого цикла потребует выполнения

1 + 3*N элементарных операций

Б.3 элементарных операции

1 элементарная операция

Г. 3N элементарных операций

Общая эффективность алгоритма не будет зависеть от:

А.Количества выполненных элементарных операций

Б. Количества памяти для хранения промежуточных ресурсов

В. Времени, затраченного разработчиком на построение алгоритма

Г. от всех параметров.

Пакет преподавателя

Показатели оценки результатов освоения программы учебной дисциплины:

КОНТРОЛЬ ПРОВЕРЯЕМЫХ УМЕНИЙ

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

Задания для проведения промежуточной аттестации

по дисциплине

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

УСЛОВИЯ

Зачет проводится одновременно для всей учебной группы путем письменного ответа на вопросы.

Инструкция для обучающихся

Внимательно прочитайте задание.

Время выполнения задания – 40 минут

I. ЗАДАНИЕ ДЛЯ ЭКЗАМЕНУЮЩЕГОСЯ

Вопросы для дифференцированного зачета

Возникновение и история развития теории алгоритмов.

Основные разделы, задачи и направления развития современной теории алгоритмов.

Понятие алгоритма и его свойства.

Понятия рекурсии и вычислимой функции.

Простейшие рекурсивные функции.

Частично рекурсивные функции и тезис Чёрча.

Понятие алгоритма как абстрактной машины.

Алгоритмическая машина Поста (определение, команды, принцип работы).

Алгоритмическая машина Тьюринга (определение, команды, схема функционирования).

Алгоритмическая машина Тьюринга (общее правило работы, конфигурация машины, определение класса решаемых задач).

Проблема алгоритмической разрешимости.

Алгоритмически неразрешимые задачи (примеры).

Понятие сложности алгоритма.

Задачи с полиномиальной сложностью.

Задачи с экспоненциальной сложностью.

Полиномиально проверяемые задачи.

Примеры NP-задач (раскраска графа, упаковка рюкзака, планирование работ и др.).

Проблема P=NP.NP-полные задачи.

Оценка трудоёмкости алгоритма. Функция трудоёмкости.

Классификация алгоритмов на основе функции трудоёмкости (классы N,PR и NPR).

Определение элементарных операций при оценке функции трудоёмкости.

Методика анализа трудоёмкости основных алгоритмических конструкций.

Трудоёмкость рекурсивной реализации алгоритмов.

Временные оценки сложности алгоритмов.

Метод прямого определения среднего времени.

Оценка ресурсной эффективности алгоритмов.

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

Сортировка массива методом пузырька

Сортировка массива вставками

Динамическое программирования. Подход Беллмана.

Алгоритм решения задачи о замене оборудования

Способы представления графа.

Поиск минимального пути в графе

Сетевое планирование и управление. Критические пути. Анализ сетевого графика.

Метод ветвей и границ решения задачи коммивояжёра

II. ПАКЕТ ЭКЗАМЕНАТОРА

II а. УСЛОВИЯ

Зачет проводится одновременно для всей учебной группы путем письменного ответа на вопросы.

Количество вопросов для экзаменующегося–2

Время выполнения задания – 40 мин.

IIб. КРИТЕРИИ ОЦЕНКИ

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