266
.pdfМинистерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
«Нижегородский государственный архитектурно-строительный университет»
Ю. А. Громов
АЛГОРИТМЫ И ТЕОРИЯ ВЫЧИСЛЕНИЙ
Учебно-методическое пособие
по подготовке к лекциям (включая рекомендации по организации самостоятельной работы) для обучающихся по дисциплине «Алгоритмы и теория вычислений»
по направлению подготовки 09.03.02 Информационные системы и технологии, без профиля
Нижний Новгород
2016
Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
«Нижегородский государственный архитектурно-строительный университет»
Ю. А. Громов
АЛГОРИТМЫ И ТЕОРИЯ ВЫЧИСЛЕНИЙ
Учебно-методическое пособие
по подготовке к лекциям (включая рекомендации по организации самостоятельной работы) для обучающихся по дисциплине «Алгоритмы и теория вычислений»
по направлению подготовки 09.03.02 Информационные системы и технологии, без профиля
Нижний Новгород ННГАСУ
2016
1
УДК 681.3 (075)
Громов Ю. А./ Алгоритмы и теория вычислений [Электронный ресурс]: учеб. – метод. пос./ Ю. А. Громов; Нижегор. гос. архитектур. – строит. ун-т – Н. Новгород: ННГАСУ, 2016. - 9 с. 1 электрон. опт. диск (CD-R)
Даются тематика лекций, их краткое содержание, а также методические рекомендации по самостоятельной работе обучающихся по дисциплине «Алгоритмы и теория вычислений». Указывается необходимая литература и источники, разъясняется последовательность их изучения, выделяются наиболее сложные вопросы и даются рекомендации по их изучению.
Предназначено для обучающихся в ННГАСУ по дисциплине «Алгоритмы и теория вычислений» по направлению подготовки 09.03.02 Информационные системы и технологии, без профиля.
© Ю. А. Громов © ННГАСУ. 2016.
2
Учебно-методическое пособие по подготовке к лекциям (включая рекомендации по организации самостоятельной работы) по дисциплине «Алгоритмы и теория вычислений» предназначены для студентов второго курса, обучающихся по направлению 09.03.02 Информационные системы и технологии, и содержат программу для проведения лекционных занятий, а также методические рекомендации по самостоятельной работе.
Цель учебно-методического пособия: помочь студентам при изучении учебной программы с использованием лекционных материалов и рекомендуемой учебно-методической литературы при формировании необходимых компетенций дисциплины «Алгоритмы и теория вычислений».
Целями освоения дисциплины «Алгоритмы и теория вычислений» являются изучение основных разделов теории алгоритмов и теории вычислений, используемых при проектировании различных информационных систем и технологий.
В лекциях излагается общая характеристика вопросов тем, даются практические примеры решения прикладных задач, осуществляется групповая работа студентов и преподавателя по разработке алгоритмического и программного обеспечения прикладных задач. Главной целью лекции является привитие студентам интереса к изучаемому материалу, формирование мотивации к последующему самостоятельному анализу рассматриваемой проблематики. На лекциях студентам раскрываются наиболее сложные вопросы и теоретические положения, показывается их практическая значимость, даются рекомендации по углубленному самостоятельному изучению теории и практики.
На лекциях по дисциплине «Алгоритмы и теория вычислений» широко используются активные формы проведения занятий. Такие формы организации образовательного процесса способствуют разнообразному (индивидуальному, групповому, коллективному) изучению учебных вопросов (проблем), активному взаимодействию студентов и преподавателя, живому обмену мнениями между ними, нацеленному на выработку правильного понимания содержания изучаемой темы и способов ее практического использования.
Материал пропущенных лекций студент восстанавливает самостоятельно и по всем непонятным положениям и вопросам обращается за разъяснением к преподавателю.
Самостоятельная работа направлена на развитие компетенций дисциплины:
-ОПК-2 - способность использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования;
-ПК-2 - способностью проводить техническое проектирование;
-ПК-12 - способность разрабатывать средства реализации информационных технологий (методические, информационные, математические, алгоритмические, технические и программные).
Виды и формы самостоятельной работы студентов по дисциплине:
3
-систематическая проработка лекций, основной и дополнительной литературы;
-подготовка к зачёту.
Содержание разделов дисциплины «Алгоритмы и теория вычислений» представлено в таблице 1.
Таблица 1 Содержание разделов дисциплины
|
|
|
|
Аудиторные занятия |
|
|
|
|||
|
|
|
|
|
(в часах) |
|
|
Перечень |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Самост |
компетенций, |
|
|
|
|
|
|
|
,семинарПрактика |
|
||
№ |
Наименование раздела |
Всего |
Лекции |
Лабораторные |
|
|
оятельн |
формируемых в |
||
п/п |
дисциплины |
часов |
|
|
ая |
процессе |
||||
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
работа |
освоения |
|
|
|
|
|
|
|
|
|
|
раздела |
|
|
|
|
|
|
|
|
|
|
|
|
Преобразование |
|
|
|
|
|
|
|
ОПК-2, ПК-2, |
|
1 |
числовой |
информации. |
10 |
4 |
|
|
2 |
|
4 |
|
|
|
|
ПК-12 |
|||||||
|
Системы счисления. |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
Машинная арифметика. |
|
|
|
|
|
|
|
|
|
2 |
|
|
10 |
4 |
|
|
2 |
|
4 |
ОПК-2, ПК-2, |
|
|
|
|
|
ПК-12 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
Основные |
положения |
10 |
4 |
|
|
2 |
|
4 |
ОПК-2, ПК-2, |
теории алгоритмов. |
|
|
|
ПК-12 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
Элементы |
теории |
10 |
4 |
|
|
2 |
|
4 |
ОПК-2, ПК-2, |
рекурсивных функций. |
|
|
|
ПК-12 |
||||||
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
5 |
Машины Тьюринга. |
10 |
4 |
|
|
2 |
|
4 |
ОПК-2, ПК-2, |
|
|
|
|
|
|
ПК-12 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
Итерации |
машин |
16 |
6 |
|
|
3 |
|
7 |
ОПК-2, ПК-2, |
|
Тьюринга. |
|
|
|
|
ПК-12 |
||||
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
7 |
Теорема Тьюринга. |
24 |
8 |
|
|
4 |
|
12 |
ОПК-2, ПК-2, |
|
|
|
|
|
|
|
ПК-12 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
На консультациях в |
течение |
семестра |
студенты |
могут |
обсуждать с |
преподавателем различные вопросы по теоретическим основам алгоритмизации способов решения прикладных задач.
Рекомендуется проработать конспект лекций, затем повторить теоретический материал, пользуясь рекомендованной основной и дополнительной литературой. Если после этого остаются вопросы, рекомендуется выписать их и обратиться к преподавателю на консультациях.
4
Втечение курса со студентами проводятся индивидуальные и групповые консультации по общетеоретическим вопросам, возникающим при самостоятельной работе студентов при подготовке к занятиям.
Вконце семестра студенты проходят электронное тестирование по всем разделам курса. В конце тестирования студент видит, в каких разделах и сколько ошибочных ответов он дал и получает балл в диапазоне от 0,0 до 5,0. Перед зачётом студентам выдаётся список примерных вопросов, по которым можно понять, на что нужно сделать упор при подготовке к зачёту.
При подготовке к зачету после получения перечня вопросов рекомендуется: 1) внимательно прочитать материал лекций; 2) постараться разобраться с непонятными, в частности, новыми терминами,
используя рекомендованную литературу; 3) выписать вопросы для подробного обсуждения с преподавателем на
консультации.
Перечень примерных вопросов, выносимых на зачёт:
Интуитивное понятие алгоритма Свойства алгоритмов, соответствующие его интуитивному представлению.
Приведите пример нарушения свойства детерминированности алгоритма Приведите пример нарушения свойства результативности алгоритма
Приведите пример нарушения свойства конечности алгоритма В чем суть свойства массовости алгоритма?
Основные типовые алгоритмы вычислительных задач. Арифметика нормализованных чисел.
Системы счисления.
Алгоритм перевода чисел из одной системы счисления в другую Принцип кодирования числовых данных в ЭВМ
Понятие вычислимой функции. Укажите пример невычислимой функции
Чем отличается формализованное понятие алгоритма от интуитивного?
Типовые структурные схемы алгоритмов. Понятие примитивно-рекурсивной функции.
Укажите пример примитивно-рекурсивной функции Понятие частично-рекурсивной функции.
Укажите пример частично-рекурсивной функции Понятия машины Тьюринга.
5
Композиция машин Тьюринга.
Приведите пример композиции машин Тьюринга. Простейшие вычислимые функции и операторы. Составьте программу для машины Тьюринга, реализующую простейшие вычислимые функции и операторы.
Понятие итерации машин Тьюринга. Приведите пример итерации машин Тьюринга.
Показатели оценки по зачёту представлены в таблице 2.
Таблица 2 Показатели оценки по зачёту
Показатели |
Бал- |
|
|
|
|
|
|
|
|
оценивания |
|
Оценка |
Критерий оценки |
||||||
лы |
|
||||||||
компетенций |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Результаты |
4,5 |
- |
«зачтено» |
ставится |
|
обучающемуся, |
|||
освоения |
5,0 |
|
|
показавшему |
|
|
глубокие |
||
дисциплины |
|
|
|
систематизированные |
знания |
||||
соответствует |
|
|
|
учебного материала, в полной |
|||||
требованиям |
|
|
|
мере |
соответствующие |
||||
ФГОС |
|
|
|
требованиям |
|
к |
уровню |
||
|
|
|
|
подготовки |
|
обучающегося, |
|||
|
|
|
|
проявившему |
|
творческие |
|||
|
|
|
|
способности |
в |
понимании, |
|||
|
|
|
|
изложении |
и |
использовании |
|||
|
|
|
|
учебного |
материала |
при |
|||
|
|
|
|
решении поставленных задач, |
|||||
|
|
|
|
умеющему |
|
|
обобщать |
||
|
|
|
|
информацию, |
|
|
|
|
|
|
|
|
|
аргументировано |
|
и |
|||
|
|
|
|
практически |
без |
ошибок |
|||
|
|
|
|
ответившему на все вопросы. |
|||||
Результаты |
3,5 |
- |
«зачтено» |
ставится |
|
обучающемуся, |
|||
освоения |
4,4 |
|
|
продемонстрировавшему |
|||||
дисциплины |
|
|
|
достаточно |
полные |
|
знания |
||
соответствует |
|
|
|
учебного материала, |
в целом |
||||
требованиям |
|
|
|
соответствующие |
|
|
|||
ФГОС |
|
|
|
требованиям |
|
к |
уровню |
||
|
|
|
|
подготовки |
|
обучающегося, |
|||
|
|
|
|
способность |
|
|
к |
|
их |
|
|
|
|
самостоятельному |
|
|
|||
|
|
|
|
восполнению и обновлению в |
|||||
|
|
|
|
ходе решения |
поставленных |
||||
|
|
|
|
задач, |
|
|
|
|
умение |
|
|
|
|
систематизировать |
|
|
|||
|
|
|
|
информацию, |
допустившему |
||||
|
|
|
6 |
|
|
|
|
|
|
|
Показатели |
|
Бал- |
|
|
|
|
|
|
|
|
|
|
оценивания |
|
|
Оценка |
|
Критерий оценки |
|
|||||
|
|
лы |
|
|
|
|||||||
|
компетенций |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
негрубые |
|
ошибки |
и |
|
||
|
|
|
|
|
|
недочеты. |
|
|
|
|
|
|
|
Результаты |
|
2,5 |
- |
«зачтено» |
ставится |
|
обучающемуся, |
|
|||
|
освоения |
|
3,4 |
|
|
показавшему уровень знаний |
|
|||||
|
дисциплины |
|
|
|
|
учебного материала в объёме, |
|
|||||
|
соответствует |
|
|
|
|
минимально |
необходимом |
|
||||
|
требованиям |
|
|
|
|
для |
решения |
поставленных |
|
|||
|
ФГОС |
|
|
|
|
задач, |
знание |
|
основ |
|
||
|
|
|
|
|
|
дисциплины, |
владеющего |
|
||||
|
|
|
|
|
|
навыками |
|
логического |
|
|||
|
|
|
|
|
|
мышления |
и |
допустившему |
|
|||
|
|
|
|
|
|
непринципиальные |
ошибки |
|
||||
|
|
|
|
|
|
при ответе на вопросы. |
|
|
||||
|
Результаты |
|
0,0 |
- |
«не зачтено» |
ставится |
|
обучающемуся, |
|
|||
|
освоения |
|
2,4 |
|
|
показавшему |
существенные |
|
||||
|
дисциплины |
НЕ |
|
|
|
пробелы в знании основного |
|
|||||
|
соответствует |
|
|
|
|
учебного |
|
материала, |
|
|||
|
требованиям |
|
|
|
|
допустившему |
|
|
|
|||
|
ФГОС |
|
|
|
|
принципиальные ошибки при |
|
|||||
|
|
|
|
|
|
применении знаний, |
которые |
|
||||
|
|
|
|
|
|
не позволяют ему приступить |
|
|||||
|
|
|
|
|
|
к |
решению |
поставленных |
|
|||
|
|
|
|
|
|
задач без |
дополнительной |
|
||||
|
|
|
|
|
|
подготовки. |
|
|
|
|
||
|
Перечень основной и дополнительной учебной литературы, необходимой |
|||||||||||
для освоения дисциплины. |
|
|
|
|
|
|
|
|
|
|||
|
Основная литература: |
|
|
|
|
|
|
|
|
|
1.под ред. А.Н. Супруна Информатика : учеб. пособие для студентов вузов по спец. "Пром. и гражд. стр-во" направления подгот. дипломир. специалистов "Стр-во". М. : Изд-во АСВ, 2006
2.Кулиш У., Рац Д., Хаммер Р., Хокс М., Яковлев А. Г. Достоверные вычисления. Базовые численнные методы: учебное пособие. Москва, Ижевск: Регулярная и хаотическая динамика, 2013
3.Марченков С. С. Рекурсивные функции. Москва: ФИЗМАТЛИТ, 2007
4.Рязанов Ю. Д. Теория вычислительных процессов: Лабораторный практикум. Учебное пособие. Белгород: Белгородский государственный технологический университет им. В.Г. Шухова, ЭБС АСВ, 2011
7
Дополнительная литература:
1.Синюк В. Г., Рязанов Ю. Д. Алгоритмы и структуры данных: Лабораторный практикум. Учебное пособие. Белгород: Белгородский государственный технологический университет им. В.Г. Шухова, ЭБС АСВ, 2013
2.Штарьков Ю. М. Универсальное кодирование. Теория и алгоритмы. Москва: ФИЗМАТЛИТ, 2013
3.Львович И. Я., Ермолова В. В., Преображенский Ю. П. Основы информатики: учебное пособие. Воронеж: Воронежский институт высоких технологий, 2014
Перечень ресурсов информационно – телекоммуникационной сети «интернет» (далее - сеть «интернет»), необходимых для освоения дисциплины:
1. http://www.intuit.ru – Национальный открытый университет.
8
Громов Юрий Алексеевич
Учебно-методическое пособие
по подготовке к лекциям (включая рекомендации по организации самостоятельной работы) для обучающихся по дисциплине «Алгоритмы и теория вычислений»
по направлению подготовки 09.03.02 Информационные системы и технологии, без профиля
Федеральное государственное бюджетное образовательное учреждение высшего образования «Нижегородский государственный архитектурно-строительный университет»
603950, Нижний Новгород, ул. Ильинская, 65. http://www.nngasu.ru, srec@nngasu.ru
9