Бюджетное учреждение профессионального образования Ханты-Мансийского автономного округа - Югры "Нижневартовский социально-гуманитарный колледж"

УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС

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

«ТЕОРИЯ АЛГОРИТМОВ»

Составитель:

Преподаватель Ульянова О.В.

Содержание

Аннотация        4

Рабочая программа        5

Паспорт рабочей программы учебной дисциплины        8

Область применения примерной программы        8

Место учебной дисциплины в структуре основной профессиональной образовательной программы: дисциплина входит в профессиональный  цикл.        8

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

Распределение часов и форм промежуточной аттестации по семестрам        9

Структура и примерное содержание  учебной дисциплины        10

Объем учебной дисциплины и виды учебной работы        10

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

Условия реализации учебной дисциплины        13

Требования к минимальному материально-техническому обеспечению        13

Информационное обеспечение обучения        13

Используемые образовательные технологии        14

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

Аннотация к рабочей программы        21

Учебно-методический блок        23

Учебно-методические материалы для проведения занятий        23

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

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

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

Организация контроля и оценивания        33

Материально-техническое обеспечение контрольно-оценочных мероприятий        33

Комплект материалов для контроля и оценки освоения умений и усвоения знаний по учебной дисциплине        37

Требования к выполнению самостоятельной работы (реферат):        46

Глоссарий        49

Аннотация

Учебно-методический комплекс написан в соответствии с требованиями федерального государственного образовательного стандарта среднего профессионального образования и примерной программой, рекомендованной Экспертным советом по профессиональному образованию Федерального государственного автономного учреждения Федерального института развития образования. УМК предназначен для организации аудиторной и самостоятельной работы студентов специальности «09.02.03 Программирование в компьютерных системах», квалификации техник-программист. В пособии представлены рабочая программа по дисциплине, учебно-методический блок, в котором изложены план изучения дисциплины, практические работы, темы для самостоятельных работ, комплект контрольно-оценочных средств для оценки результатов.

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

УМК написан в доступной форме, снабжен словарем терминов и определений.

Бюджетное учреждение профессионального образования

Ханты-Мансийского автономного округа - Югры

«Нижневартовский  социально-гуманитарный колледж»

Рабочая программа

Номер группы: 319П

г. Нижневартовск

Рабочая программа учебной дисциплины разработана в соответствии с требованиями  Федерального государственного образовательного стандарта среднего профессионального образования по специальности 

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

и на основе Примерной программы учебной дисциплины Теория алгоритмов, рекомендованной Экспертным советом по профессиональному образованию Федерального государственного автономного учреждения Федерального института развития образования (ФГАУ ФИРО), заключение Экспертного совета  № 093 от 02 марта 2012 г.

Паспорт рабочей программы учебной дисциплины

Теория алгоритмов

Область применения примерной программы

Рабочая программа учебной дисциплины является частью адаптированной основной профессиональной образовательной программы в соответствии с ФГОС по специальности (специальностям) СПО

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

Рабочая программа учебной дисциплины может быть использована в профессиональной подготовке работников в области разработки программного обеспечения при наличии среднего (полного) общего образования. Опыт работы не требуется.

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

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

В результате освоения учебной дисциплины обучающий должен

уметь:

• разрабатывать алгоритмы для конкретных задач;
• определять сложность работы алгоритмов;

знать:

• основные модели алгоритмов;
• методы построения алгоритмов;
• методы вычисления сложности работы алгоритмов.

Обучающийся должен обладать общими компетенциями, включающими в себя способность:

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

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

ОК 3. Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.

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

ОК 5. Использовать информационно-коммуникационные технологии в профессиональной деятельности.

ОК 6. Работать в коллективе и в команде, эффективно общаться с коллегами, руководством, потребителями.

ОК 7. Брать на себя ответственность за работу членов команды (подчиненных), за результат выполнения заданий.

ОК 8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.

ОК 9. Ориентироваться в условиях частой смены технологий в профессиональной деятельности.

Обучающийся должен обладать профессиональными компетенциями, включающими в себя способность:

ПК 1.1. Выполнять разработку спецификаций отдельных компонент.

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

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

Структура и примерное содержание  учебной дисциплины

Объем учебной дисциплины и виды учебной работы

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

Условия реализации учебной дисциплины

Требования к минимальному материально-техническому обеспечению 

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

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

Технические средства обучения:

программное обеспечение общего и профессионального назначения: С++.

Для обучающихся с нарушениями слуха используются мультимедий-ные средства и технические средства приема-передачи учебной информации в доступных формах такие как система организации равномерного звукового поля «Front Row Juno», индукционная система «Исток А2». Для обучающихся с нарушениями зрения используется карманная лупа с подсветкой «Eschenbach Mobilux», портативный видеоувеличитель «Bigger B2-50TV-HDMI», читающая машина Optelec ClearReader+, стационарный комплекс видеоувеличения и преобразования изображений объектов Optelec ClearView C, программное обеспечение экранного доступа с синтезом речи SuperNova Access Suite, дисплей для вывода информации рельефно-точечным шрифтом ALVA 640 Comfort, устройство для нанесения тактильного рельефного шрифта ROMEO ATTACHE, устройство создания рельефной графики для тактильного восприятия ZYFUSE. Для обучающихся с нарушениями опорно-двигательного аппарата используется сенсорное устройство ввода для облегчения взаимодействия с компьютерной техникой «Клавинта», специализированный манипулятор управления с выносными кнопками.

Информационное обеспечение обучения 

Перечень рекомендуемых учебных изданий, Интернет-ресурсов, дополнительной литературы

Дополнительные источники:

1. Судоплатов С.В., Овчинникова Е.В. / Математика. Математическая логика и теория алгоритмов. Учебник и практикум для СПО. – М.:Юрайт, 2019. – 255 с.
2. Математическая логика и теория алгоритмов: Учебник / Пруцков А.В., Волкова Л.Л. - М.:КУРС, НИЦ ИНФРА-М, 2016. - 152 с.: 60x90 1/16. - (Бакалавриат) (Переплёт 7БЦ) ISBN 978-5-906818-74-4 - Режим доступа: http://znanium.com/catalog/product/558694
3. Теория алгоритмов. Учебное пособие/М.С.Мерзоев, В.Л.Матросов. – Прометей, 2019. – 200 с.

Интернет источники

1. http://www.intuit.ru 
2. http://habrahabr.ru/blogs/programming/

Используемые образовательные технологии

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

1. для слепых:

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

• письменные задания выполняются на компьютере со специализированным программным обеспечением для слепых либо надиктовываются ассистенту;

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

• практические нормативы по элективным курсам адаптивной физической культуры выполняются в связке с наводящим (ассистентом).

2) для слабовидящих:

• обеспечивается индивидуальное равномерное освещение не менее 300 люкс;

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

• задания для выполнения, а также методические указания для выполнения аттестации оформляются увеличенным шрифтом;

• практические нормативы по элективным курсам адаптивной физической культуры при необходимости выполняются в связке с наводящим (ассистентом).

3) для глухих и слабослышащих:

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

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

4) для слепоглухих:

• предоставляются услуги тифлосурдопереводчика (помимо требований, выполняемых соответственно для слепых и глухих);

• практические нормативы по элективным курсам адаптивной физической культуры при необходимости выполняются в связке с наводящим (ассистентом).

5) для лиц с тяжелыми нарушениями речи, глухих, слабослышащих занятия проводятся в письменной форме;

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

6) для лиц с нарушениями двигательных функций верхних конечностей или отсутствием верхних конечностей:

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

• написание рефератов или подготовка презентаций по разработанной для каждого

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

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

Для студентов с нарушениями слуха.

Наличие звукоусиливающей аппаратуры, мультимедийных средств.

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

Учебная аудитория, в которой обучаются студенты с нарушением слуха, оборудована компьютерной техникой, аудиотехникой (акустический усилитель и колонки),

видеотехникой (мультимедийный проектор, телевизор), электронной доской, мультимедийной системой. Особую роль в обучении слабослышащих также играют видеоматериалы.

Для студентов с нарушениями зрения.

Наличие  программ  невизуального  доступа  к  информации,  программ-синтезаторов

речи.

Компьютерные тифлотехнологии базируются на комплексе аппаратных и программных средств, обеспечивающих преобразование компьютерной информации в доступные для незрячей и слабовидящей формы (звуковое воспроизведение,) и позволяют им самостоятельно работать на обычном персональном компьютере с программами общего назначения. В сети Интернет имеется версия официального сайта филиала для слабовидящих (для инвалидов и лиц с ограниченными возможностями здоровья по зрению)

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

Для студентов с нарушениями опорно-двигательного аппарата.

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

Для студентов с нарушениями опорно-двигательного аппарата используются альтернативные устройства ввода информации. Имеются специальные возможности операционной системы Windows, таких как экранная клавиатура, с помощью которой можно вводить текст, настройка действий Windows при вводе с помощью клавиатуры или мыши.

При  проведении  практических  занятий  среди        студентов-инвалидов  и  лиц  с  ОВЗ

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

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

1. Операционная система Windows
2. Пакет офисных программ Microsoft Office
3. Справочная правовая система «Консультант Плюс» (версия «ПРОФ»)
4. Электронный периодический справочник «Система ГАРАНТ»
5. Электронно-библиотечная система издательства

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

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

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

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

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

Доступная форма предоставления заданий оценочных средств: в печатной форме, в печатной форме увеличенным шрифтом, в форме электронного документа, задания зачитываются ассистентом, задания предоставляются с использованием сурдоперевода.

Доступная форма предоставления ответов на задания (письменно на бумаге, набор ответов на компьютере, с использованием услуг ассистента, устно).

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

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

Аннотация к рабочей программы

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

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

Рабочая программа учебной дисциплины разработана в соответствии с требованиями ФГОС СПО по данной специальности и на основе примерной программы учебной дисциплины, рекомендованной Экспертным советом по профессиональному образованию Федерального государственного автономного учреждения Федерального института развития образования (ФГАУ ФИРО), заключение Экспертного совета  № 093 от 02 марта 2012 г, в соответствии с Требованиями к организации образовательной деятельности для лиц с ограниченными возможностями здоровья в профессиональных образовательных организациях, в том числе требованиями к средствам обучения и воспитания, утвержденными Минобрнауки РФ 26 декабря 2013 г. N 06-2412вн.

Включает в себя: паспорт рабочей программы (место учебной дисциплины в структуре ОПОП, цели и задачи учебной дисциплины – требования к результатам освоения дисциплины); структуру и содержание учебной дисциплины (объем учебной дисциплины и виды учебной работы, тематический план и содержание учебной дисциплины); условия реализации дисциплины (требования к минимальному материально-техническому обеспечению, информационное обеспечение обучения, перечень рекомендуемых учебных изданий, Интернет-ресурсов, основной и дополнительной литературы); контроль и оценку результатов освоения дисциплины.

Максимальная учебная нагрузка (всего часов) – 78, в том числе обязательная аудиторная учебная нагрузка – 52 часа, самостоятельная работа – 26 часов.

Вид промежуточной аттестации – экзамен (5 семестр).

Наименование разделов дисциплины:

1. Основные модели алгоритмов.
2. Методы построения алгоритмов.
3. Методы вычисления сложности работы алгоритмов.

Учебно-методический блок

 Учебно-методические материалы для проведения занятий

Раздел 1. Основные модели алгоритмов

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

Содержание учебного материала

1. Алгоритмы. Общие сведения.
2. Основные требования к алгоритмам.
3. Свойства алгоритмов.
4. Способы представления алгоритмов
5. Основные алгоритмические структуры

Самостоятельная работа обучающихся: Реферат: Теория алгоритмов. Исторический обзор

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

Содержание учебного материала:

1. Машина Поста.
2. Машина Тьюринга
3. Устройство машины Тьюринга
4. Алгоритмически неразрешимые проблемы

Лабораторные работы: Решение задач, составление алгоритмов и программ.

Задачи, используется машина Поста.

1. На ленте находятся два массива меток, разделенных пробелом. Пусть в первом из них А меток, а во втором В меток.  Каретка стоит на самой правой метке первого числа. Сформировать справа от них через пустую секцию результирующий массив, в котором А+В меток.
2. Целое число N записано на ленте в унарной системе счисления (как последовательность из N меток). вычислить функцию, которая равна 1, если число N чётное, и равна 0 (оставляет пустую ленту), если N - нечётное. В начальный момент каретка стоит над первой слева меткой.
3. Определить, какая из двух групп, разделенных пустой секцией, больше, и удалить из нее самую правую метку. Каретка стоит на самой правой метке первого числа.
4. Скопировать число, записанное в унарной системе счисления. Каретка стоит на самой левой метке, входящей в число.
5. Деление с остатком. На ленте записаны в унарной системе делитель, а потом через пробел - делимое (возможно, нуль), Каретка стоит на первом знаке делителя.
6. В конце работы слева от каретки - частное, справа - остаток от деления.
7. На ленте расставлены метки, между которыми могут быть пропуски длиной в одну ячейку. Заполнить все пропуски метками. Каретка стоит над самой левой меткой.
8. На ленте расположен массив, состоящий из нечетного количества идущих подряд меток. Каретка стоит у самой левой метки массива. Найти среднюю метку массива и стереть ее.
9. На ленте записаны два числа в унарной системе счисления (как цепочки идущих подряд меток). Числа разделены одной пустой ячейкой, над ней находится каретка. Число справа от каретки больше числа слева от каретки. Вычесть из «правого» числа «левое».

Задачи, используется машина Тьюринга.

1. Сортировка цепочки из букв "а" и "б" так, чтобы сначала стоял все буквы "а", а потом - все буквы "б". Каретка стоит над строкой.
2. Даны два числа: одно (A) - в восьмеричной системе счисления, другое (B) - в троичной. Вычислить сумму в восьмеричной системе счисления.
3. Даны два числа (A и B) в двоичной системе счисления, разделенные знаком «+». Вычислить их сумму.
4. На информационной ленте машины Тьюринга в произвольном порядке записаны 3 буквы A, B и C. В начальном состоянии каретка обозревает букву, крайнюю справа. Поменять местами крайние буквы.
5. Удалить все вхождения символа 'a'. Каретка находится на первом символе слова.
6. Удалить из слова второй символ, если он есть. Каретка находится в начале слова.
7. Удвоить слово, поставив между ним и его копией знак =. Каретка находится на первом символе слова.
8. Если первый и последний символы (непустого) слова одинаковы, тогда это слово не менять, а иначе заменить его на пустое слово. Каретка стоит на первом символе слова.
9. Вставить символ 'a' за первым вхождением символа 'c', если он есть. Каретка находится на первом символе слова.
10. Даны два числа (A и B) в десятичной системе счисления, разделенные знаком «-». Вычислить их разность.

Алгоритмически неразрешимые проблемы:

1. Доказать теорему: существует функция, не вычислимая по Тьюрингу, т.е. не вычислимая ни на одной машине Тьюринга.
2. Доказать, что проблема эквивалентности слов является алгоритмически неразрешима.

Методические рекомендации по решению задач с использованием машины Поста и машины Тьюринга: для решения задач необходимо использовать тренажеры для изучения универсальных исполнителей https://kpolyakov.spb.ru/prog/turing.htm, https://kpolyakov.spb.ru/prog/post.htm 

Список рекомендуемой литературы:

В.И.Игошин. Теория алгоритмов: учеб. пособие для студ. Учреждений сред. проф. образования – 3-е изд., стер. – М.Издательский центр «Академия», 2019. – 320 с. (Главы 1, 3, 6)

Раздел 2. Методы построения алгоритмов

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

Содержание учебного материала:

1. Арифметика многоразрядных целых чисел.
2. Комбинаторные алгоритмы.
3. Перебор и методы его сокращения.
4. Сортировка.
5. Алгоритмы на графах. Поиск в графе. Поиск в глубину. Поиск в ширину.
6. Алгоритмы на графах. Кратчайшие пути.
7. Динамическое программирование.

Лабораторные работы: Решение задач, составление алгоритмов и программ.

1. Ввод и вывод длинного числа.
2. Сравнение длинных чисел.
3. Сложение и вычитание длинных чисел.
4. Вычисление 100!
5. Сколькими способами можно выбрать 13 из 52 игральных карт, различая их только по масти?
6. В чемпионате по футболу принимают участие 17 команд и разыгрываются золотые, серебряные и бронзовые медали. Сколькими способами они могут быть определены?
7. Сколькими способами можно выбрать три из пяти букв слова эскиз?
8. Дана вещественная матрица А(N,M). Составить программу замены всех положительных элементов матрицы на элемент, имеющий минимальное значение.
9. Реализация методов сортировки.
10. Напишите подробный алгоритм обхода в глубину, использующий представление графа с помощью матрицы примыканий; при посещении очередной вершины алгоритм должен просто печатать ее метку.
11. Напишите подробный алгоритм обхода по уровням, использующий представление графа с помощью списка примыканий; при посещении очередной вершины алгоритм должен просто печатать ее метку.
12. Выполните алгоритм поиска кратчайшего пути из вершины А во все остальные вершины в каждом из следующих примеров. Подсчитайте количество просмотренных Вами ребер (если Вы обращаетесь к ребру несколько раз, то всякий раз его нужно учитывать заново). (рис 1)

Рисунок 1. Графы

Самостоятельная работа обучающихся: Выполнение домашних заданий по теме 2.1

Написать часть алгоритма на языке программирования:

1. Умножение длинных чисел.
2. Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли бить друг друга?
3. Партия состоит из 25 человек. Требуется выбрать председателя партии, его заместителя, секретаря и казначея. Сколькими способами можно это сделать, если каждый член партии может занимать лишь один пост.
4. Дана вещественная матрица А(N,M). Составить программу замены всех отрицательных элементов матрицы на элемент, имеющий максимальное значение.

Список рекомендуемой литературы:

1. Длинная арифметика В.Гольдштейн
2. ДЖ. МАККОНЕЛЛ, Основы современных алгоритмов. 2-е дополненное издание. Перевод с английского под редакцией С.КЛандо. Дополнение М.В.Ульянова
3. Программирование в алгоритмах / С. М. Окулов. —М.: БИНОМ. Лаборатория знаний, 2002 — 341 с: ил.

Раздел 3. Методы вычисления сложности работы алгоритмов

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

Содержание учебного материала:

1. Сравнительные оценки алгоритмов.
2. Классификация алгоритмов по виду функции трудоёмкости
3. Теория сложности вычислений и сложностные классы задач.
4. Рекурсивные алгоритмы и методы их анализа.

Лабораторные работы:  

1. Анализ алгоритма решения задачи

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

1) Дан массив целых чисел осуществить сортировку четных элементов массива.

2)Дан массив целых чисел осуществить сортировку элементов массива записанных на нечетных местах.

3) Дан массив целых чисел осуществить сортировку отрицательных элементов массива.

4) Дан массив целых чисел осуществить сортировку положительных элементов массива.

5) В упорядоченный по возрастанию значений элементов массив М, состоящий из целых чисел, необходимо вставить число, не нарушив упорядоченности исходного массива.

6) Задан массив М, состоящий из N целочисленных элементов. Упорядочить элементы таким образом, чтобы вначале располагались все нечетные аргументы, а после них все четные.

7). Задан массив М, состоящий из N целочисленных элементов. Упорядочить элементы таким образом, чтобы вначале располагались все четные аргументы, а после них все нечетные.

2. Анализ рекурсивного алгоритма

1) Написать программу, которая выводит на экран n первых чисел ряда Фибоначчи.

2) Найти удвоенное десятое число Фибоначчи.

3)  Создать рекурсивную функцию вычисляющую сумму ряда

Список рекомендуемой литературы:

1. А.А. Разборов. Краткие лекции по теории сложности вычислений.

http://genesis.mi.ras.ru/~razborov/phasis.ps  

http://www.mi.ras.ru/~razborov/lecture.ps  

2. Н. Н. Кузюрин. Эффективные алгоритмы и сложность вычислений.

http://discopal.ispras.ru/ru.book-advanced-algorithms.htm  

3. http://www.wisdom.weizmann.ac.il/~oded/cc.html  
4. В.В. Ященко и др. Введение в криптографию.

http://nature.web.ru/db/msg.html?mid=1157083  

Самостоятельная работа обучающихся: Реферат: Рекурсивные функции и алгоритмы

Бюджетное учреждение профессионального образования

Ханты-Мансийского автономного округа-Югры

«Нижневартовский социально-гуманитарный колледж»

(БУ«Нижневартовский социально-гуманитарный колледж»)

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

(индекс и наименование  учебной дисциплины/ междисциплинарного курса)

основной профессиональной образовательной программы

по специальности СПО

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

(код, наименование)

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

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

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

Таблица 1

Организация контроля и оценивания

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

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

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

       Доступная форма предоставления заданий оценочных средств: в печатной форме, в печатной форме увеличенным шрифтом, в форме электронного документа, задания зачитываются ассистентом, задания предоставляются с использованием сурдоперевода.

       Доступная форма предоставления ответов на задания (письменно на бумаге, набор ответов на компьютере, с использованием услуг ассистента, устно).

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

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

Материально-техническое обеспечение контрольно-оценочных мероприятий

Контрольно-оценочные мероприятия проводятся в лабораториях информационно-коммуникационных систем.

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

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

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

1) для обучающихся с ограниченными возможностями здоровья по зрению:

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

• справочная информация  о расписании лекций, учебных занятий, промежуточной аттестации  изготовлена в адаптированной форме и размещается в папке на вахте колледжа
• входные группы и внутренние структуры здания колледжа снабжены тактильными знаками и желтыми полосами для удобства перемещения
• читальный зал и аудитории оснащены портативными видеоувеличителями текста и лупами
• в наличии имеется программное обеспечение:

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

-  компьютер, оснащенный дисплеем для вывода информации рельефно-точечным шрифтом,

- читающая машина,

- устройство создания рельефной графики для тактильного восприятия

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

2) для обучающихся с ограниченными возможностями здоровья по слуху:

• справочная информации о расписании учебных занятий, промежуточной аттестации, об изменениях в учебных занятиях  подается визуально на первом этаже от входа левое крыло, на каждом этаже - на настенных мониторах
•  информация о звонке на урок/с урока подается зрительно, для этих целей в фойе и коридорах размещены красные световые индикаторы

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

-  система организации равномерного звукового поля,

- персональные наушники,

- аудиосистема для создания безбарьерной среды,

- индукционные петли,

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

3) для обучающихся, имеющих нарушения опорно-двигательного аппарата:

• материально-технические условия:

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

- в цокольном этаже расположена  специализированная туалетная комната, оснащенная поручнями;

-  в наличии  специальные гусеничные подъемники  для передвижения инвалидных колясок по ступеням

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

• в наличии имеется программное обеспечение:

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

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

- специализированный манипулятор управления с выносными кнопками,  

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

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

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

Требования к выполнению самостоятельной работы (реферат):

1. Изложение текста и оформление реферата выполняют в соответствии с требованиями ГОСТ 7.32 – 2017, ГОСТ 2.114-2016 . Страницы текстовой части и включенные в нее иллюстрации и таблицы должны соответствовать формату А4 по ГОСТ 9327-60.
2. Реферат должен быть выполнен с использованием компьютера и принтера на одной стороне бумаги формата А4 через полтора интервала. Цвет шрифта должен быть черным, высота букв, цифр и других знаков не менее 1.8 (шрифт Times New Roman, 14 пт.).
3. Текст следует печатать, соблюдая следующие размеры полей: верхнее и нижнее — 20 мм, левое — 30 мм, правое — 10 мм. Абзацный отступ должен быть одинаковым по всему тексту и составлять 1,25 см.
4. Выравнивание текста по ширине.
5. Разрешается использовать компьютерные возможности акцентирования внимания на определенных терминах, формулах, применяя выделение жирным шрифтом, курсив, подчеркивание.
6. Перенос слов недопустим!
7. Точку в конце заголовка не ставят. Если заголовок состоит из двух предложений, их разделяют точкой.
8. Подчеркивать заголовки не допускается.
9. Расстояние между заголовками раздела, подраздела и последующим текстом так же, как и расстояние между заголовками и предыдущим текстом, должно быть равно 15мм (2 пробела).
10. Название каждой главы и параграфа в тексте работы можно писать более крупным шрифтом, жирным шрифтом, чем весь остальной текст. Каждая глава начинается с новой страницы, параграфы (подразделы) располагаются друг за другом.
11. В тексте реферат рекомендуется чаще применять красную строку, выделяя законченную мысль в самостоятельный абзац.
12. Перечисления, встречающиеся в тексте реферата, должны быть оформлены в виде маркированного или нумерованного списка.

Пример:

Цель работы:

1). Научиться организовывать свою работу;

2). Поставить достижимые цели;

3). Составить реальный план;

4). Выполнить его и оценить его результаты

13. Все страницы обязательно должны быть пронумерованы. Нумерация листов должна быть сквозной. Номер листа проставляется арабскими цифрами.
14. Нумерация листов начинается с третьего листа (после содержания) и заканчивается последним. На третьем листе ставится номер «3».
15. Номер страницы на титульном листе не проставляется!
16. Номера страниц проставляются в центре нижней части листа без точки. Список использованной литературы и приложения включаются в общую нумерацию листов.
17. Рисунки и таблицы, расположенные на отдельных листах, включают в общую нумерацию листов и помещают по возможности следом за листами, на которых приведены ссылки на эти таблицы или иллюстрации. Таблицы и иллюстрации нумеруются последовательно арабскими цифрами сквозной нумерацией. Допускается нумеровать рисунки и таблицы в пределах раздела. В этом случае номер таблицы (рисунка) состоит из номера раздела и порядкового номера таблицы, разделенных точкой.
18. Оформление литературы:

1. Каждый источник должен содержать следующие обязательные реквизиты:

 - фамилия и инициалы автора;

- наименование;

- издательство;

- место издания;

- год издания.

2. Все источники, включенные в библиографию, должны быть последовательно пронумерованы и расположены в следующем порядке:

- законодательные акты;

- постановления Правительства;

- нормативные документы;

- статистические материалы;

- научные и литературные источники – в алфавитном порядке по первой букве фамилии автора.

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

Глоссарий

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

Алгоритм линейной структуры(Следование) - Алгоритм, в котором все действия выполняются последовательно друг за другом.

Алгоритмизация - Техника составления алгоритмов и программ для решения задач на ЭВМ.

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

 Ветвление - Схема, в которой предусмотрено разветвление указанной последовательности действий на два направления в зависимости от итога проверки заданного условия.

Вещественный Тип(REAL) - Элементы подмножеств вещественного типа.

 Выражение - Совокупность операций и операндов.

 Графический способ записи Алгоритмов - Описание алгоритма с помощью графических символов.

 Дискретность - Свойство алгоритма разчленять предопределённый алгоритмом вычислительный процесс, на отдельные этапы, элементарные операции.

 Идентификатор - Последовательность символов, начинающаяся с буквы, для наименования объектов.

 Интерпретатор - Програмный продукт, выполняющий предъявленную программу путём одновременного её онализа и реализации предписанных ею действий.

 Итерация - Повторение последовательности операторов, включающим проверку условия в начале каждого прохода цикла.

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

 Константа - Элемент данных, сохраняющий неизменное значение в течении всего времени выполнения программы.

Логический тип(BOOLEAN) - Одно из двух истиностных значений, обозначаемых предопределёнными именами false и true.

 Массовость - Свойство алгоритма, позволяющее решать однотипичные задачи с различными исходными дынными по одному алгоритму.

 Метка - Произвольный идентифакатор, позволяющий именовать некоторый оператор программы и таким образом ссылаться на него.

Оператор выбора - Оператор для программирования алгоритмов с множиственным выбором (CASE-OF-ELSE-END)

 Оператор перехода - Оператор передачи управления соответствующиму меченому оператору(GOTO)

Оператор повторений WHILE-DO - Оператор для программирования алгоритмов циклической структуры с предпроверкой условия.

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

 Определённость - Свойство алгоритма исключать произвольность толкования любого из предписаний и заданного порядка исполнения.

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

Переменная - Объект, имеющий фиксированное имя, фиксированный тип и изменяющееся в зависимости от применяемых действий значение.

 Программирование - Процесс определения последовательности инструкций, которые должен выполнить компьютер для решения определённой задачи.

 Программный способ записи алгоритмов - запись алгоритма на языке программирования.

Результативность - Свойство алгоритма через определённое число шагов приводит к выдаче результатов или сообщения о невозможности решения задачи.

 Символьный(литерный) тип - Элементы конечного и упорядоченного множества символов.

 Синтаксическая диаграмма - Направленый граф для описания синтаксиса языка, в соответствии с которым строится синтаксически правильная программа.

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

Скалярные переменные - Переменные, имеющие в качестве текущего значения только одну величену.

Словесный способ записи алгоритмов - Запись Последовательности действийв произвольном изложении на естественном язке

 Составной оператор - Последовательность произвольных операторов программы, заключённая в операторные скобки(BEGIN-END)

Стандартные типы данных - Изначало определённые типы данных, встроенные в ЭВМ

Структурированная переменная - Переменная, состоящая из нескольких элементов или компонент, на которую можно ссылаться как на единный объект.

Структурно-стилизованный способ записи алгоритмов - Запись алгоритма путём использования ограниченного набора типовых синтаксических конструкций.

 Тип данных - Множество значений, которые может принимать переменная и совокупность операций, выполняемых с этими данными.

Транслятор - Программа, осуществяющая перевод текстов с одного языка на другой.

Уровень языка программирования - Смысловая ёмкость его конструкции и его ориентация на программиста-человека.

Условный оператор - Оператор с ключевыми словами IF-THEN-ELSE для программирования алгоритмов разветвляющейся структуры.

Целый тип(INTEGER) - Элементы подмножества целых чисел.

Язык программирования - Система обозначений для точного описания алгоритмов для ЭВМ.

Приложение 2. Титульный лист отчета

по лабораторным работам

Бюджетное учреждение профессионального образования Ханты-Мансийского автономного округа - Югры "Нижневартовский социально-гуманитарный колледж"

ОТЧЕТ

По лабораторной работе №___

Раздел____