Программа дисциплины «Построение и анализ алгоритмов»
Скачать 183.84 Kb.
|
 НИУ ВШЭ – Нижний Новгород Программа дисциплины «Построение и анализ алгоритмов» для направления 231000.62 – Программная инженерия подготовки бакалавра Правительство Российской Федерации Нижегородский филиал Федерального государственного автономного образовательного учреждения высшего профессионального образования "Национальный исследовательский университет "Высшая школа экономики" Факультет бизнес-информатики и прикладной математики Программа дисциплины «Построение и анализ алгоритмов» для направления 231000.62 – Программная инженерия подготовки бакалавра Автор программы: доцент Тимофеева О.П. Одобрена на заседании кафедры «Базовая кафедра МЕРА» «___»____________ 2013г. Зав. кафедрой Н.И.Кащеев Рекомендована секцией УМС «Прикладная математика и информатика» «___»____________ 2013г. Председатель В.А. Калягин Утверждена УМС НИУ ВШЭ – Нижний Новгород «___»_____________2013 г. Председатель В.М. Бухаров Нижний Новгород, 2013 г. Область применения и нормативные ссылкиНастоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направлений подготовки 231000.62 «Программная инженерия» подготовки бакалавра, изучающих дисциплину «Построение и анализ алгоритмов». Программа разработана в соответствии с образовательным стандартом федерального государственного образовательного автономного учреждения высшего профессионального образования Высшей школы экономики, рабочим учебным планом университета по направлению подготовки 231000.62 «Программная инженерия», утвержденным в 2013г. Цели освоения дисциплиныЦелями освоения данной дисциплины являются как получение теоретических знаний в области организации структур данных и базовых вычислительных алгоритмов, так и практические навыки анализа алгоритмов, составления программ на языках Си и Scheme. Компетенции обучающегося, формируемые в результате освоения дисциплиныВ результате освоения дисциплины студент должен: знать основные структуры данных (массив, список, дерево), базовые алгоритмы (сортировку, группировку, инвертирование) развить «программистское» мышление овладеть навыками программирования на языках Scheme и C в плане реализации основных вычислительных алгоритмов и организации структур данных В результате освоения дисциплины студент осваивает следующие компетенции:
Место дисциплины в структуре образовательной программыНастоящая дисциплина относится к базовой части математического и естественнонаучного цикла, обеспечивающего подготовку бакалавра. Дисциплина опирается на следующие дисциплины «Дискретная математика», «Программирование». Курс играет важную роль в развитии понимания будущими специалистами низкоуровневого программирования и функционирования компьютерной системы. Тематический план учебной дисциплины
Формы контроля знаний студентов
Критерии оценки знаний, навыковТекущий контроль осуществляется в виде проверки выполнения практических работ. По каждой работе оформляется электронный отчёт с описанием хода выполнения заданий, обоснованием результатов и выводами. Итоговый контроль: экзамен на последней неделе. Учитываются результаты домашней работы (отчёты по практикам). Оценка определяется в соответствии с п. 10. Контрольная работа содержит задачу в виде двух программ на языке scheme. Cтудент должен представить решение в электронном виде, включая текст программ и числовые ответы. Порядок формирования оценок по дисциплинеКонтроль знаний студентов включает формы текущего и итогового контроля. Текущий контроль осуществляется в течение трех модулей. В рамках учебного курса предусмотрены различные формы текущего контроля знаний и работы студентов на практических занятиях: практические задания (после каждого практического занятия, каждое по 80 минут), реферат по заранее выбранной и согласованной с преподавателем теме. Работа над рефератом ведется на протяжении 4 недель в течение 3 модуля. Каждая форма текущего контроля оценивается по 10-балльной шкале, оценка выставляется в рабочую ведомость преподавателя. По результатам текущего контроля организуются индивидуальные консультации в рамках второй половины рабочего дня преподавателя. Формы итогового контроля – экзамен по окончании третьего модуля. Каждая форма итогового контроля оценивается так же по 10-балльной шкале Практическое задание: оценка в 10 баллов проставляется в исключительных случаях самостоятельно проведенной работы, результаты которой могут в дальнейшем использоваться в учебном процессе или в исследовательской работе студента; оценка в 8-9 баллов проставляется при самостоятельно разработанном или удачно адаптированном и отлично представленном исследовании по выбранной тематике; оценка в 6-7 баллов проставляется при своевременно выполненном и самостоятельно представленном исследовании по выбранной тематике; оценка в 4-5 баллов проставляется при частичном, несамостоятельном участии в выполнении работ над заданием; оценка в 2-3 балла проставляется, когда студент не может самостоятельно представить работу или когда работа носит явные признаки заимствований (работу предлагается переделать); оценка в 1 балл проставляется при наличии каких-либо демонстративных проявлений безграмотности и неэтичного отношения к работе. Зачет или экзамен: На зачете (экзамене), представляющем собой письменные ответы на вопросы и решение задачи с последующим собеседованием, оценка проставляется следующим образом: высшая оценка в 9 баллов (10 баллов только в исключительных случаях) проставляется при отличном выполнении заданий (полных, с примерами и возможными обобщениями ответах на вопросы, при правильном решении задачи и детальном ее представлении); почти отличная оценка в 8 баллов проставляется при полностью правильных ответах на вопросы и решении задачи, но при отсутствии примеров и обобщений, а также детального представления решаемой задачи; оценка в 7 баллов проставляется при правильных ответах на вопросы и правильном решении задачи, но при отсутствии пояснений и обобщений, а также детального представления решаемой задачи; оценка в 6 баллов проставляется при наличии отдельных неточностей в ответах на вопросы или неточностях в решении задачи непринципиального характера (описки и случайные ошибки); оценка в 4-5 баллов проставляется в случаях, когда в ответах на вопросы и в решении задачи имеются существенные неточности и ошибки, свидетельствующие о недостаточном понимании изучаемой дисциплины; оценка в 2-3 балла проставляется при наличии лишь отдельных положительных моментов в ответах на вопросы и в решении задачи; оценка в 1 балл проставляется в тех случаях, когда наряду с неправильными ответами на вопросы и решением задачи имеют место какие-либо демонстративные проявления безграмотности или неэтичное отношение к изучаемой дисциплине. По результатам устного собеседования с преподавателем возможны корректировки оценки в ту или иную сторону. Накопленная оценка за текущий контроль учитывает результаты студента следующим образом: Онакопленная = 0,5* Отекущая +0,5*Оаудитор. где Отекущая= 0,5*Ореферат + 0,5*Од/з Способ округления накопленной оценки – арифметический. Результирующая оценка за дисциплину рассчитывается по формуле: Орезульт = 0,6*Онакопленная + 0,4*Оэкз В диплом выставляет результирующая оценка по учебной дисциплине. Способ округления результирующей оценки по учебной дисциплине – арифметический. Полученные после округления этих величин до целого значения и выставляются как результирующие оценки по 10-балльной шкале. Содержание дисциплиныГлава 1. АЛГОРИТМЫ И ИХ СВОЙСТВА Тема 1.1. Понятие и свойство алгоритма. Способы записи алгоритма. Классы алгоритмов Определение понятия «алгоритм». Основные свойства алгоритма. Способы записи алгоритмов, их «плюсы» и «минусы». Математическое определение алгоритма (по Колмогорову). Классы алгоритмов. Классификация алгоритмов по прикладным областям. Основная литература Кормен Т.,Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание – М.: Вильямс, 2006. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2000 Дополнительная литература Серджвик Р. Фундаментальные алгоритмы на С.Часть 1-3 СПб: Диасофт, 2003. Тема 1.2. Сложность алгоритмов. Классы алгоритмов по сложности P и NP Понятие сложности алгоритма. Оценки сложности. Классификация алгоритмов по сложности. Понятие Машины Тьюринга. Классы сложности задач: P,NP. Задача комивояжёра. Основная литература Кормен Т.,Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание – М.: Вильямс, 2006. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2000 Дополнительная литература Серджвик Р. Фундаментальные алгоритмы на С.Часть 1-3 СПб: Диасофт, 2003. Глава 2. ОСНОВЫ ПРОГРАММИРОВАНИЯ НА ЯЗЫКЕ SCHEME Тема 2.1. Введение в Lisp-подобные языки. Среда программирования DrScheme (DrRacket) Язык scheme и его исторические корни. Отличие scheme от традиционных императивных языков. Основные реализации языка scheme. Среда разработки DRScheme (DrRacket). REPL и его использование в DrScheme. Основная литература Абельсон Х., Сассман Д. Структура и интерпретация компьютерных программ. М.: Добросвет, 2006 Майлингова О., Манжелей С., Соколовская Л. Прототипирование программ на языке scheme. – М.: МГУ, 2001. Дополнительная литература Harvey B., Wright M. Simply Scheme: introducing computer science. – MIT, 1993 Тема 2.2. Выражения языка scheme. Комбинации и порядок вычислений. Классификация выражений в языке scheme. Примитивные выражение, комбинации, специальные формы. Нормальный и аппликативный порядок вычислений. Основная литература Абельсон Х., Сассман Д. Структура и интерпретация компьютерных программ. М.: Добросвет, 2006 Майлингова О., Манжелей С., Соколовская Л. Прототипирование программ на языке scheme. – М.: МГУ, 2001. Дополнительная литература Harvey B., Wright M. Simply Scheme: introducing computer science. – MIT, 1993 Тема 2.3. Основные структуры данных scheme: точечная пара, список, вектор, строка Типы данных Scheme: целые, вещественные, рациональные, символьные, строковые. Точечные пары и списки. Обращения к элементам списков. Векторы и строки. Основные операции над векторами и строками. Основная литература Абельсон Х., Сассман Д. Структура и интерпретация компьютерных программ. М.: Добросвет, 2006 Майлингова О., Манжелей С., Соколовская Л. Прототипирование программ на языке scheme. – М.: МГУ, 2001. Дополнительная литература Harvey B., Wright M. Simply Scheme: introducing computer science. – MIT, 1993 Тема 2.4. Специальные формы языка scheme Понятие специальной формы. Форма define для связывания имён со значениями. Условные формы if, cond. Основная литература Абельсон Х., Сассман Д. Структура и интерпретация компьютерных программ. М.: Добросвет, 2006 Майлингова О., Манжелей С., Соколовская Л. Прототипирование программ на языке scheme. – М.: МГУ, 2001. Дополнительная литература Harvey B., Wright M. Simply Scheme: introducing computer science. – MIT, 1993 Тема 2.5. Разработка процедур на языке scheme. Именованные и безымянные (lambda) процедуры Специальная форма define для создания процедур. Именованные процедуры. Механизм безымянных lambda-функций. Процедуры высших порядков. Блочная структура программы. Рекурсия. Виды рекурсии. Окружения let и let*. Основная литература Абельсон Х., Сассман Д. Структура и интерпретация компьютерных программ. М.: Добросвет, 2006 Майлингова О., Манжелей С., Соколовская Л. Прототипирование программ на языке scheme. – М.: МГУ, 2001. Дополнительная литература Harvey B., Wright M. Simply Scheme: introducing computer science. – MIT, 1993 Глава 3. ОСНОВНЫЕ СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ Тема 3.1 Классификация основных структур данных. Абстрактные типы данных Попытка определения типа данных. Скалярные и векторные типы. Стандартные и производные типы. Понятие АТД – абстрактного типа данных. Основная литература Кормен Т.,Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание – М.: Вильямс, 2006. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2000 Дополнительная литература Серджвик Р. Фундаментальные алгоритмы на С.Часть 1-3 СПб: Диасофт, 2003. Тема 3.2 Простейшие алгоритмы на массивах Свойства массивов. Простейшие алгоритмы обработки массивов: суммирование элементов, нахождение минимального и максимального значений. Группировка элементов. Основная литература Кормен Т.,Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание – М.: Вильямс, 2006. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2000 Дополнительная литература Серджвик Р. Фундаментальные алгоритмы на С.Часть 1-3 СПб: Диасофт, 2003. Тема 3.3 Алгоритмы сортировки Понятие сортировки. Классификация методов сортировки. Обзор методов: нерациональная, вставками, выбором, пузырьковая. Быстрая сортировка и сортировка Шелла. Исследование методов сортировки. Основная литература Кормен Т.,Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание – М.: Вильямс, 2006. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2000 Дополнительная литература Серджвик Р. Фундаментальные алгоритмы на С.Часть 1-3 СПб: Диасофт, 2003. Тема 3.4 Связанные списки Преимущества и недостатки массивов. Связанные списки: классификация. Программная реализация списков. Основная литература Кормен Т.,Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание – М.: Вильямс, 2006. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2000 Дополнительная литература Серджвик Р. Фундаментальные алгоритмы на С.Часть 1-3 СПб: Диасофт, 2003. Тема 3.5 Деревья Структура данных дерево: преимущества и недостатки по сравнению со списками. Терминология и классификация деревьев. Бинарные деревья поиска. Сбалансированные деревья. Примеры использования деревьев. Основная литература Кормен Т.,Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание – М.: Вильямс, 2006. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2000 Дополнительная литература Серджвик Р. Фундаментальные алгоритмы на С.Часть 1-3 СПб: Диасофт, 2003. Тема 3.6 Сжатие с потерями и без Основные понятия теории информации. Энтропия и избыточность. Свойства энтропии. Классификация методов сжатия без потерь. Алгоритм Хаффмана и построение адаптивного кода. Строковые алгоритмы на примере LZW. Краткий обзор методов сжатия с потерями. Основная литература Кормен Т.,Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание – М.: Вильямс, 2006. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2000 Дополнительная литература Серджвик Р. Фундаментальные алгоритмы на С.Часть 1-3 СПб: Диасофт, 2003. Тема 3.7. Методы численного интегрирования Классификация методов численного интегрирования. Методы прямоугольников: левые, правые, серединные. Метод трапеций. Метод парабол (Симпсона). Основная литература Кормен Т.,Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание – М.: Вильямс, 2006. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2000 Дополнительная литература Серджвик Р. Фундаментальные алгоритмы на С.Часть 1-3 СПб: Диасофт, 2003. Образовательные технологииТрадиционное чтение лекций. Разбор практических задач. Методические рекомендации преподавателюТемы индивидуальных заданий для проведения практических занятий должны отличаться для каждого нового учебного года Методические указания студентамРекомендуется подготовка к каждому занятию по заданиям, озвученным преподавателем на предыдущем занятии. Для более глубокого усвоения курса предполагается использование студентами дополнительной литературы, работа в библиотеке, поиск информации в сети Интернет Оценочные средства для текущего контроля и аттестации студентаТематика практических заданий
Вопросы для оценки качества освоения дисциплиныПримерный перечень вопросов к промежуточному контролю для самопроверки студентов
Примеры заданий промежуточного /итогового контроляПрактические задания к зачёту: Задача 1. Написать программу, рассчитывающую сумму простых чисел, не превосходящих миллион. Задача 2. Написать программу, находящее максимальное число Фибоначчи в диапазоне от миллиона до двух. Учебно-методическое и информационное обеспечение дисциплиныОсновная литература: Кормен Т.,Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание – М.: Вильямс, 2006. Абельсон Х., Сассман Д. Структура и интерпретация компьютерных программ. М.: Добросвет, 2006 Дополнительная литература Серджвик Р. Фундаментальные алгоритмы на С.Часть 1-3 СПб: Диасофт, 2003. Harvey B., Wright M. Simply Scheme: introducing computer science. – MIT, 1993 Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2000 Майлингова О., Манжелей С., Соколовская Л. Прототипирование программ на языке scheme. – М.: МГУ, 2001. – Материально-техническое обеспечение дисциплиныМультимедийное оборудование – ноутбук, экран, проектор. Состав программного обеспечения:
Используется ПО в компьютерном классе НИИТ. В НИУ ВШЭ – Нижний Новгород студентам предоставляется возможность самостоятельной работы с электронными ресурсами информации, периодической литературой. В компьютерном классе (НИИТ) доступ on-line Автор программы, доцент Тимофеева О.П. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Добавить документ в свой блог или на сайт
Похожие:
 | Программа по формированию навыков безопасного поведения на дорогах... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 231000.... |  | Программа курса «Построение и анализ алгоритмов» Сертификаты и определение класса np. Полиномиальная сводимость и np-полные задачи. Примеры np-полных задач для графов, множеств,... |
| Программа по формированию навыков безопасного поведения на дорогах... Тема: Понятие алгоритмов, свойства алгоритма. Исполнители алгоритмов, система команд исполнителя. Способы записей алгоритмов. Формальное... | | Конспект урока на тему "Алгоритм. Свойства алгоритмов. Виды алгоритмов... ... |
| Программа по формированию навыков безопасного поведения на дорогах... Иметь представление об алгоритмах, свойствах алгоритмов и записи алгоритмов. Приводить примеры алгоритмов из жизни. Применять готовые... | | Урок по информатике по теме «Методика обучения сортировке одномерного массива» Образовательная: формирование у учащихся навыков составления алгоритмов сортировки массива методом прямого выбора и методом пузырька;... |
| Рабочая программа дисциплины «Алгоритмы и анализ сложности» Кроме того, изучение алгоритмов и сложности позволяет более глубоко вникнуть в задачу и может подсказать методы решения, не зависящие... | | План-конспект урока алгоритм. Свойства алгоритмов. Виды алгоритмов. Формы записи алгоритмов Преподавание алгебры в 7 классе ведётся по умк «Алгебра 7 класс» под редакцией А. Г. Мордковича. Учебное пособие для изучения курса... |
| Конспект по теме «Алгоритмы» Цель урока: дать учащимся понятие алгоритма, изучить свойства алгоритмов, применение алгоритмов в жизнедеятельности человека | | Урок 18 построение циркулем и линейкой. Примеры задач на построение цели Цели: дать представление о новом классе задач – построение геометрических фигур с помощью циркуля и линейки без масштабных делений... |
| Программа по формированию навыков безопасного поведения на дорогах... Урок 50. Анализ контрольной работы. Алгоритм — модель деятельности исполнителя алгоритмов | | Программа дисциплины теория алгоритмов красноярск 2006 Цель дисциплины – формирование представлений об алгоритмах в математике, алгоритмически разрешимых и неразрешимых проблемах |
| Типы алгоритмов. Алгоритмы с повторениями ... | | Рабочая программа дисциплины теория алгоритмов направление |
| Рабочая программа составлена в соответствии с требованиями фгос впо... Дёгтев А. Н. Теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов направления 010100. 62 – математика,... | | Рабочая программа составлена в соответствии с требованиями фгос впо... Дёгтев А. Н. Теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов направления 010200. 62 – математика... |
