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

Основы программирования

рабочая программа дисциплины
Закреплена за кафедройКафедра информатики
Направление подготовки02.03.02. Фундаментальная информатика и информационные технологии
ПрофильПрограммирование и информационные технологии
Форма обученияОчная
Общая трудоемкость9 ЗЕТ
Учебный план02_03_02_ФИиИТ-2-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
Сам. работа 4 4 161 161 165 165
Часы на контроль 0 0 27 27 27 27
Итого 72 72 252 252 324 324

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

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

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

разработана в соответствии с ФГОС:
Федеральный государственный образовательный стандарт высшего образования по направлению подготовки 02.03.02 Фундаментальная информатика и информационные технологии (уровень бакалавриата) (приказ Минобрнауки России от 23.08.2017 г. № 808)

составлена на основании учебного плана:
02.03.02 Фундаментальная информатика и информационные технологии
утвержденного учёным советом вуза от 30.06.2020 протокол № 6.

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

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

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


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

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

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

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


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

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

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

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

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

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

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

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

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

6.1. Рекомендуемая литература
6.1.1. Основная литература
Авторы Заглавие Издательство, год Эл. адрес
Л1.1 Подбельский В.В., Фомин С.С. Курс программирования на языке Си: Учебники Издательство "ДМК Пресс", 2012 e.lanbook.com
Л1.2 Смирнов А.А. Технологии программирования : учебно-практическое пособие [Электронный ресурс]: Учебно-практическое пособие Евразийский открытый институт, 2011 // ЭБС "Университетская библиотека ONLINE" biblioclub.ru
Л1.3 Паронджанов В.Д. Учись писать, читать и понимать алгоритмы. Алгоритмы для правильного мышления. Основы алгоритмизации: Научно-популярная литература Издательство "ДМК Пресс", 2012 e.lanbook.com
Л1.4 Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона: Учебные пособия Издательство "ДМК Пресс", 2010 e.lanbook.com
6.1.2. Дополнительная литература
Авторы Заглавие Издательство, год Эл. адрес
Л2.1 Кауфман В.Ш. Языки программирования. Концепции и принципы: Учебник М.: ДМК Пресс // ЭБС "Лань", 2011 e.lanbook.com
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 portal.edu.asu.ru
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. Экзамен проводится в письменном виде. Пример экзаменационного билета и пример его решения приводится на электронном ресурсе данного курса. Перед изложением нового материала каждой лекции рассматриваются задачи, которые входят в экзаменационные билеты.