266

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования

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

Ю. А. Громов

АЛГОРИТМЫ И ТЕОРИЯ ВЫЧИСЛЕНИЙ

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

по подготовке к лекциям (включая рекомендации по организации самостоятельной работы) для обучающихся по дисциплине «Алгоритмы и теория вычислений»

по направлению подготовки 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 Содержание разделов дисциплины

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

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

4

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

Вконце семестра студенты проходят электронное тестирование по всем разделам курса. В конце тестирования студент видит, в каких разделах и сколько ошибочных ответов он дал и получает балл в диапазоне от 0,0 до 5,0. Перед зачётом студентам выдаётся список примерных вопросов, по которым можно понять, на что нужно сделать упор при подготовке к зачёту.

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

используя рекомендованную литературу; 3) выписать вопросы для подробного обсуждения с преподавателем на

консультации.

Перечень примерных вопросов, выносимых на зачёт:

Интуитивное понятие алгоритма Свойства алгоритмов, соответствующие его интуитивному представлению.

Приведите пример нарушения свойства детерминированности алгоритма Приведите пример нарушения свойства результативности алгоритма

Приведите пример нарушения свойства конечности алгоритма В чем суть свойства массовости алгоритма?

Основные типовые алгоритмы вычислительных задач. Арифметика нормализованных чисел.

Системы счисления.

Алгоритм перевода чисел из одной системы счисления в другую Принцип кодирования числовых данных в ЭВМ

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

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

Типовые структурные схемы алгоритмов. Понятие примитивно-рекурсивной функции.

Укажите пример примитивно-рекурсивной функции Понятие частично-рекурсивной функции.

Укажите пример частично-рекурсивной функции Понятия машины Тьюринга.

5

Композиция машин Тьюринга.

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

Понятие итерации машин Тьюринга. Приведите пример итерации машин Тьюринга.

Показатели оценки по зачёту представлены в таблице 2.

Таблица 2 Показатели оценки по зачёту

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