МИНОБРНАУКИ РОССИИ
федеральное государственное бюджетное образовательное учреждение высшего образования
«Алтайский государственный университет»

Основы программирования
рабочая программа дисциплины

Закреплена за кафедройКафедра информатики
Направление подготовки02.03.01. Математика и компьютерные науки
Форма обученияОчная
Общая трудоемкость9 ЗЕТ
Учебный план02_03_01_МиКН-4-2020
Часов по учебному плану 324
в том числе:
аудиторные занятия 132
самостоятельная работа 165
контроль 27
Виды контроля по семестрам
экзамены: 2
зачеты: 1

Распределение часов по семестрам

Курс (семестр) 1 (1) 1 (2) Итого
Недель 19 19
Вид занятий УПРПДУПРПДУПРПД
Лекции 34 34 32 32 66 66
Лабораторные 34 34 32 32 66 66
Сам. работа 40 40 125 125 165 165
Часы на контроль 0 0 27 27 27 27
Итого 108 108 216 216 324 324

Программу составил(и):
старший преподаватель, Смолякова Лариса Ленгардовна

Рецензент(ы):
к.ф.-м.н., доцент, Пономорев И.В.

Рабочая программа дисциплины
Основы программирования

разработана в соответствии с ФГОС:
Федеральный государственный образовательный стандарт высшего образования по направлению подготовки 02.03.01 МАТЕМАТИКА И КОМПЬЮТЕРНЫЕ НАУКИ (уровень бакалавриата) (приказ Минобрнауки России от 07.08.2014 г. № 949)

составлена на основании учебного плана:
02.03.01 Математика и компьютерные науки
утвержденного учёным советом вуза от 30.06.2020 протокол № 6.

Рабочая программа одобрена на заседании кафедры
Кафедра информатики

Протокол от 30.06.2020 г. № 6
Срок действия программы: 2017-2021 уч. г.

Заведующий кафедрой
к.ф.-м.н., доцент Козлов Д.Ю.

Визирование РПД для исполнения в очередном учебном году

Рабочая программа пересмотрена, обсуждена и одобрена для
исполнения в 2020-2021 учебном году на заседании кафедры

Кафедра информатики

Протокол от 30.06.2020 г. № 6
Заведующий кафедрой к.ф.-м.н., доцент Козлов Д.Ю.

1. Цели освоения дисциплины

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

2. Место дисциплины в структуре ООП

Цикл (раздел) ООП: Б1.Б

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

ОПК-3: способностью к самостоятельной научно-исследовательской работе
В результате освоения дисциплины обучающийся должен
3.1.Знать:
3.1.1.о различных парадигмах программирования и современном уровне развития языков и технологий программирования;
о сложности программных систем и методах ее преодоления;
об основах построения трансляторов;
основные понятия в области алгоритмизации, свойства алгоритмов, методы анализа сложности алгоритмов;
синтаксис и базовые конструкции языков C и С++, основные возможности и приемы программирования на этих языках;
принципы структурного программирования;
назначение, устройство и свойства основных структур данных: список, очередь, стэк, дерево, граф;
эффективные алгоритмы поиска и сортировки, алгоритмы решения задач теории графов.

3.2.Уметь:
3.2.1.разрабатывать алгоритмы решения типичных задач и реализовывать их на языке С;
применять при решении алгоритмических задач типичные алгоритмы и структуры данных;
использовать для разработки и отладки программ современные интегрированные среды разработки.
3.3.Иметь навыки и (или) опыт деятельности (владеть):
3.3.1.приемами чтения, построения и записи алгоритмов;
навыками написания и отладки программ на высокоуровневом языке программирования в интегрированной среде разработки.

4. Структура и содержание дисциплины

Код занятия Наименование разделов и тем Вид занятия Семестр Часов Компетенции Литература
Раздел 1. Алгоритмизация
1.1. Алгоритмические языки программирования. Базовые алгоритмические структуры: cледование, ветвление, повторение. Алгоритмические языки программирования. Уровни языков программирования. Алфавит, синтаксис и семантика алгоритмических языков программирования. Инструменты и схема построения исполняемого модуля для программы на языке программирования высокого уровня. Интегрированные среды разработки. Лекции 1 1 Л2.1, Л1.1, Л1.2, Л1.4
1.2. Основы алгоритмизации. Исполнитель: среда, система команд исполнителя, отказы. Фон-неймановские принципы работы компьютеров. Алгоритм. Свойства алгоритма: понятность, дискретность, детерминированность, конечность, результативность, массовость. Формы записи алгоритмов: cловесно-пошаговая, графическая, в псевдокодах, на алгоритмических языках. Лекции 1 1 Л2.1, Л1.2, Л1.3
Раздел 2. Язык программирования Си
2.1. Общая характеристика языка Си. История и условия возникновения. Генеалогия языка Си. Базовые принципы и свойства языка Си. Простейшая программа. Лекции 1 2 Л1.1, Л1.3
2.2. Управляющие конструкции языка Си. Условный оператор. Оператор ветвления. Операторы циклов. Прерывание циклов. Инвариант цикла Лекции 1 2 Л1.1, Л1.4
2.3. Синтаксис языка Си. Алфавит, идентификаторы, ключевые слова. Комментарии. Типы, константы. Операции и выражения. Приоритет операций. Общая структура программы. Лекции 1 2 Л2.1, Л1.1, Л1.3
2.4. Функции. Параметры функций. Инвариантная функция. Рекурсия. Взаимосвязь итерации и рекурсии. Индуктивное вычисление функции на последовательности данных Лекции 1 2 Л2.1, Л1.2, Л1.3
2.5. Логическая и физическая структура программы. Структура программы, состоящей из нескольких файлов. Области видимости. Заголовочные файлы. Лекции 1 2 Л2.1, Л1.1
2.6. Скалярные переменные. Классы памяти переменных. Изменяемость переменных. Общая схема описания переменных. Лекции 1 2 Л1.1
2.7. Препроцессор. Назначение и роль препроцессора. Директивы препроцессора. Макроконстанты и макрофункции. Условная компиляция. Лекции 1 2 Л1.3
2.8. Массивы. Многомерные массивы. Массивы как параметры функций. Типичные операции над массивами. Лекции 1 2 Л1.3
2.9. Указатели. Связь указателей и массивов. Динамические массивы. Указатели на функции. Указатели и параметры функций. Сложные описания с указателями. Лекции 1 2 Л1.3
2.10. Структуры. Битовые поля. Указатели на структуры. Объединения. Размещение структур в памяти Лекции 1 2 Л1.3
2.11. Строки. Функции для работы со строками. Типичные операции над строками. Строки как параметры функций Лекции 1 2 Л1.3
2.12. Стандартная библиотека языка Си. Модули stdio.h, stdlib.h, math.h, time.h. Операционная система. Системные функции ОС. Модуль system.h. Процесс. Состояния процесса. Планирование процессов. Тупики и способы их устранения. Лекции 2 2 Л1.3
2.13. Файлы. Файловая система. Текстовые и бинарные файлы. Функции для работы с файлами. Типичные приемы работы с файлами. Лекции 1 2 Л1.3
2.14. Линейный вычислительный процесс Лабораторные 1 4 Л1.3
2.15. Ветвящийся вычислительный процесс Лабораторные 1 6 Л1.3
2.16. Циклический вычислительный процесс Лабораторные 1 10 Л2.1, Л1.3
2.17. Циклический вычислительный процесс Сам. работа 1 10 Л1.3
2.18. Функции Лабораторные 1 4
2.19. Функции Сам. работа 1 20 Л2.1
2.20. Массивы Лабораторные 1 10 Л1.3
2.21. Массивы Сам. работа 1 10 Л1.3
2.22. Строки Лабораторные 2 6 Л1.3
2.23. Строки Сам. работа 2 19 Л1.3
2.24. Структуры Лабораторные 2 4 Л1.3
2.25. Структуры Сам. работа 2 10 Л1.3
2.26. Файлы Лабораторные 2 4 Л1.3
2.27. Файлы Сам. работа 2 10
Раздел 3. Технология программирования
3.1. Сложность программных систем. Причины и последствия сложности программных систем. Пять признаков сложных систем. Ограниченность интеллектуальных возможностей человека и пути преодоления связанных с нею трудностей. Способы борьбы со сложностью. Эволюция языков программирования. Топология языков программирования. Структурное программирование: цели, принципы и стандарты. Модульность. Методы программирования «сверху вниз» и «снизу вверх». Стиль программирования. Комментарии. Ошибкоустойчивость. Тестирование программ. Методы тестирования. Отладка. Надежность. Переносимость программ. Лекции 1 2
3.2. Основы трансляции. Компиляция и интерпретация. Основные этапы компиляции. Лексический, синтаксический, семантический анализ. Формальная грамматика. Компиляция формулы. Прямая и обратная польские нотации. Дерево синтаксического разбора. Лекции 1 2
3.3. Парадигмы программирования. Логическое, императивное, объектно-ориентированное, декларативное и функциональное программирование. Визуальное программирование. Современные технологии программирования. Компонентное сборочное программирование. Динамика и открытость языков программирования. Лекции 1 2
Раздел 4. Алгоритмы и структуры данных
4.1. Сложность алгоритмов. Эффективность алгоритмов. Оценка сложности алгоритмов. Взаимосвязь расхода памяти и скорости алгоритма. Асимптотический анализ сложности алгоритмов. Анализ худшего, лучшего и среднего случаев. Символы $\theta$, $\Omega$, $\Theta$. Правила редукции асимптотических оценок сложности алгоритмов. Классы сложности алгоритмов. Лекции 1 2 Л1.1
4.2. Типы и структуры данных. Абстрактные типы данных. Физическая реализация абстрактных типов данных. Лекции 2 2
4.3. Сортировка. Нижняя граница временной сложности алгоритмов сортировки. Пузырьковая сортировка. Шейкерная сортировка. Сортировка выбором. Сортировка вставками. Сортировка слиянием. Алгоритм быстрой сортировки Хоара (quicksort). Сортировка Шелла (shellsort). Линейные сортировки. Лекции 2 4 Л2.1, Л1.1
4.4. Списки. Односвязный список. Реализация абстрактного типа «односвязный список» на основе массивов и механизма динамического распределения памяти. Двусвязный список. Словарь. Стэк. Очередь. Лекции 2 4
4.5. Деревья. Бинарные деревья. Полные и сбалансированные бинарные деревья. Свойства сбалансированных деревьев. Обходы деревьев. Реализации абстрактного типа «бинарное дерево». Бинарные деревья поиска. Очереди с приоритетом. Лекции 2 4
4.6. Поиск. Линейный и бинарный поиск. Поиск с возвратом. Задача о восьми ферзях. Поиск и деревья Лекции 2 4
4.7. Хэширование. Прямая адресация. Операции вставик, удаления и поворота. Хэш-таблицы. Хэш-функции. Разрешение коллизий. Открытое хэширование. Закрытое хэширование. Линейный обход. Квадратичный обход. Двойное хэширование. Лекции 2 4 Л2.1, Л1.2
4.8. Графы. Основные понятия теории графов. Способы представления графов: матрица смежности, матрица инцидентности, реберный список с двойными связями, списки смежности. Лекции 2 4 Л2.1, Л1.2
4.9. Задачи на графах. Алгоритм поиска компонент связности графа. Алгоритм Дейкстры поиска кратчайшего пути. Алгоритм Флойда поиска кратчайших путей. Алгоритмы Краскала и Прима построения остовного дерева графа. Гамильтоновы и эйлеровы циклы в графе. Алгоритмы проверки ацикличности и поиска циклов в графе. Лекции 2 4 Л1.2
4.10. Базовые методы сортировки Лабораторные 2 4
4.11. Базовые методы сортировки Сам. работа 2 20
4.12. Методы сортировки с линейно-логарифмической сложностью Лабораторные 2 4
4.13. Методы сортировки с линейно-логарифмической сложностью Сам. работа 2 20
4.14. Анализ сложности алгоритмов сортировки Лабораторные 2 4
4.15. Анализ сложности алгоритмов сортировки Сам. работа 2 20
4.16. Динамические структуры данных Лабораторные 2 6
4.17. Динамические структуры данных Сам. работа 2 26

5. Фонд оценочных средств

5.1. Контрольные вопросы и задания
смотри приложение
5.2. Темы письменных работ (эссе, рефераты, курсовые работы и др.)
Не предусматривается
5.3. Фонд оценочных средств
смотри приложение
Приложения

6. Учебно-методическое и информационное обеспечение дисциплины

6.1. Рекомендуемая литература
6.1.1. Основная литература
Авторы Заглавие Издательство, год Эл. адрес
Л1.1 Смирнов А.А. Технологии программирования : учебно-практическое пособие [Электронный ресурс]: Учебно-практическое пособие Евразийский открытый институт, 2011 // ЭБС "Университетская библиотека ONLINE" http://biblioclub.ru/index.php?page=book_red&id=90777&sr=1
Л1.2 Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона: Учебные пособия Издательство "ДМК Пресс", 2010 https://e.lanbook.com/book/1261
Л1.3 Подбельский В.В., Фомин С.С. Курс программирования на языке Си: Учебники Издательство "ДМК Пресс", 2012 https://e.lanbook.com/book/4148
Л1.4 Паронджанов В.Д. Учись писать, читать и понимать алгоритмы. Алгоритмы для правильного мышления. Основы алгоритмизации: Научно-популярная литература Издательство "ДМК Пресс", 2012 https://e.lanbook.com/book/4155
6.1.2. Дополнительная литература
Авторы Заглавие Издательство, год Эл. адрес
Л2.1 Кауфман В.Ш. Языки программирования. Концепции и принципы: Учебник М.: ДМК Пресс // ЭБС "Лань", 2011 https://e.lanbook.com/reader/book/1270/#1
6.2. Перечень ресурсов информационно-телекоммуникационной сети "Интернет"
Название Эл. адрес
Э1 C — The ISO Standard — Rationale, Revision 5.10 (англ.) (апрель 2004). — Обоснование и пояснения для стандарта C99. – http://www.open-std.org/JTC1/SC22/WG14/www/docs/C99RationaleV5.10.pdf
Э2 ISO/IEC JTC1/SC22/WG14 official home – Официальная страница международной рабочей группы по стандартизации языка программирования Си. – http://www.open-std.org/JTC1/SC22/WG14/
Э3 Поисковые системы - yandex.ru, google.com
Э4 Свободная энциклопедия Википедия – http://ru.wikipedia.org
Э5 Форум разработчиков программного обеспечения - Stackoverflow.com
Э6 Интернет-университет информационных технологий. – http://www.intuit.ru
Э7 Образовательный курс Основы программирования на платформе MOODLE https://portal.edu.asu.ru/course/view.php?id=223
6.3. Перечень программного обеспечения
Интегрированная среда разработки
Компилятор С/С++
Текстовый редактор
Microsoft Windows
Microsoft Office
7-Zip
AcrobatReader
6.4. Перечень информационных справочных систем
1. Образовательный портал АлтГУ [Электронный ресурс]: http://portal.edu.asu.ru
2. Издательство «Лань» - электронно-библиотечная система [Электронный
ресурс]: http://e.lanbook.com
3. Издательство МЦНМО. Свободно распространяемые книги издательства
Московского центра непрерывного математического образования
[Электронный ресурс]: www.mccme.ru/free-books
4. Математическая библиотека [Электронный ресурс]: www.math.ru/lib
7. Электронная библиотечная система Алтайского государственного
университета [Электронный ресурс]: http://elibrary.asu.ru
8. Научная электронная библиотека Elibrary [Электронный ресурс]:
http://elibrary.ru

7. Материально-техническое обеспечение дисциплины

Аудитория Назначение Оборудование
Учебная аудитория для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска)
Помещение для самостоятельной работы помещение для самостоятельной работы обучающихся Компьютеры, ноутбуки с подключением к информационно-телекоммуникационной сети «Интернет», доступом в электронную информационно-образовательную среду АлтГУ
107Л лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации Учебная мебель на 18 посадочных мест; компьютеры: марка HP, модель ProOne 400 - 18 единиц; проектор: марка SMART, модель UF70 - 1 единица; интерактивная доска: марка SMART Board модель SMB680 - 1 единица

8. Методические указания для обучающихся по освоению дисциплины

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

1. Рабoчая программа дисциплины

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

2. Глoссарий

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

3. Слайды к лекциям

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

4. Видеолекции

Видеолекции смонтированы на основе звукозаписей "живых" лекций и до некоторой степени способны их заменить. Пока они не покрывают полный курс, но их коллекция неуклонно пополняется. Используйте их для освежения в памяти рассмотренного материала. К сожалению, при просмотре видеолекций нет возможности задать вопрос лектору, однако его можно задать а) в личном сообщении преподавателю, б) в группе ВКонтакте vk.com/asuop2014, в) на очной консультации.

5. Лабораторные работы

Выполнение лабораторных работ -- основа практических занятий. Основные навыки программирования вырабатываются именно в эти моменты. Для выполнения работы необходимо

получить вариант задания у преподавателя, ведущего практические занятия;
обратившись к нужной лабораторной работе,загрузить документ с описанием работы;
внимательно прочитать задание к работе (как правило, на второй странице документа);
разработать, отладить и оттестировать программы, решающие указанные задачи;
составить отчёт о лабораторной работе по шаблону (см. ссылку в 0-м разделе курса);
загрузить PDF-версию отчета, используя нужный элемент "Лабораторная работа №..." (при необходимости вместо уже загруженного варианта отчета всегда можно загрузить и его обновленную версию);
очно защитить результаты работы перед преподавателем и получить оценку.

Оценки за лабораторные работы можно просмотреть через пункт меню "Оценки", расположенном на главной странице курса в её левой нижней части (Настройки\Управление курсом\Оценки).

Как правило на выполнение лабораторной работы отводится 3 недели, при этом сложность работ возрастает с увеличением номера лабораторной работы. По этой причине не рекомендуется затягивать первые простые работы.

6. Шаблон отчета о лабораторной работе

Шаблон отчета -- Word-документ, содержащий пример оформления отчета о выполнении лабораторной работы. Используйте этот документ как образец содержания и стиля оформления отчета, в том числе и в ситуациях, когда для подготовки отчета используются текстовые редакторы, отличные от Word-а.

7. Тесты

Тесты предназначены для контроля усвоения теоретического материала, а также умения читать и понимать код программ. Количество попыток на каждый тест ограничено тремя. Зачётные попытки выполнения теста осуществляются только в присутствии преподавателя (на практическом занятии или консультации). Оценка за тест определяется как максимальная из оценок, полученных в зачетных попытках. Результаты прочих попыток аннулируются, а попытки рассматриваются как тренировочно-ознакомительные.

Оценки за тесты сообщаются по окончании попытки, а также могут быть просмотрены в любой момент через пункт меню "Оценки", расположенный на главной странице курса в её левой нижней части (Настройки\Управление курсом\Оценки).

8. Рекомендации "Чтo почитать?"

Элемент "Чтo почитать?" имеется в большинстве разделов курса и содержит ссылки на фрагменты текстов учебников, вдумчивое прочтение которых является залогом успешного выполнения как тестовых заданий, так и лабораторных работ.

9. Рекомендации "Чтo посмотреть?"

На страницах с названием "Чтo посмотреть?" содержатся ссылки на видео-материалы, служащие либо полезными иллюстрациями к материалу соответствующего раздела курса, либо излагающие дополнительные сведения, необходимые для понимания раздела, но выходящие за рамки курса.

10. Примеры прoграмм

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

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