Закреплена за кафедрой | Кафедра информатики |
---|---|
Направление подготовки | 02.03.01. Математика и компьютерные науки |
Профиль | Математические основы компьютерных наук |
Форма обучения | Очная |
Общая трудоемкость | 7 ЗЕТ |
Учебный план | 02_03_01_МиКН-2-2020 |
|
|
Распределение часов по семестрам
Курс (семестр) | 1 (1) | 1 (2) | Итого | |||
---|---|---|---|---|---|---|
Недель | 19 | 19,5 | ||||
Вид занятий | УП | РПД | УП | РПД | УП | РПД |
Лекции | 34 | 34 | 32 | 32 | 66 | 66 |
Лабораторные | 34 | 34 | 32 | 32 | 66 | 66 |
Сам. работа | 4 | 4 | 89 | 89 | 93 | 93 |
Часы на контроль | 0 | 0 | 27 | 27 | 27 | 27 |
Итого | 72 | 72 | 180 | 180 | 252 | 252 |
Визирование РПД для исполнения в очередном учебном году
Рабочая программа пересмотрена, обсуждена и одобрена для
исполнения в 2020-2021 учебном году на заседании
кафедры
Кафедра информатики
Протокол от 30.06.2020 г. № 6
Заведующий кафедрой к.ф.-м.н., доцент Козлов Д.Ю.
1.1. | Целями освоения дисциплины являются: - формирование базовых знаний в области основ алгоритмизации и программирования; - выработка навыков решения типичных задач с использованием ЭВМ; - овладение приемами разработки и отладки программ в современных средах программирования. Изучение дисциплины направлено - на развитие у обучающихся алгоритмического мышления, систематизацию принципов построения языков программирования и подходов к разработке программ для ЭВМ; - на формирование навыков реализации алгоритмов на высокоуровневом императивном языке программирования; разработки, отладки и тестирования программ; - на подготовку обучающихся к системному восприятию дальнейших дисциплин из учебного плана, использующих навыки алгоритмизации и программирования; - на получение представлений об основных идеях структурного программирования и развитие способностей сознательно использовать материал курса, умение разбираться в существующих языковых и программных средствах и условиях их применения. |
---|
Цикл (раздел) ООП: Б1.О.04 |
УК-1 | Способен осуществлять поиск, критический анализ и синтез информации, применять системный подход для решения поставленных задач |
УК-2 | Способен определять круг задач в рамках поставленной цели и выбирать оптимальные способы их решения, исходя из действующих правовых норм, имеющихся ресурсов и ограничений |
ОПК-4 | Способен находить, анализировать, реализовывать программно и использовать на практике математические алгоритмы, в том числе с применением современных вычислительных систем |
ОПК-5 | Способен решать стандартные задачи профессиональной деятельности на основе информационной и библиографической культуры с применением информационно-коммуникационных технологий, в том числе отечественного производителя, и с учетом основных требований информационной безопасности |
ПК-1 | Способен демонстрировать базовые знания математических и естественных наук, основ программирования и информационных технологий |
ПК-2 | Способен преподавать математику и информатику в средней школе, специальных учебных заведениях на основе полученного фундаментального образования и научного мировоззрения. |
ПК-4 | Способен использовать современные методы разработки и реализации конкретных алгоритмов математических моделей на базе языков программирования и пакетов прикладных программ моделирования. |
В результате освоения дисциплины обучающийся должен | |
3.1. | Знать: |
---|---|
3.1.1. | о различных парадигмах программирования и современном уровне развития языков и технологий программирования; о сложности программных систем и методах ее преодоления; об основах построения трансляторов; основные понятия в области алгоритмизации, свойства алгоритмов, методы анализа сложности алгоритмов; синтаксис и базовые конструкции языков C и С++, основные возможности и приемы программирования на этих языках; принципы структурного программирования; назначение, устройство и свойства основных структур данных: список, очередь, стэк, дерево, граф; эффективные алгоритмы поиска и сортировки, алгоритмы решения задач теории графов. |
3.2. | Уметь: |
3.2.1. | разрабатывать алгоритмы решения типичных задач и реализовывать их на языке С; применять при решении алгоритмических задач типичные алгоритмы и структуры данных; использовать для разработки и отладки программ современные интегрированные среды разработки. |
3.3. | Иметь навыки и (или) опыт деятельности (владеть): |
3.3.1. | приемами чтения, построения и записи алгоритмов; навыками написания и отладки программ на высокоуровневом языке программирования в интегрированной среде разработки. |
Код занятия | Наименование разделов и тем | Вид занятия | Семестр | Часов | Компетенции | Литература |
---|---|---|---|---|---|---|
Раздел 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 | 1 | Л1.1 | |
2.24. | Структуры | Лабораторные | 2 | 4 | Л1.1 | |
2.25. | Структуры | Сам. работа | 2 | 1 | Л1.1 | |
2.26. | Файлы | Лабораторные | 2 | 4 | Л1.1 | |
2.27. | Файлы | Сам. работа | 2 | 1 | ||
Раздел 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 | 20 | ||
4.14. | Анализ сложности алгоритмов сортировки | Лабораторные | 2 | 4 | ||
4.15. | Анализ сложности алгоритмов сортировки | Сам. работа | 2 | 20 | ||
4.16. | Динамические структуры данных | Лабораторные | 2 | 6 | ||
4.17. | Динамические структуры данных | Сам. работа | 2 | 26 |
5.1. Контрольные вопросы и задания для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины |
смотри приложение |
5.2. Темы письменных работ для проведения текущего контроля (эссе, рефераты, курсовые работы и др.) |
Не предусматривается |
5.3. Фонд оценочных средств для проведения промежуточной аттестации |
смотри приложение |
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 |
Аудитория | Назначение | Оборудование |
---|---|---|
Учебная аудитория | для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик | Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска) |
Помещение для самостоятельной работы | помещение для самостоятельной работы обучающихся | Компьютеры, ноутбуки с подключением к информационно-телекоммуникационной сети «Интернет», доступом в электронную информационно-образовательную среду АлтГУ |
107Л | лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации | Учебная мебель на 18 посадочных мест; компьютеры: марка HP, модель ProOne 400 - 18 единиц; проектор: марка SMART, модель UF70 - 1 единица; интерактивная доска: марка SMART Board модель SMB680 - 1 единица |
В процессе освоения курса "Основы программирования" обучающийся будет сталкиваться с материалами разного рода. Ниже даны краткие инструкции по их использованию и освоению. 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. Экзамен проводится в письменном виде. Пример экзаменационного билета и пример его решения приводится на электронном ресурсе данного курса. Перед изложением нового материала каждой лекции рассматриваются задачи, которые входят в экзаменационные билеты. |