МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Нижегородский государственный университет им. Н.И. Лобачевского»
Радиофизический факультет
Кафедра математики
УТВЕРЖДАЮ
Декан радиофизического факультета
____________________Якимов А.В.
«18» мая 2011 г.
Учебная программа
Дисциплины Б3.Б3 «Основы программирования»
по направлению 010300 «Фундаментальная информатика и информационные технологии»
Нижний Новгород
2011 г.
1. Цели и задачи дисциплины
Целью преподавания дисциплины «Основы программирования» является ознакомление студентов с основными понятиями и методами программирования, простейшими алгоритмами, дающими представление о предмете в целом. Основной упор при этом делается на изучение методики постановки и решения вычислительных задач на современных ЭВМ, на формирование у студентов логически обоснованного подхода к выбору средств достижения результата и проведение анализа этого результата.
2.
Место дисциплины в структуре программы бакалавра
Дисциплина «Основы программирования» относится к дисциплинам базовой части профессионального цикла основной образовательной программы по направлению 010300 «Фундаментальная информатика и информационные технологии», преподается в 1 и 2 семестрах.
Знания, приобретённые в процессе изучения дисциплины «Основы программирования» используются как основа для преподавания и изучения дисциплин «Языки программирования», «Алгоритмы и анализ сложности», «Архитектура вычислительных систем», «Операционные системы», а также других дисциплин профессионального цикла, в которых затрагиваются вопросы программной реализации алгоритмов решения задач с профессиональной ориентацией.
3. Требования к уровню освоения содержания дисциплины
В результате освоения дисциплины формируются следующие компетенции:
-
способность понимать сущность и значение информации в развитии современного информационного общества (ОК–11);
-
владеть основными методами, способами и средствами получения, хранения, переработки информации, иметь навыки работы с компьютером как средством управления информацией (ОК 12);
-
способность применять в профессиональной деятельности современные языки программирования методологии системной инженерии, системы автоматизации проектирования, электронные библиотеки и коллекции, библиотеки и пакеты программ, современные профессиональные стандарты информационных технологий (ПК–1, ПК–27);
-
способность в составе научно-исследовательского и производственного коллектива решать задачи профессиональной деятельности (в соответствии с профилем подготовки) (ПК-5);
-
понимание концепций, синтаксической и семантической организации, методов использования современных языков программирования (ПК–19);
-
понимание концепций, базовых алгоритмов, принципов разработки и функционирования современных операционных систем (ПК–20);
-
знание международных стандартов в области разработки программного обеспечения, понимание процессного подхода, методов управления жизненным циклом и качеством программного обеспечения (ПК 21).
В результате изучения студенты должны:
-
знать основы алгоритмизации и принципы использования алгоритмических языков программирования для постановки и решения прикладных задач на ЭВМ; основные элементы, синтаксис и семантику языка высокого уровня;
-
уметь применять приобретенные знания в решении практических задач на примере традиционного набора простейших задач вычислительной математики;
-
иметь представление об инструментальных средствах решения практических задач на примере одного из алгоритмических языков высокого уровня;
Дисциплина опирается на материалы курсов аналитической геометрии и высшей алгебры, а также курса введение в информационные системы.
4.
Объём дисциплины и виды учебной работы
Общая трудоемкость дисциплины составляет 6 зачетных единиц, 216 часов.
Виды учебной работы
|
Всего часов
|
Семестры
|
Общая трудоемкость дисциплины
|
216
|
1
|
2
|
Аудиторные занятия
|
102
|
51
|
51
|
Лекции
|
68
|
34
|
34
|
Практические занятия (ПЗ)
|
34
|
17
|
17
|
Семинары (С)
|
0
|
0
|
0
|
Лабораторные работы (ЛР)
|
0
|
0
|
0
|
Другие виды аудиторных занятий
|
0
|
0
|
0
|
Самостоятельная работа
|
78
|
39
|
39
|
Курсовой проект (работа)
|
0
|
0
|
0
|
Расчетно-графическая работа
|
0
|
0
|
0
|
Реферат
|
0
|
0
|
0
|
Другие виды самостоятельной работы
|
0
|
0
|
0
|
Вид итогового контроля (зачет, экзамен)
|
зачет, экзамен (36)
|
зачет
|
экзамен (36)
|
5. Содержание дисциплины
5.1. Разделы дисциплины и виды занятий
№ п/п
|
Раздел дисциплины
|
Лекции
|
ПЗ (или С)
|
ЛР
|
1
|
Введение
|
4
|
-
|
-
|
2
|
Структурное и модульное программирование на языках высокого уровня
|
15
|
9
|
-
|
3
|
Объектно-ориентированное программирование
|
15
|
8
|
-
|
4
|
Основные структуры данных
|
19
|
9
|
-
|
5
|
Основы алгоритмизации
|
15
|
8
|
-
|
5.2. Содержание разделов дисциплины
Раздел 1. Введение.
Этапы развития современных ЭВМ и языков программирования.
Инструментальные средства системного программного обеспечения. Назначение и основные команды MS WINDOWS, OS UNIX.
Работа с текстовыми редакторами. Редактирование, компиляция, компоновка и выполнение простейших программ в средах MS WINDOWS и OS UNIX.
Раздел 2. Структурное и модульное программирование на языках высокого уровня.
Операторы. Метки. Комментарии. Формат.
Базисные элементы языка. Типы данных. Константы. Переменные. Указатели. Идентификаторы. Принцип умолчания. Описание типов данных. Индексированные переменные и массивы данных. Описание. Размещение и инициализация в памяти ЭВМ. Присваивание значения.
Типы выражений. Арифметические выражения. Выражения отношений. Логические выражения.
Операции. Приоритет операций, ранги операндов.
Структура программного модуля.
Алгоритмы линейной структуры, разветвляющейся структуры. Безусловные и условные переходы. Алгоритмы циклической структуры. Правила явной организации циклов. Цикл общего вида. Цикл с предусловием и постусловием. Итерационный цикл. Счетный цикл. Функции и подпрограммы. Формальные и фактические параметры. Способы передачи данных. Принцип модульного программирования.
Ввод-вывод информации. Управление вводом-выводом. Хранение данных.
Раздел 3. Объектно-ориентированное программирование.
Объектно-ориентированная разработка; инкапсуляция и информационное упрятывание; отделение описания поведения от реализации; классы, подклассы и наследование; полиморфизм; иерархия классов; собрания классов и протоколы взаимодействия; программирование на основе шаблонов.
Раздел 4. Основные структуры данных.
Простые типы; массивы; записи; строки и обработка строк; представление данных в памяти; методы распределения памяти (статическое, автоматическое, динамическое); управление памятью периода выполнения; связанные списки; методы реализации стеков, очередей, хеш-таблиц, графов и деревьев.
Раздел 5. Основы алгоритмизации.
Понятие алгоритма. Блок-схема алгоритма.
Понятие рекурсии; математические рекурсивные функции; примеры рекурсивных процедур; рекурсия и метод «разделяй и властвуй»; реализация бэктрекинга (backtracking) посредством рекурсии; реализация рекурсии с помощью стека.
Различные алгоритмы сортировки массивов: плюсы, минусы, скорость работы, устойчивость, примеры реализации на языке высокого уровня.
5.3. Темы практических занятий
-
Работа в командной строке. Основные операторы ОС Windows и Linux
-
Создание программ на языке С. Компилляторы. Принципы компилляции.
-
Применение оператора ветвления.
-
Работа с массивами. Операторы цикла.
-
Ввод-вывод. Работа с файлами.
-
Применение структур и объединений.
-
Создание пользовательских функций.
-
Отчет по задачам.
-
Принципы построения программ на языке С++
-
Создание класса. Поля и методы.
-
Использование механизма скрытия данных.
-
Создание класса «Трехмерный вектор».
-
Создание класса «Трехмерный вектор».
-
Принцип наследования.
-
Создание класса «N-мерный вектор».
-
Создание класса «N-мерный вектор».
-
Отчет по задачам.
7. Лабораторный практикум
Не предусмотрен.
8. Учебно-методическое обеспечение дисциплины
8.1. Рекомендуемая литература.
а) основная литература:
-
Болски М.И. Справочник. Язык программирования Си. М.: Радио и связь, 1986 – 96с.
-
Дейтел П. Дж., Дейтел Х.М. Как программировать на С++. Введение в объектно-ориентированное проектирование с использованием UML. М.: БИНОМ, 2002 – 1152с.
-
Джехани Н. Программирование на языке Си. М.: Радио и связь, 1988 – 270с.
-
Керниган Б., Ритчи Д. Язык программирования Си. 3-е изд., СПб.: Невский диалект, 2001 – 352с.
-
Кнут Д. - Искусство программирования для ЭВМ. Т. 3. - М.: Мир, 1978 – 844с.
-
Кормен, Томас - Алгоритмы: построение анализ. - М.: МЦНМО, 1999 – 960с.
-
Савин В.А. Представление данных цифровых ЭВМ / Методическая разработка для студентов радиофизического факультета ННГУ. – Н.Новгород: ННГУ, 2001 – 58с.
-
Страуструп Б. Язык программирования С++. М.:БИНОМ, СПб.: Невский диалект, 2001 – 1099с.
-
Шилдт Г. Самоучитель С++. СПб.: БХВ-Петербург, 1997 – 512с.
-
Шилдт Г. Справочник программиста по С/С++. М.: изд. дом Вильямс, 2001 – 448с.
б) дополнительная литература:
-
Липпман С.Б. С++ для начинающих. М.: Унитех, Рязань: Гэлион, 1993. т.1 – 304с, т.2 – 345с.
-
Липпман С.Б., Лажойе Ж. Язык программирование С++. Вводный курс, 3-е изд. СПб: Невский проспект, М.: ДМК Пресс, 2001 – 1104с.
-
Липпман С.Б. Основы программирования на С++. Серия C++ InDepth, М.: Вильямс, 2002 – 256с.
-
Страуструп Б. Язык программирования С++. М.: Радио и связь, 1991 – 352с.
-
Страуструп Б. Язык программирования С++. Второе издание. Киев: ДиаСофт, 1993. ч.1 – 264с, ч.2 – 296с.
-
Шилдт Г. Теория и практика С++. СПб.: БХВ-Петербург, 2000 – 416с.
-
Элджер Дж. С++ : библиотека программиста. СПб.: Питер, 1999 – 320с.
-
Эллис М., Строуструп Б. Справочное руководство по языку программирования С++ с комментариями. Проект стандарта ANSI. М.: Мир, 1992 – 445с.
9. Вопросы для контроля
-
Общая характеристика языка С.
-
Структура программы на языке С. Подключение библиотек. Организация ввода-вывода с помощью библиотеки stdio.
-
Модуль в языке С. Организация многофайловой программы, заголовочные файлы, директива #include, прототипы функций.
-
Оператор присваивания и оператор ветвления. Особенности оператора присваивания и вычисления условий в языке С. Примеры операторов присваивания и ветвления.
-
Организация циклов. Циклы с предусловием и постусловием. Цикл for и его связь с циклом while. Примеры.
-
Оператор переключатель (switch). Инструкция break. Примеры применения оператора переключателя.
-
Обзор операций языка С. Приоритеты операций. Правила вычисления выражений. Примеры операций.
-
Понятие идентификатора и переменной. Объявления и инициализация переменных и массивов в С.
-
Числовые типы данных языка С. Целочисленные (десятичные, восьми и шестнадцатеричные) и действительные константы. Именованные константы и способы их задания в языке С.
-
Массивы с языке С. Объявление и использование массивов.
-
Структуры в языке С. Объявление типа и переменных. Использование элементов структур.
-
Символьный тип в языке С. Символьные константы. Представление строк в С.
-
Указатели и ссылки в языке С/C++. Константные указатели и ссылки. Операции с указателями и ссылками.
-
Массив как указатель в языке С. Особенности индексации массива при записи кода. Массив как параметр функции. Многомерные массивы.
-
Динамическое выделение памяти. Операторы new и delete.
-
Функции в языке С. Объявление, описание и вызов. Особенности передачи параметров (по значению, по ссылке [C++], указателем, по константной ссылке [C++]).
-
Время жизни и область видимости объектов. Локальные и глобальные объекты.
-
Форматный вывод и ввод. Функции printf и scanf библиотеки stdio.
-
Работа с текстовыми файлами. Функции fopen, fclose, fprintf, fscanf библиотеки stdio.
-
Технологические основы языков программирования высокого уровня. Структурное и модульное программирование.
-
Объектный подход. Парадигмы ООП. Достоинства и недостатки ООП.
-
Понятие класса. Инкапсуляция. Объявление класса. Поля и методы. Секции public и private. Скрытие данных.
-
Объявление класса. Поля и методы. Секции public и private. Скрытие данных. Пример разработки класса “Комплексное число”. Реализация методов класса.
-
Способы создания объектов. Доступ к данным и методам объекта. Указатель this. Статическое и динамическое создание объектов внутри методов. Ссылки в заголовках методов. Примеры.
-
Создание объектов. Конструкторы. Виды конструкторов. Конструктор копирования. Пример разработки конструктора копирования.
-
Уничтожение объектов. Деструкторы.
-
Перегрузка операций. Правила перегрузки операторов. Перегрузка унарных операторов. Перегрузка операции []. Перегрузка бинарных операторов. Перегрузка операции присваивания. Операция присваивания и конструктор копирования.
-
Виды иерархий. Наследование и агрегация. Реализация агрегации в C++.
-
Наследование в C++. Public, private и protected-наследование. Перекрытие методов. Некоторые правила наследования.
-
Перегрузка функций в C++. Сигнатура. Алгоритм проверки соответствия сигнатуре.
-
Шаблоны функций. Шаблоны классов.
-
Блок-схема как способ представления алгоритма. Пример составления блок-схемы.
-
Рекурсия. Пример итеративной реализации рекурсивного алгоритма. Метод "перебор с возвратом" (backtracking) на примере задачи о шахматном коне. Метод "разделяй и властвуй" на примере возведения числа в целую степень.
-
Тип данных "Массив". Основные алгоритмы обработки массивов. Добавление и удаление элементов. Поиск максимального и минимального элемента. Линейный и бинарный поиск элемента в массиве.
-
Задача сортировки массива. Сортировка простыми включениями. Сортировка бинарными включениями. Сортировка простым выбором. Сортировка простым обменом. Шейкерная сортировка. "Быстрая сортировка" (quick-sort). Сортировка слиянием.
-
Тип данных "Стек". Основные операции. Реализация стека на массиве. Реализация стека на связном списке.
-
Тип данных "Очередь". Основные операции. Структура элемента связного списка. Операции со связным списком. Реализация очереди на массиве. Реализация очереди на связном списке.
-
Тип данных "Хэш-таблица". Хэш-функции и их применение.
10. Критерии оценок
Зачтено
|
Подготовка, удовлетворяющая минимальным требованиям.
|
Не зачтено
|
Необходима дополнительная подготовка для успешного прохождения испытаний.
|
Превосходно
|
Превосходная подготовка с очень незначительными погрешностями
|
Отлично
|
Подготовка, уровень которой существенно выше среднего с некоторыми ошибками
|
Очень хорошо
| В целом хорошая подготовка с рядом заметных ошибок |
Хорошо
| Хорошая подготовка, но со значительными ошибками |
Удовлетворительно
|
Подготовка, удовлетворяющая минимальным требованиям
|
Неудовлетворительно
|
Необходима дополнительная подготовка для успешного прохождения испытания
|
Плохо
| Подготовка совершенно недостаточная |
11. Примерная тематика курсовых работ и критерии их оценки
Не предусмотрены.
Программа составлена в соответствии с Федеральным государственным образовательным стандартом высшего профессионального образования по направлению 010300 «Фундаментальная информатика и информационные технологии»
Автор программы ___________ Уткин С.Г.
Программа рассмотрена на заседании кафедры 18 марта 2011 г. протокол № 10-11-04
Заведующий кафедрой _________________ Дубков А.А.
Программа одобрена методической комиссией факультета 11 апреля 2011 года
протокол № 05/10
Председатель методической комиссии_________________ Мануилов В.Н.