МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ВЛАДИВОСТОКСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ЭКОНОМИКИ И СЕРВИСА
КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И СИСТЕМ
АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ
Рабочая программа дисциплины
по направлению подготовки
11.03.02 Инфокоммуникационные технологии и системы связи
Владивосток 2017
Рабочая программа дисциплины «Алгоритмизация и программирование» составлена в соответствии с требованиями ФГОС ВО по направлению подготовки 11.03.02 «Инфокоммуникационные технологии и системы связи» и «Порядком организации и осуществления образовательной деятельности по образовательным программам высшего образования – программам бакалавриата, программам специалитета, программам магистратуры» (утв. приказом Минобрнауки России от 01.01.01 г. № 000)
Составитель:
, к. х.н., доцент кафедры информационных технологий и систем,
boris. *****@***ru
Утверждена на заседании кафедры ИТС от 01.01.2001 г., протокол № 8
Заведующий кафедрой (разработчика) _____________________
подпись фамилия, инициалы
«____»_______________2017 г.
Заведующий кафедрой (выпускающей) _____________________ _________________
подпись фамилия, инициалы
«____»_______________2017 г.
1 Цель и задачи освоения дисциплины
Целями освоения дисциплины «Алгоритмизация и программирование» являются:
Знакомство обучающих с основными принципами разработки алгоритмов и их программной реализации на процедурных языках высокого уровня, приобретение навыков в разработке абстрактных типов данных и алгоритмов для выполнения операций над ними. В качестве основного языка выбран язык Си, поскольку на нем хорошо реализуются основные структуры данных. Приобретение знаний и умений в разработке алгоритмов работы с типовыми структурами данных, владения языком программирования Си в такой степени, чтобы решать задачи обработки любых видов информации. Овладение способами оптимизации программного кода, компиляции и компоновки программных модулей, оценки асимптотического поведения алгоритмов и определения времени выполнения отдельных фрагментов программы. Получения сведений о современных направлениях в алгоритмизации, источниках информации, основных стратегиях, применяемых в алгоритмах.Задачи освоения дисциплины состоят: в формировании компетенции, позволяющей решать стандартные задачи составления и анализа алгоритмов, их реализации и применения в задачах обработки информации.
2 Перечень планируемых результатов обучения по дисциплине, соотнесенных с планируемыми результатами освоения образовательной программы
Планируемыми результатами обучения по дисциплине, являются знания, умения, навыки и/или опыт деятельности, характеризующие этапы/уровни формирования компетенций и обеспечивающие достижение планируемых результатов освоения образовательной программы в целом. Перечень компетенций, формируемых в результате изучения дисциплины, приведен в таблице 1.
Таблица 1 – Формируемые компетенции
Название ОПОП ВО (сокращенное название) | Компетенции | Название компетенции | Составляющие компетенции | |
11.03.02 «Инфокоммуникационные технологии и системы связи» | ОПК-3 | способностью владеть основными методами, способами и средствами получения, хранения, переработки информации | Знания: | принципов разработки алгоритмов и их программной реализации |
Умения: | осуществлять программную реализацию алгоритмов | |||
Навыки: | владения способами разработки и использования алгоритмов работы с различными типами данных |
3 Место дисциплины в структуре основной образовательной программы
Отнесение дисциплины к базовой части ОПОП определяется спецификой и миссией ВГУЭС, а также особенностями взаимодействия ВГУЭС с рынком труда и региональными требованиями, выраженными в результатах образования и компетенциях.
Входными требованиями необходимыми к освоению дисциплины «Алгоритмизация и программирование» является наличие у обучающихся компетенций, сформированных при изучении основ информатики, при прохождении модульного курса «программирования на языке Си».
На данную дисциплину «Алгоритмизация и программирование» опираются дисциплины, связанные с применением полученных знаний, такие как «Технология программирования», «Операционные системы», «Архитектура вычислительных машин», курсовое и дипломное проектирование.
4. Объем дисциплины
Объем дисциплины в зачетных единицах с указанием количества академических часов, выделенных на контактную работу с обучающимися (по видам учебных занятий) и на самостоятельную работу по всем формам обучения, приведен в таблице 2.
Название ОПОП | Форма обучения | Цикл | Семестр курс | Трудоем-кость | Объем контактной работы (час) | СРС | Форма аттестации | |||||
(З. Е.) | Всего | Аудиторная | Внеаудитор- ная | |||||||||
лек. | прак. | лаб. | ПА | КСР | ||||||||
Б-ИК | ОФО | Бл1.В | 2 | 4 | 77 | 17 | 17 | 34 | 9 | – | 67 | Э |
Таблица 2 – Общая трудоемкость дисциплины
5 Структура и содержание дисциплины
5.1 Структура дисциплины
Тематический план, отражающий содержание дисциплины (перечень разделов и тем), структурированное по видам учебных занятий с указанием их объемов в соответствии с учебным планом, приведен в таблице 3.
Таблица 3 – Структура дисциплины
№ | Название темы | Вид занятия | Объем час | Кол-во часов в интерактивной и электронной форме | СРС |
1 | 2 | 3 | 4 | 5 | 6 |
1 | Основные свойства алгоритмов и размещения данных и конструкций программы в памяти | Лекция | 2 | ||
Практическое занятие | 2 | 1 | 1 | ||
Лабораторная работа | 4 | 4 | 10 | ||
2 | Понятие об эффективности алгоритма и программы, оптимизация размещения объектов в памяти. O - символика. Пример на алгоритмах сортировки | Лекция | 2 | 1 | |
Практическое занятие | 2 | ||||
Лабораторная работа | 6 | 6 | 10 | ||
3 | Линейные списки. | Лекция | 2 | 1 | |
Практическое занятие | 2 | 1 | |||
Лабораторная работа | 6 | 4 | 10 | ||
4 | Вычисление выражений | Лекция | 2 | ||
Практическое занятие | 2 | ||||
Лабораторная работа | 6 | 6 | 8 | ||
5 | Двоичные деревья | Лекция | 2 | ||
Практическое занятие | 2 | ||||
Лабораторная работа | 6 | 6 | 8 | ||
6 | Алгоритмы на графах | Лекция | 2 | 1 | |
Практическое занятие | 2 | ||||
Лабораторная работа | 4 | 4 | 8 | ||
7 | Алгоритмы компьютерной геометрии | Лекция | 3 | ||
Практическое занятие | 3 | ||||
Лабораторная работа | 6 | 6 | 8 | ||
8 | Алгоритмы обработки данных | Лекция | 2 | ||
Практическое занятие | 2 | 1 | |||
Лабораторная работа |
5.2 Содержание дисциплины
Тема 1 Основные свойства алгоритмов и размещение данных и конструкций программы в памяти
Содержание темы: Простые переменные и массивы. Объявление, синтаксис и семантика использования простых переменных, указателей и переменных с индексами. Вычисление адреса объекта в памяти. Процесс компиляции, ключи компилятора и компоновщика. Настройка интегрированных сред разработки. Основные свойства алгоритма, отличия алгоритма от программы. Примеры алгоритмов. Основные стратегии, используемые в алгоритмах: жадная, «разделяй и властвуй», «грубой силы», динамическое программирование. Арифметические и логические операции над переменными. Получение доступа к отдельным двоичным разрядам.
Литература по теме: [4,6,11,9]
Формы и методы проведения занятий по теме: Лекция — 2 ч., практические занятия — 4 часа, лабораторная работа №1a. Реализовать в виде программы: а) Алгоритм преобразования русского текста (кодировка cp1251/cp866/koi8-r) в «транслит» (4 часа).
Форма текущего контроля: выполненная лабораторная.
Виды самостоятельной подготовки студентов по теме: поиск в интернете и анализ таблиц кодировки.
Тема 2. Понятие об эффективности алгоритма и программы, оптимизация размещения объектов в памяти. O - символика. Пример на алгоритмах сортировки.
Содержание темы: Размещение переменных в оперативной памяти, занимаемый объем, классы памяти. Дополнительные спецификаторы unsigned, const, register, static, auto, extern, volatile, их использование. Структуры и объединения. Обращение к записям в структуре. Алгоритмы сжатия информации на основе битовых карт. O-символика. Алгоритмы сортировки с оценками O(N), O(N2), O(NlogN). Алгоритмы поиска в сортированных и не-сортированных массивах.
Литература по теме: [4,6,11]
Формы и методы проведения занятий по теме: Лекция — 2 ч., практические занятия — 2 часа, лабораторная работа №1b. Реализовать в виде программы б) Алгоритм преобразования из «транслита» в koi8-r/cp1251/cp866 (4 часа).
Форма текущего контроля: выполненная лабораторная.
Виды самостоятельной подготовки студентов по теме: поиск в интернете и анализ таблиц кодировок. Изучение утилит определения кодировки и преобразования кодировок — enca и iconv.
Тема 3. Линейные списки.
Содержание темы: Структуры со ссылками на себя. Линейные списки. Виды линейных списков, области применения в практике программирования. Основные операции над линейными списками. Поиск в списке и в массиве. Алгоритмы поиска: линейный, методом дихотомии, с использованием хэш-функций.
Литература по теме: [4,5,6,12,13]
Формы и методы проведения занятий по теме: Лекция — 2 ч., практические занятия — 2 часа, лабораторная работа №2 - Составление частотного словаря текста с использованием массива. Реализовать алгоритм и программу, выполняющую чтение текстового файла и заполняющую массив структур; каждое прочитанное из файла слово ищется в уже (частично) заполненном массиве, в случае присутствия — увеличивается на 1 счетчик count, при отсутствии — слово добавляется в массив. Различные словоформы считаются разными словами. Словом считается непустая последовательность букв, не содержащая знаков препинания, цифр и специальных символов, ограниченная пробельными символами (пробел, табуляция, переход на новую строку). После завершения чтения файла — отсортировать массив слов по алфавиту, вывести результат в файл. (6 часов).
Форма текущего контроля: выполненная лабораторная.
Виды самостоятельной подготовки студентов по теме: изучить справочные данные о функции qsort.
Тема 4. Вычисление выражений.
Содержание темы:
Понятие об постфиксной и префиксной польской записи. Использование линейных списков для получения постфиксной польской записи. Использование вычислительного стека для получения значения польской записи.
Литература по теме: [4,5,9]
Формы и методы проведения занятий по теме: Лекция — 2 ч., практические занятия — 2 часа, лабораторная работа №3 - Телефонная книжка с использованием линейного списка.
При помощи линейных списков реализовать приложение, позволяющее поддерживать список контактов, содержащих номер телефона (число), имя абонента (строка текста до 128 символов) и дополнительные данные (строка текста до 256 символов). Данные записаны в файле, при запуске приложения загружаются о память в виде линейного списка, при закрытии приложения — записываются в файл, если были сделаны изменения в данных. (6 часов).
Форма текущего контроля: выполненная лабораторная.
Виды самостоятельной подготовки студентов по теме: поиск в интернете и анализ алгоритмов нечеткого поиска.
Тема 5 Двоичные деревья.
Определение деревьев. Виды деревьев. Структура, описывающая узел. Применение деревьев в программировании. Алгоритмы работы с деревом: добавление узла, удаление узла, достижение баланса. Алгоритм Хаффмана.
Содержание темы:
Литература по теме: [4,5,7,8]
Формы и методы проведения занятий по теме: Лекция — 2 ч., практические занятия — 4 часа, лабораторная работа №4. Частотный словарь с использованием двоичного дерева. При помощи двоичных деревьев реализовать приложение, позволяющее поддерживать список контактов, содержащих номер телефона (число), имя абонента (строка текста до 128 символов) и дополнительные данные (строка текста до 256 символов). Данные записаны в файле, при запуске приложения загружаются о память в виде сортированного двоичного дерева, при закрытии приложения — записываются в файл, если были сделаны изменения в данных. (6 часов)
Форма текущего контроля: выполненная лабораторная.
Виды самостоятельной подготовки студентов по теме: поиск в интернете и анализ таблиц кодировки.
Тема 6 Алгоритмы на графах
Содержание темы: Понятие графа, основные используемые термины. Представление графа в программе. Матрицы смежности и инцидентности. Алгоритмы прохождения графа в ширину и в глубину. Применение метода динамического программирования для нахождения критического пути на графе.
Литература по теме: [5,8,12,13]
Формы и методы проведения занятий по теме: Лекция — 2 ч., практические занятия — 4 часа, лабораторная работа №5. Нахождение пути в лабиринте поиском сначала в ширину (BFS) (6 часов)
Форма текущего контроля: выполненная лабораторная.
Виды самостоятельной подготовки студентов по теме: поиск в интернете и анализ алгоритмов прохождения лабиринтов.
Тема 7 Алгоритмы компьютерной геометрии
Содержание темы: Алгоритмы компьютерной геометрии. Основные структуры данных для описания объектов геометрии на плоскости и в пространстве. Алгоритмы вычисления периметра и площади произвольного многоугольника. Габаритный, лучевой и др. тесты нахождения точки в многоугольнике, пересечения двух отрезков, пересечения многоугольников. Оценка их временной сложности. Преобразования на плоскости и в пространстве: перенос, поворот, масштабирование и проекция. Алгоритмы построения выпуклых оболочек. Триангуляция по Делоне. Основные алгоритмы.
Литература по теме: [8,10,12,13].
Формы и методы проведения занятий по теме: Лекция — 3 ч., практические занятия — 3 часа, лабораторная работа №6 - Построить с помощью предложенного алгоритма (QuickHull, Грехема, GiftWrapping) выпуклую оболочку и вывести номера точек, в нее входящие. Обосновать асимптотическую оценку алгоритма, найти времена выполнения для среднего и худшего случая. (6 часов)
Форма текущего контроля: выполненная лабораторная.
Виды самостоятельной подготовки студентов по теме: поиск в интернете и выбор адекватного алгоритма построения выпуклой оболочки на плоскости.
Тема 8 Алгоритмы обработки данных
Содержание темы: Алгоритмы обработки экспериментальных данных: замечания о природе данных, получаемых путем измерений, применимость операций сглаживания, аппроксимации и интерполяции одномерных и двухмерных наборов данных. Операторы типа свертки. Обратная задача и способы регуляризации некорректных задач.
Литература по теме: [8,12,13].
Формы и методы проведения занятий по теме: Лекция — 2 ч., практические занятия — 2 часа.
Форма текущего контроля: обсуждение программной реализации методов решения обратных задач.
6. Методические указания для обучающихся по освоению дисциплины
В ходе изучения дисциплины «Алгоритмизация и программирование» студенты могут посещать аудиторные занятия (лекции, лабораторные занятия, практические занятия, консультации). Особенность изучения дисциплины «Алгоритмизация и программирование» состоит в необходимости освоения как теоретических основ, связанных с разработкой и применением алгоритмов в различных предметных областях, так и в приобретении практических навыков реализации алгоритмов при выполнении лабораторных заданий. Для выполнения работ рекомендуется использовать компилятор gcc и среду разработки geany в операционной системе Linux (или dev-cpp под Windows). Применение студентами более сложных сред допускается при наличии у них навыков работы. Иначе освоение среды будет отвлекать от задач дисциплины. Лабораторные работы проводятся в компьютерном классе со всем предустановленным программным обеспечением, для облегчения работы со справочной системой на компьютерах установлен словарь stardict с набором англо-русских словарей.
Особое место в овладении частью тем данной дисциплины может отводиться самостоятельной работе, при этом во время аудиторных занятий могут быть рассмотрены и проработаны наиболее важные и трудные вопросы по той или иной теме дисциплины, а второстепенные и более легкие вопросы, а также вопросы, специфичные для направления подготовки, могут быть изучены студентами самостоятельно. В частности, практическое кодирование и отладка стандартных процедур, может выполняться в виде домашнего задания, в том случае если на практических занятиях обсуждены все сложные и спорные моменты реализации.
В соответствии с учебным планом направления подготовки процесс изучения дисциплины может предусматривать проведение лекций, лабораторных занятий, консультаций, а также самостоятельную работу студентов. Обязательным является проведение лабораторных занятий в специализированных компьютерных аудиториях, оснащенных подключенными к центральному серверу терминалами или персональными компьютерами.
Ниже перечислены предназначенные для самостоятельного изучения студентами очной формы обучения те вопросы из лекционных тем, которые во время проведения аудиторных занятий изучаются недостаточно или изучение которых носит обзорный характер.
Тема 1. Алгоритмы работы с текстами в различных кодировках, реализация нечеткого поиска (metafont и/или Soundex с использованием русских кодировок).
Тема 2. Алгоритмы работы с отдельными двоичными разрядами. Установка бита в нужное значение, проверка значения заданного бита. Реализация при помощи функций и через макросы.
Тема 3. Алгоритмы сжатия информации. Алгоритмы на основе битовых карт, методы сжатия RLE и Хаффмана.
Результаты освоения теоретического материала, в том числе и самостоятельно осваиваемые, могут быть проверены при проведении письменной экспресс-проверки, а также в результате обсуждений на практических и лабораторных работах.
Ниже приведены рекомендации по работе с литературой:
При освоении особенностей языка программирования Си рекомендуется использовать классические учебники, созданные разработчиками языка [4,7].
Вопросы реализации конкретных алгоритмов можно найти как в бессмертном многотомном издании Кнута [5], так и в современных учебниках. В качестве последнего можно рекомендовать электронный ресурс, наиболее близкий к структуре данного курса[6].
В качестве вспомогательного материала можно использовать интернет-ресурсы, ориентированные на изучающих предмет и рассматривающие широкий круг прикладных алгоритмов[12,13].
7. Перечень учебно-методического обеспечения для самостоятельной работы
В процессе самостоятельной работы при изучении дисциплины студенты могут использовать в специализированных аудиториях терминалы, подключенные к центральному серверу, обеспечивающему доступ к современному программному обеспечению, необходимому для изучения дисциплины, а также доступ через локальную сеть университета к студенческому файловому серверу и через информационно-телекоммуникационную сеть «Интернет» к электронной образовательной среде и к хранилищу полнотекстовых материалов, где в электронном виде располагаются учебно-методические и раздаточные материалы, которые могут быть использованы для самостоятельной работы при изучении дисциплины.
8. Фонд оценочных средств для проведения промежуточной аттестации
В соответствии с требованиями ФГОС ВО для аттестации обучающихся на соответствие их персональных достижений планируемым результатам обучения по дисциплине созданы фонды оценочных средств (Приложение 1).
9. Перечень основной и дополнительной учебной литературы, необходимой для освоения дисциплины
а) основная литература
Кузин на языке С / , - М.: Форум, НИЦ ИНФРА-М, 2015. - 144 с.[Электронный ресурс] Режим доступа: http:///bookread2.php? book=505194 Царев на языке Си: учеб. пособие / . – Красноярск: Сиб. федер. ун-т, 2014. – 108 с.
[Электронный ресурс] Режим доступа: http:///bookread2.php? book=510946 Немцова на языке С++: Учебное пособие / , , ; Под ред. . - М.: ИД ФОРУМ: ИНФРА-М, 2012. - 512 с.
[Электронный ресурс] Режим доступа: http:///bookread2.php? book=244875
б) дополнительная литература
Язык программирования Си. М., Вильямс, 2015, 304 с. Возможно использование предыдущих изданий и изданий других издательств, имеющихся в библиотеке. Кнут программирования. Том 1. Основные алгоритмы. М., Вильямс, 2015, 720 с.; Кнут программирования. Том 3. Сортировка и поиск. М., Вильямс, 2012, 824 с. Возможно использование предыдущих изданий и изданий других издательств. , , Катаева . Введение в язык программирования С++, М., ИНТУИТ, 2016, 197 с. ( есть электронный вариант: http://www. intuit. ru/goods_store/ebooks/9787, также в сетевой библиотеке Genesis и в локальной сети ВГУЭС — ftp:///pub/Алгоритмизация и программирование/КНИГИ/ , , -Алгоритмизация. Введение в язык программирования С++.pdf). Брайан Керниган, Деннис Ритчи, Алан Фьюэр. Язык программирования Си. Задачи по языку Си. М., Финансы и статистика, 1985, 279 с. ундаментальные алгоритмы на C. Части 1-5. Спб, ДиаСофтЮП, 2003, 1136 с. етоды программирования, тт.1,2. М., Мир, 1982. лгоритмические основы машинной графики. М., Мир, 1989, 512 с.10. Перечень ресурсов информационно-телекоммуникационной сети «Интернет»
а) полнотекстовые базы данных
http://www. intuit. ru/studies — электронные курсы для дистанционного обучения.б) интернет-ресурсы
http://www. alglib-chat. ru http://algolist. manual. ru http://kpolyakov. spb. ru/download/devcpp_1.pdf (также devcpp_(2,3,4).pdf) — начальный курс программирования на языке Си.11. Перечень информационных технологий
Для проведения лекционных и лабораторных занятий рекомендуется использовать программное обеспечение: операционная система Linux с ядром 3, 4 версий и выше, пакет Libreoffice 5.1 и выше, обслуживающие программы и среды разработки программ по выбору преподавателей (см. далее в п.13). Задания к лабораторным работам, методические и вспомогательные материалы размещаются на файловом сервере с общим доступом перед проведением работ.
12. Электронная поддержка дисциплины
При изучении дисциплины для проработки всех тем и выполнения заданий по всем темам студенты могут использовать различные учебно-методические материалы, размещаемые в электронном виде преподавателями на файловом сервере, в хранилище полнотекстовых материалов, а также в электронной образовательной среде, которая предполагает также возможность обмена информацией с преподавателем для подготовки заданий. Доступ студентов к файловому серверу, хранилищу полнотекстовых материалов, электронной образовательной среде осуществляется с использованием с использованием учетных записей студентов.
13. Материально-техническое обеспечение дисциплины
Для проведения лекций по дисциплине используются специализированные аудитории
с мультимедийным оборудованием или с возможностями подключения к такому оборудованию, позволяющему демонстрировать на большом экране приемы работы со средой разработки, компиляторами и другой лекционный материал (технические характеристики компьютера, входящего в состав мультимедийного оборудования или используемого совместно с таким оборудованием, должны обеспечивать возможность работы с современными версиями операционной системы Linux, пакета LibreOffice, обслуживающих, прикладных программ и другого, в том числе и сетевого программного обеспечения).
Для проведения практических, лабораторных занятий по дисциплине и для самостоятельной работы студентов используются специализированные аудитории, оснащенные персональными компьютерами, подключенными к корпоративной сети, обеспечивающей доступ к файловым серверам и службам, позволяющим при проведении лабораторных занятий использовать современное программное обеспечение, операционную систему Linux (Mint, OpenSuSE, Ubuntu), пакет LibreOffice 5.1 и выше, а также обслуживающие программы и среды разработки программ по выбору преподавателей (Kdevelop, Qtdesigner, geany, Netbeans, Eclipse). Должна быть предусмотрена возможность использования грифельной доски и проектора для демонстрации приемов работы и обсуждения различных алгоритмических решений.
