Рабочая программа дисциплины «Алгоритмы и анализ сложности»

Скачать 0.5 Mb.

Название	Рабочая программа дисциплины «Алгоритмы и анализ сложности»
страница	4/5
Дата публикации	15.10.2014
Размер	0.5 Mb.
Тип	Рабочая программа

100-bal.ru > Информатика > Рабочая программа

1 2 3 4 5

Раздел 4. Контрольный раздел (промежуточная аттестация)
В начале каждой лекции, кроме первой, производится экспресс-тестирование по материалам предыдущих лекций. На первой лекции производится входное тестирование. Разбор теста производится немедленно. Тестирование оценивается по 9-балльной шкале (1 балл – просто за попытку, 9 баллов - безошибочное выполнение). Оценка выставляется по формализованным критериям в зависимости от числа допущенных ошибок. Оценки суммируются за период до даты рубежного контроля и нормализуются в соответствии с требованиями, выдвигаемыми факультетом. Тесты обновляются к каждой лекции и в последствии публикуются на интернет-странице курса.

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

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

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

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

Не имитационные неигровые технологии:

метод проектов (мини-проекты),
кейс-метод.

Имитационные игровые технологии – метод «Дебаты», деловые игры.
Информационно-коммуникативные технологии:

Интернет-технологии;
Технология проблемного обучения;
Компьютерное тестирование;
Мультимедийные технологии;
Технология дистанционного обучения.

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

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

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

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

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

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

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

Вопросы к экзамену для студентов
1. Конструктивные логические теории.

2. Вычислительная интерпретация логических формул.

3. Вычислительная интерпретация доказательств.

4. Машины Тьюринга и другие модели вычислений.

5. Машины Джонса.

6. Равнодоступные адресные машины.

7. РАМ с хранимой программой.

8. Примитивно рекурсивные функции.

9. Частично-рекурсивные и общерекурсивные функции.

10. Тезисы Черча, Тьюринга, Маркова.

11. Эквивалентность разных моделей вычислимости.

12. Универсальные алгоритмы.

13. Рекурсивно разрешимые множества, неразрешимые множества.

14. Примитивно рекурсивные множества, отношения, предикаты.

15. Перечислимые множества и не перечислимые множества.

16. Элементарные функции, множества, отношения, предикаты.

17. Классы функция, основанных на ограниченной рекурсии.

18. Классы Гжегорчика и их аналоги.

19. Классы словарных функций.

20. Определение словарных функций с помощью словарной ограниченной рекурсии.

21. Конечная сложность вычислений (сложность вычислений наконечных равнодоступных адресных машинах).

22. Алгоритмическая (описательная, дескриптивная) сложность.

23. Алгоритмическое определение случайности.
Пример набора задач к экзамену
1. РАМ для нахождения максимума 100 входных чисел.
2. РАМ для нахождения минимума 400 входных чисел.
3. РАМ для нахождения максимума входных чисел, не превосходящих 200,

(всего дано 500 входных чисел) или выдать 300, если таких чисел нет.
4. РАМ для нахождения минимума входных чисел, не меньших 50,

(всего дано 150 входных чисел) или 0, если таких чисел нет.
5. РАМ для вычисления максимума попарных сумм из 120 входных чисел

(x[1],...,x[120]) x[i]+x[j], меньших 10 при i,j=1,...,120.
6. РАМ для вычисления миниимума попарных сумм из 80 входных чисел

(x[1],...,x[80]) x[i]+x[j], больших 20 при i,j=1,...,80.
7. РАМ для вычисления максимума попарных разностей 40 входных чисел.
8. РАМ для вычисления минимума попарных положительных разностей 60

входных чисел.
9. Машина Тьюринга, распознающая слова длины 3 в алфавите {0,1}

(101 -> 1, 10 -> 0, 1111 - > 0)
10. Машина Тьюринга, распознаюшие слова в алфавите {0,1}, имеющие

более 2-x единиц в своем составе (010 -> 0, 11 -> 0, 1011 -> 1).
11. РАМ для нахождения наименьшего из номеров наибольших чисел в заданной

последовательности из 10 чисел (2 2 3 4 5 7 6 7 4 3 -> 6).
12. РАМ для нахождения наибольшего из номеров наибольших чисел в заданной

последовательности из 10 чисел (2 2 3 4 5 7 6 7 4 3 -> 8).
13. РАМ для нахождения наименьшего из номеров наименьших чисел в заданной

последовательности из 10 чисел (3 2 2 3 4 5 7 6 7 4 -> 2).
4. РАМ для нахождения наибольшего из номеров наименьших чисел в заданной

последовательности из 10 чисел (2 2 3 4 5 7 6 7 4 3 -> 2).
15. Машина Тьюринга для уменьшения числа на 3 в монадической

("палочковой") системе счисления.
16. Машина Тьюринга для увеличения числа на 4 в монадической

("палочковой") системе счисления.
17. Машина Тьюринга для распознавания слова в алфавите {0,1},

состоящего из одних единиц.
18. Машина Тьюринга для распознавания словав алфавите {0,1},

состоящего из одних нулей.
19. РАМ для определения наименьшего положительного натурального

i, при котором x[i]=x[1] по входным числам x[1],...,x[80].
20. РАМ для определения наибольшего натурального i от 0 до 80,

при котором x[i]=x[1] по входным числам x[1],...,x[80].
21. РАМ для нахождения такого наименьшего i, что

x[i]=max{x[1],...,x[70],70} или i=71 по x[1],...,x[70].
22. РАМ для нахождения такого наибольшего i, что

x[i]=min{76,x[1],...,x[75]} или i=0 по x[1],...,x[75].
23. РАМ для вычисления такого наименьшего i (от 1 до 101), что

x[i]=0 или i=101 по входным числам x[1],...,x[100].
24. РАМ для вычисления такого наибольшего i (от 0 до 100), что

x[i]=0 или i=0 по входным числам x[1],...,x[100].

Связь логики и вычислимости

Примерное содержание тестов
Промежуточные тесты

8.1.11. Пусть p=R(O,I32), q=I22 o R(O, I32), m=R(I11, p o I33).

Чему равно:

8.1.11.1. p(3,0)

8.1.11.2. p(2,1)

8.1.11.3. q(0)

8.1.11.4. q(2)

8.1.11.5. m(2,0)

8.1.11.6. m(2,1)

8.1.11.7. m(1,2)
8.1.12. Написать программу машины Тьюринга для сложения нескольких

чисел в монадической ("палочковой") системе счисления, разделенных

знаком "+".
8.1.13. Что делает машина Тьюринга

aq>qqr

bq> qqqr

q>1s

aqq>aqqr

bqq>bqqr

aqqq>aqqqr

bqqq>bqqqr

qq> qqqql

qqq> qqqqql

aqqqq> qqqqqql

bqqqqq> qqqqqql

aqqqqq> qqqqqqql

bqqqq> qqqqqqql

qqqq>1s

qqqqq>1s

aqqqqqq>aqqqqqql

bqqqqqq>bqqqqqql

aqqqqqqq> qqqqqqql

bqqqqqqq> qqqqqqql

qqqqqq> qr

qqqqqqq>0s

со словами: "", "a", "ba", "aba", "abba", "baba"?"
8.1.14. Что делает алгоритм

f(ex','ee)=ex':'f(ee);

f(ee)=ee;
f('a,b')=?, f('a')=?, f('a,b,c')=?

Зачётные (итоговые) тесты
1. РАМ для нахождения максимума 100 входных чисел.
2. РАМ для нахождения минимума 400 входных чисел.
3. РАМ для нахождения максимума входных чисел, не превосходящих 200,

(всего дано 500 входных чисел) или выдать 300, если таких чисел нет.
4. РАМ для нахождения минимума входных чисел, не меньших 50,

(всего дано 150 входных чисел) или 0, если таких чисел нет.
5. РАМ для вычисления максимума попарных сумм из 120 входных чисел

(x[1],...,x[120]) x[i]+x[j], меньших 10 при i,j=1,...,120.
6. РАМ для вычисления миниимума попарных сумм из 80 входных чисел

(x[1],...,x[80]) x[i]+x[j], больших 20 при i,j=1,...,80.
7. РАМ для вычисления максимума попарных разностей 40 входных чисел.
8. РАМ для вычисления минимума попарных положительных разностей 60

входных чисел.
9. Машина Тьюринга, распознающая слова длины 3 в алфавите {0,1}

(101 -> 1, 10 -> 0, 1111 - > 0)
10. Машина Тьюринга, распознаюшие слова в алфавите {0,1}, имеющие

более 2-x единиц в своем составе (010 -> 0, 11 -> 0, 1011 -> 1).
11. РАМ для нахождения наименьшего из номеров наибольших чисел в заданной

последовательности из 10 чисел (2 2 3 4 5 7 6 7 4 3 -> 6).
12. РАМ для нахождения наибольшего из номеров наибольших чисел в заданной

последовательности из 10 чисел (2 2 3 4 5 7 6 7 4 3 -> 8).
13. РАМ для нахождения наименьшего из номеров наименьших чисел в заданной

последовательности из 10 чисел (3 2 2 3 4 5 7 6 7 4 -> 2).
4. РАМ для нахождения наибольшего из номеров наименьших чисел в заданной

последовательности из 10 чисел (2 2 3 4 5 7 6 7 4 3 -> 2).
15. Машина Тьюринга для уменьшения числа на 3 в монадической

("палочковой") системе счисления.
16. Машина Тьюринга для увеличения числа на 4 в монадической

("палочковой") системе счисления.
17. Машина Тьюринга для распознавания слова в алфавите {0,1},

состоящего из одних единиц.
18. Машина Тьюринга для распознавания слова алфавите {0,1},

состоящего из одних нулей.
19. РАМ для определения наименьшего положительного натурального

i, при котором x[i]=x[1] по входным числам x[1],...,x[80].
20. РАМ для определения наибольшего натурального i от 0 до 80,

при котором x[i]=x[1] по входным числам x[1],...,x[80].
21. РАМ для нахождения такого наименьшего i, что

x[i]=max{x[1],...,x[70],70} или i=71 по x[1],...,x[70].
22. РАМ для нахождения такого наибольшего i, что

x[i]=min{76,x[1],...,x[75]} или i=0 по x[1],...,x[75].
23. РАМ для вычисления такого наименьшего i (от 1 до 101), что

x[i]=0 или i=101 по входным числам x[1],...,x[100].
24. РАМ для вычисления такого наибольшего i (от 0 до 100), что

x[i]=0 или i=0 по входным числам x[1],...,x[100].

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

«5» – ответ четкий, грамотный, логичный. Ответы полные, подкреплены примерами, показаны глубокие знания теории. Студент способен использовать теоретические знания при решении практических задач.

«4» – ответ правильный, недостаточно четкий. Студент показал знание материала, но не привёл примеры, слабо ориентируется в теории.

«3» – ответ недостаточно полный, рассказ непоследовательный, с ошибками. Слабое знание учебного материала, неуверенность в ответах, допускаются не точности.

«2» – ответы на вопросы не полные, имеются грубые ошибки, либо ответ отсутствует. На дополнительные вопросы нет ответов.

Основными технологиями оценки уровня сформированности компетенций являются:

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

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

Общее количество баллов: 100

Количество рубежных контролей: 2

Учитывается:

Текущий контроль – посещение лекций и лабораторных занятий и работа на них.

Рубежный контроль – результаты тестов по специализации оцениваются по 9-ти балльной системе (каждый из тестов); оценки, полученные за выполнение лабораторных работ, оценки хода выполнения курсовых работ; баллы за тестирование программ. Промежуточная аттестация по итогам освоения дисциплины предполагает суммарно 30 баллов и получается линейным нормированием суммарной оценки.

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

8. Учебно-методическое и информационное обеспечение дисциплины
Основная литература
1. Абрамов С.А. Лекции о сложности алгоритмов. - М.: МЦНМО, 2009.http://www.twirpx.com/file/942288/
2. Левитин Ананий В. Алгоритмы: введение в разработку и анализ. - М.: Издательский дом «Вильямс», 2006.http://progbook.ru/algoritmy/1159-levitin-algoritmy-vvedenie-v-razrabotku-i-analiz.html
3. Ху Т.Ч., Шинг М.Т. Комбинаторные алгоритмы. – Н.Новгород: Изд-во Нижегородского государственного университета, 2004.http://bookre.org/reader?file=757445
4. Коварцев А.Н. Курс лекций Алгоритмы и анализ сложности, 2009 -

http://gendocs.ru/v10424/%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B8_%D0%BF%D0%BE_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0%D0%BC_%D0%B8_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7%D1%83_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8
Дополнительная литература:

Дональд Э. Кнут. Искусство программирования. Том 1. -М. Издательский дом «Вильямс», 2005.
Дональд Э. Кнут. Искусство программирования. Том 2. -М. Издательский дом «Вильямс», 2005.
Дональд Э. Кнут. Искусство программирования. Том 3. -М. Издательский дом «Вильямс», 2005.
Красиков И.В., Красикова И.Е. Алгоритмы: как дважды два. - М.: Эксмо, 2006.

Дополнительная литература 2
1. А.А.Марков Теория алгорифмов М.Л. Изд-во АН СССР, 1954,

374с., 1984, 432 с.
2. А.Ахо, Дж.Хопкрофт, Дж.Ульман. Построение и анализ

вычислительных алгоритмов. М. Мир, 1979. 536 с.
3. Проблемы математической логики (сб.). Под ред. Козмидиади и

др. М. Мир 1970, 432 с.
4. Э.Мендельсон. Введение в математическую логику. (Гл. 5.) M.

1971, 1976, 1984. 320 с.
5. С.К.Клини. Математическая логика. (Гл. V). М. Мир, 1973.

480с.
6. Ю.Л.Ершов, Е.А.Палютин. Математическая логика. (Гл. 7). М.

"Наука" 1971. 320 с.
7. Р.Смальян. Теория формальных систем. (Гл. I, II.) М. Наука,

1981, 207 с.
8. Дж.Шенфилд. Математическая логика. (Гл. 6-7.) М. Наука, 1975.

527 с.
9. С.К.Клини. Введение в метаматематику. М "Иностраниздат",

1957, 526 с.
10. Н.Верещагин, А.Шень. Лекции по математической логике и

теории алгоритмов. Ч 3. Вычислимые функции. M. МЦНМО 1999.

126с.
11. К.А.Гоуд. Доказательства как описания вычислений. В кн.

"Математическая логика в программировании". Под ред.

М.В.Захарьящева и Ю.И.Янова. М. 1991. С. 311-330. (407 с.)
12. А.И.Мальцев Алгоритмы и рекурсивные функции. М Наука 1986.

357с.
13. В.Г.Карпов, В.А.Мощенский Математическая логика и дискретная

математика, Минск "Высшая школа", 1977. 254 с.
14. А.Н.Колмогоров, Драгалин Математическая логика,

дополнительные главы, М МГУ, 1984. 120 с.
15. А.Н.Колмогоров, Драгалин Введение в математическую логику,

М. МГУ. 1982.
16. Н.К.Косовский Основы теории элементарных алгоритмов, Л. ЛГУ,

1987. 132 с.
17. С.Л.Эдельман Математическая логика, М. Высшая школа. 1975.

176с.
18. Дж.Булос,Р.Джефри. Вычислимость и логика, М. Мир. 1994.

396с.

Дополнительная литература3
19. Математическая логика. Под ред. А.А.Столяра. Гл. А.4, Б.3. М.

1971.
20. Б.А.Трахтенброт. Алгоритмы и вычислительные автоматы. М.1974.
21. В.А.Успенский, А.Л.Семенов Теория Алгоритмов: основные

открытия и приложения. М., "Н", 1987.
22. Г.Д.Эббинхауз, К.Якобс, Ф.-К.Ман, Г.Хермес Машины Тьюринга и

рекурсивные функции. М.1972
23. Х.Роджерс Теория рекурсивных функций и эффективная

вычислимость, М.1972
24. В.К.Иложарский Математическая логика и алгоритмы, 1970

1 2 3 4 5

	Радиофизический факультет Дисциплина «Алгоритмы и анализ сложности» относится к дисциплинам базовой части профессионального цикла основной образовательной...		Рабочая программа дисциплины «Алгоритмы и процессоры цифровой обработки сигналов» ...
	Рабочая программа дисциплины «экономический анализ» Рабочая программа предназначена для преподавания общепрофессиональной дисциплины федерального компонента опд. Ф. 06 «Экономический...		Рабочая программа дисциплины «финансовый анализ» Рабочая программа предназначена для преподавания специальной дисциплины вузовского компонента студентам заочной формы обучения (сокращенный...
	Рабочая программа Наименование дисциплины Охватывают основные сведения по данной дисциплине. Варианты сбалансированы по сложности и равноценны по трудоемкости		Рабочая программа дисциплины «инвестиционный анализ» Рабочая программа предназначена для преподавания специальной дисциплины вузовского компонента студентам очной и заочной форм обучения...
	Реферат по информатике и икт по теме: «Алгоритмы» Я выбрал тему учебно-методического комплекса «Алгоритмы», так как она является одной из главной тем в информатике		Реферат по информатике и икт по теме: “ Разветвляющиеся алгоритмы” Я выбрал тему: «Разветвляющиеся алгоритмы», потому что они очень часто применяются в алгоритмизации и программировании. Без знания...
	Программа по формированию навыков безопасного поведения на дорогах... Иметь представление об алгоритмах, свойствах алгоритмов и записи алгоритмов. Приводить примеры алгоритмов из жизни. Применять готовые...		Урока Тема урока Количество часов «Зарождение и предмет кибернетики», «Компьютер и управление», «Управление и алгоритмы», «Линейные алгоритмы управления без обратной...
	Рабочая программа дисциплины «Иностранный язык» Рабочая программа предназначена для преподавания дисциплины специальности 080109. 65 "Бухгалтерский учет, анализ и аудит" в 1- 4...		Рабочая программа дисциплины «Иностранный язык» Рабочая программа предназначена для преподавания дисциплины специальности 080109. 65 "Бухгалтерский учет, анализ и аудит" в 1- 4...
	Рабочая программа дисциплины «Иностранный язык» Рабочая программа предназначена для преподавания дисциплины специальности 080109. 65 "Бухгалтерский учет, анализ и аудит" в 1- 4...		Рабочая программа дисциплины «информатика» Рабочая программа предназначена для преподавания общематематической и естественнонаучной дисциплины студентам очной формы обучения...
	Рабочая программа по дисциплине В. В экономический анализ Целью освоения дисциплины «Экономический анализ» является изучение теоретических основ и приобретение студентами практических навыков...		Еще с девятого класса мы изучаем алгоритмы. И вот перейдя из десятого... Целью нашей работы является раскрыть, что такое алгоритмы, их виды и назначения, в чем заключается смысл работы с алгоритмом

Рабочая программа дисциплины «Алгоритмы и анализ сложности»

Похожие: