Файл: Образовательная программа среднего профессионального образования Комплект контрольнооценочных средств по учебным.docx

В городе Н от каждой площади отходит ровно 5 улиц, соединяющих площади. Докажите, что число площадей чётно, а число улиц кратно 5.

Решение:

По теореме, что число нечётных вершин любого графа чётно, следует, что число площадей (вершин графа) 2n, а число улиц (рёбер графа) будет (2n·5):2, а значит, число площадей чётно, а число улиц кратно 5.
Задача № 24

Футбольный мяч сшит из 32 лоскутов: белых шестиугольников и чёрных пятиугольников. Каждый чёрный лоскут граничит только с белыми, а каждый белый – с тремя чёрными и тремя белыми. Сколько лоскутов белого цвета?

Решение:

Пусть на мяче число белых лоскутов х шт., а чёрных будет (32 – х) шт. Тогда границ белых лоскутов с чёрными 5(32-х)=3х, значит, х=20 и белых лоскутов 20 шт.
Задача № 25

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

Решение:

Пусть существует некоторый город А. Из него можно добраться не более, чем до трёх городов, а из каждого из них ещё не более чем до двух (не считая А). Тогда всего городов не более 1+3+6=10. Значит всего городов не более 10. Пример на рисунке (его ещё называют графом Петерсона) показывает существование авиалиний.



Задача № 26

Можно ли нарисовать графы изображенные на рисунках, не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?



Решение:

1. 
   Можно, т. к. только 2 нечетные вершины.
   
2. 
   Нельзя, т. к. 4 нечетные вершины.
   

Задача № 27

Доказать: (A®B, A® )Þ .

Доказательство:

A	B	A®B		A®
И	И	И	Л	Л	Л
И	Л	Л	И	И	Л
Л	И	И	Л	И	И
Л	Л	И	И	И	И

---

Из определения следует, что противоречие логически влечет любую формулу, а тавтология логически следует из любой формулы логики.

Определение. Формулы F и G называются равносильными, если они являются логическими следствиями друг друга. Обозначение: .

Проанализировав последнее определение, получаем, что формулы равносильны, если они на всех наборах значений переменных превращаются в одинаковые по истинностному значению высказывания.
Задача № 28

Доказать закон отрицания конъюнкции ( )

Доказательство:

Найдем значения для и и сравним их.

A	B
И	И	И	Л	Л	Л	Л
И	Л	Л	И	Л	И	И
Л	И	Л	И	И	Л	И
Л	Л	Л	И	И	И	И

Задача № 29

Найти значение и убедиться, что при всех значениях A и B - это истинное значение.
Решение:

A	B
И	И	И	Л	Л	Л	Л	И
И	Л	Л	И	Л	И	И	И
Л	И	Л	И	И	Л	И	И
Л	Л	Л	И	И	И	И	И

---

Задача № 30

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

Решение. Применяя закон склеивания (в обратном порядке, то есть ) и дистрибутивность (то есть вынесем за скобки и ), получим

.

Задача № 31

Записать предложение: прямая а параллельна прямой b с помощью предиката.

Решение:

Предметная область – множество прямых.

Введем предикат Р (х), х – прямая. Предикат параллельности х||у

Тогда предложение можно записать в виде: Р (а) Р(b) (а||b) .
Задача № 32

Записать с помощью предиката:

Аксиома: через две различные точки проходит единственная прямая. (Ели две точки принадлежат двум прямым, то эти прямые совпадают).

Решение:

Введем предикаты

Т (х), х – точка; Р (х), х – прямая; J(x,y) - x у. Тогда можно записать:

Т (А) Т (В) _{(А ≠ В)} Р (а) Р(b) J(A,a) J(B,а) J(A,b) J(B,b)

---

(a=b).

Задача № 33

Установить последнюю цифру степени y=2 ²⁰⁰⁷

Решение.

Имеем 2007=501·4+3, значит f (2007)=f (3)=2³=8. Ответ: 8

5. Описание процедуры экзамена

Комплексный экзамен по дисциплинам «Основы алгоритмизации и программирования»

и «Дискретная математика» проводится в соответствии с расписанием по экзаменационным билетам, согласованным с ПЦК и утвержденным заместителем директора по КОД.

Количество экзаменационных билетов превышает количество обучающихся.

В билете – 2 теоретических вопроса и 1 практическое задание На подготовку к ответу обучающемуся отводится до 30 минут.

Обучающийся предъявляет ответы в устной (письменной, смешанной) форме: устно раскрывает теоретические вопросы; решение задачи представляется в письменном виде с устными комментариями (пояснениями).

Требования охраны труда: инструктаж по технике безопасности, правилам поведения на занятии, по соблюдению дисциплины, наличие инструктора (преподаватель).
6. Критерии оценки:

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

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

Оценка "удовлетворительно" ставиться обучающему, показавшему знания основного учебно-программного материала в объеме, необходимом для дальнейшей учебы и предстоящей работы по специальности, справляющемуся с выполнением заданий, предусмотренных программой, знакомому с основной литературой, рекомендованной программой. Оценка "удовлетворительно" выставляется обучающемся, допустившим погрешности в ответе на экзамене и при выполнении экзаменационных заданий, но обладающим необходимыми знаниями для их устранения под руководством преподавателя.

---

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

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

При проведении промежуточной аттестации обучающимся могут пользоваться конспектом лекций, ПК, справочными материалами.
8. Эталоны ответов на теоретические вопросы:
Эталоны ответов на теоретические задания: по дисциплине «Основы алгоритмизации и программирования»

1. 
   Основные понятия алгоритмизации. Понятия «алгоритм», «исполнитель алгоритма».
   

Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.

Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.

2. 
   Свойства и формы записи алгоритмов.
   

---