• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2018/2019

Информатика и программирование

Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Статус: Курс обязательный (Информатика и вычислительная техника)
Направление: 09.03.01. Информатика и вычислительная техника
Когда читается: 2-й курс, 1, 2 модуль
Формат изучения: без онлайн-курса
Преподаватели: Клышинский Эдуард Станиславович, Константинов Юрий Алексеевич, Лежнев Евгений Владимирович, Рысаков Святослав Викторович
Язык: русский
Кредиты: 4
Контактные часы: 60

Программа дисциплины

Аннотация

Целью освоения дисциплины «Информатика и программирование» является изучение основ владения вычислительной техникой, информатикой, методами программирования на языках высокого уровня, закрепление навыков в области программирования и проектирования структуры данных, владения основными алгоритмами обработки данных. В рамках данной дисциплины даются такие разделы как основные операторы языков программирования, алгоритмы сортировки данных, базовые структуры хранения данных, работа с библиотеками файлового и консольного ввода-вывода, основы создания графического интерфейса с использованием современных библиотек. В процессе освоения дисциплины «Информатика и программирование» студент развивает следующие компетенции: · знает способы представления различной информации в компьютере; · знает основы теории алгоритмов и абстрактных вычислительных машин; · знает базовые элементы языков C/C++; · уметь использовать стандартное программное обеспечение в своей профессиональной деятельности; · иметь навыки самостоятельной постановки задачи на разработку ПО и ее решения; · иметь навыки математической постановки задач и Разработки алгоритмов решения задачи.
Цель освоения дисциплины

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

  • Освоение технологии структурного программирования
  • Изучение базовых элементов языков C/C++
  • Изучение стандартных алгоритмов обработки различных структур данных
  • Изучение приемов разработки алгоритмов для обработки различных структур данных
Планируемые результаты обучения

Планируемые результаты обучения

  • Системы счисления: основные определения, классификация. Методы перевода чисел из одной системы счисления в другую систему: общий подход, алгоритмы замещения, целочисленного деления, последовательного умножения, группирования, расщепления. Представление чиел в ЭВМ. Числа со знаком: прямой код, дополнительный код. Разрядные сетки с фиксированной и плавающей запятой. Двоичная арифметика. Применение двоичной и шестнадцатеричной систем счисления.
  • Решение задач на методы перевода чисел в различные системы счисления.
  • Прямой, инверсный и дополнительный коды. Решение задач двоичной арифметики.
  • Двоичная булева алгебра: множество элементов, множество операций. Определение и доказательство постулатов булевой алгебры. Применение булевой алгебры.
  • Основы цифровой электроники. Цифровой сигнал. Логические элемента (вентили). Конструирование логических схем на основе логического выражения.
  • Изучение интерфейса пакета MathCAD. Особенности работы с логическими функциями. Решение задач на применение постулатов булевой алгебры.
  • Решение задач на конструирование логических схем на основе логического выражения.
  • Основы комбинаторики и теории вероятностей.
  • Понятие информации и энтропии по Шеннону.
  • Понятие о параллельном программировании. Основные объекты, позволяющие проводить вычисления в несколько потоков и особенности их использования.
  • Понятие энтропии, условной энтропии, взаимной информации. Примеры использования понятия энтропии в различных разделах науки и техники.
  • Вычисление вероятностей для различных ситуаций.
  • Вычисление энтропии для различных ситуаций.
  • Применение теории информации на примере генерации случайных чисел. Подробный разбор ситуации.
  • Кодирование источника информации. Понятие дискретных каналов связи без памяти. Примеры.
  • Понятие пропускной способности канала связи. Понятие о кодах, корректирующих ошибки. Примеры.
  • Вычисление пропускной способности различных каналов связи (симметричный бинарный дискретный канал, канал со стиранием, составные каналы).
  • Сигналы, их свойства в теории информации. Методы оцифровки непрерывных сигналов. Теорема Котельникова.
  • Кодирование звука, цвета, изображения.
  • Построение графиков функций различных сигналов в среде MathCAD.
  • Оцифровка непрерывных сигналов.
  • Понятие одноразового блокнота. Классификация шифров. Связь энтропии с секретностью криптосистемы по Шеннону.
  • Связи сложности перебора ключей с энтропией. Понятие секретной пропускной способности канала связи.
  • Кратко о новых направлениях теории информации - квантовая теория информации.
  • Применение шифра Цезаря с различным сдвигом.
  • Примеры зашифрования и расшифрования в режиме одноразового блокнота в бинарной, шестнадцатеричной системе счисленияи в ASCII.
  • Язык программирования С. Достоинства и структура языка программирования. Простые и составные типы. Типы данных. Пример описания простых переменных. Константы целые, вещественные, символьные и строковые. Описания с начальным присваиванием. Выражения. Операции в Си: унарные, бинарные и тернарные. Арифметические и логические операции, операции отношения. Операции присваивания. Инкремент и декремент, префиксная и постфиксная форма инкремента и декремента.
  • Язык C. Особенности объявлений и некоторые операции. Указатели в языке С. Массивы и матрицы. Варианты ввода одномерного массива. Решение задач обработки массивов с использованием индексов и указателей.
  • Простые и составные операторы. Условная конструкция: простейшая, расширенная, выбор. Отличия от Паскаля. Вложенность операторов if, операция условия. Множественный выбор: switch. Оператор Break. Правила выбора условных операторов. Циклы. Цикл-пока (while). Цикл for. Замена for на while. Отличия for от Паскаля. Вложенные циклы. Совершенные числа. Цикл с постусловием do…while. Управляющие операторы break, continue, goto.
  • Перестановка элементов массива в заданном порядке с сохранением порядка следования отрицательных и неотрицательных элементов. Формирование массива С, состоящего из повторяющихся элементов исходного массива А, отсутствующих в заданном массиве В.
  • Потоковый ввод-вывод (cincout). Формирование массива C состоящего из элементов заданного массива A повторяющихся в заданном массиве B несколько раз. (Раздел 8). Поиск длины максимальной последовательности из нулей и начала этой последовательности в массиве целых чисел A[0:n-1]. Сортировка элементов матрицы по всем строкам (по возрастанию) без использования дополнительного массива.
  • Распределение памяти. Классы памяти. Свойства классов памяти. Автоматические переменные. Внешние переменные. Атрибут extern. Статические переменные. Внешние статические переменные. Регистровые переменные.
  • Массивы и указатели. Операции с указателями. Многомерные массивы. Доступ к элементам массива с помощью указателей.
  • Перестановка двух последних нечетных элементов одномерного целочисленного массива с использованием указателей. Перестановка двух наименьших элементов матрицы A[0:n-1,0:m-1] с использованием указателей.
  • Вычисление количества четных, нечетных. кратных 3-м и 4-м среди первых 1000 членов ряда Фибоначчи, использование оператора continue при кодировании алгоритма. Синтаксические особенности Си. Функции. Описание функции. Правила оформления функций. Вызов функции. Оператор return. Функция обмена значения двух переменных. Передача параметров по адресу и по значению.
  • Правила оформления функций. Особенности работы функций. Передача параметров по адресу и по значению. Решение задач.
  • Особенности работы функций. Ввод и вывод элементов матрицы с использованием функций. Вычисление максимального среди отрицательных элементов матрицы А, не встречающихся в массиве В. Определение адресов двух первых четных элементов массива А с использованием функции. Указатель на указатель.
  • Операции над типом char. Ввод и вывод данных типа char. Символьные строки. Примеры использования указателя при работе со строками. Инициализация. Использование указателя для создания строки.
  • Массивы символьных строк. Операции с типом char. Ввод-вывод строк. Функции scanf() и printf(). Функции gets и puts. Ввод строк до ввода пустой строки. Функции getchar() и putchar(). Строковые функции.
  • Длина строки strlen(). Сцепление строк (конкатенация – strcat(). Сравнение строк strcmp(). Копирование строки strcpy().Адрес первого появления заданного символа в строке strchr().
  • Символьный тип данных. Операции над типом char. Символьные строки. Примеры подпрограмм, реализующих стандартные функции обработки символьных строк. Вычисление длины строки. Вычисление адреса первого появления заданного символа ch в строке str. Сравнение строк str1 и str2 в лексикографическом порядке. Копирование содержимого строки str1 в строку str2.
  • Ввод символьных строк до пустой строки. Ввод массива символьных строк и поиск в каждой строке максимального целого числа без знака, заключенного в круглые скобки.
  • Пример выполнения заданий лабораторной работы 3 по обработке символьных строк (выделение из каждой строки подстрок, не содержащих квадратных скобок). Поиск подстроки, начинающейся с наибольшего числа цифр.
  • Структуры. Объявление структурного типа. Определение структурных переменных. Инициализация. Доступ к элементам структуры, составные имена. Массивы структур. Вложенные структуры. Определение переменной структурного типа и инициализация. Указатели на структуры. Указатели и массивы структур. Операции над структурами. Присваивание. Сравнение структур.
  • Доступ к элементу структуры при помощи указателя. Операция присоединения. Доступ с помощью составного имени. Передача информации о структурах функциям. Текстовые файлы. Открытие и закрытие файла. Потоковые функции ввода и вывода для файлов. Функции ввода и вывода (fgetc(), fputc()). Форматный ввод/вывод (fscanf(), fprintf()). Ввод строки (fgets()). Вывод строки (fputs()). Определение конца файла (feof).
  • Сортировка массива структур с использованием массива указателей. Чтение матрицы и массива из файла. Функция формирования текстового файла, состоящего из строк, вводимых с клавиатуры. Вывод на экран содержимого текстового файла. Функция fseek - установка позиции в текстовом файле ввода-вывода. Подсчет числа повторов каждого символа содержащегося в файле.
  • Структуры. Ввод массива структур. Поиск самой дорогой книги.
  • Файлы. Особенности текстовых файлов в языке Си. Чтение массива из файла и поиск максимума.
  • Чтение из файла и запись в файл массива структур. Варианты ввода массива структур.
  • Функции динамического распределения памяти. Функция malloc(), calloc(), free(), sizeof().
  • Динамическое выделение памяти для одномерного массива. Динамическое выделение памяти для двумерного массива. Динамические структуры данных. Формирование стека и вычисление суммы элементов стека. Циклический список. Подпрограмма занесения значения X в очередь на базе циклического списка. Двунаправленные связанные списки. Занесение значения X в стек на базе линейного двунаправленного связанного списка.
  • Удаление элементов из циклического однонаправленного списка. Бинарные деревья. Алгоритм обхода бинарного дерева (в прямом, обратном, симметричном порядке). Формирование бинарного дерева. Использование бинарного дерева для сортировки. Свойства рекурсивных алгоритмов. Операции над бинарными деревьями. Вывод дерева на экран. Задачи обработки бинарного дерева: подсчет числа узлов, подсчет числа листьев, подсчет числа однодетных отцов, подсчет глубины.
  • Задачи обработки бинарного дерева: удаление листьев, поиск максимума, удаление чисел, меньших заданного числа. Использование бинарного дерева для вычисления значения арифметического выражения. Мультисписки. Формирование мультисписка, вывод списка на экран.
  • Динамические структуры данных. Функции malloc() - выделение памяти, free() - освобождение памяти. Ввод текста в динамическую память. Освобождение памяти, занятой введенным текстом. Формирование стека, содержащего структуры КНИГА (исходные данные читаются из файла). Формирование циклического связанного списка (стека), содержащего последовательность целых положительных чисел, вводимых с клавиатуры.
  • Формирование двунаправленного связанного списка (очередь), содержащего последовательность целых положительных чисел, вводимых с клавиатуры. Вставка в двунаправленный связанный список числа 2000 до и после каждого элемента, большего чем X1 и меньшего чем X2. Рекурсия (простая и косвенная). Рекурсивный и итерационный алгоритмы вычисления факториала.
  • Бинарные деревья. Сортировка по возрастанию с использованием бинарного дерева. Удаление из данного бинарного дерева всех значений, равных заданному числу Х.
  • Понятия класса и объекта, инкапсуляция. Конструктор и деструктор. Объявление классов и объектов в С++. Динамическое выделение и освобождение памяти в С++.
  • Классы STL для хранения данных. Библиотека ввода-вывода STL.
  • Понятия сигналов и слотов в Qt. Классы виджета, окна, элементов оконного интерфейса. Методы проектирования интерфейсов на основе модели MVC.
  • Понятие оператора, перегружаемые операторы. Особенности перегрузки отдельных операторов. Понятие ссылки на объект. Необходимость перегрузки некоторых операторов.
  • Понятие наследования, виды наследования. Зоны видимости при наследовании. перегрузка функций при наследовании.
  • Понятие виртуальных функций. Перегрузка виртуальных функций. Вызов виртуальных функций в зависимости от типа объекта. Статические члены-данные и члены-функции.
  • Передача значений параметров по умолчанию. Создание функций с переменным количеством параметров.
  • Понятие исключительной ситуации. Базовый класс для обработки исключительных ситуаций. Порождение исключительных ситуаций. Метод обработки исключительных ситуаций в зависимости от типа. Положительные и отрицательные стороны применения исключительных ситуаций.
  • Создание функций с шаблонными (<template>) параметрами. Создание классов с шаблонными функциями или членами-данными. Особенности разработки шаблонных классов.
  • Общие понятия из области функционального программирования. Необходимость применения лямбда-выражений. Синтаксис лямбда-выражений.
  • Final, override. Ссылки на временные объекты. Списки инициализации.
Содержание учебной дисциплины

Содержание учебной дисциплины

  • Математические основы вычислительной техники: системы счисления, двоичная арифметика
  • Основы теории информации
  • Применение теории информации для передачи сообщений
  • Логические основы вычислительной техники: булева алгебра, логические схемы
  • Применение теории информации, примеры
  • Сигналы и их свойства в теории информации. Кодирование звука, цвета, изображения
  • Приложение теории информации в криптографии
  • Основные сведения о языке C.
  • Конструкции языка C.
  • Распределение памяти. Классы памяти.
  • Использование указателей при обработке массивов и матриц.
  • Функции в языке C.
  • Символьный и строковый тип данных.
  • Структуры. Файлы.
  • Динамическое распределение памяти. Списки. Бинарные деревья.
  • Основы объектно-ориентированного программирования.
  • Библиотека STL.
  • Визуальная библиотека Qt, сигналы и слоты, модель проектирования MVC.
  • Перегрузка операторов.
  • Наследование.
  • Виртуальные, и статические члены классов.
  • Функции с различным количеством параметров.
  • Обработка исключительных ситуаций.
  • Шаблонные классы.
  • Лямбда-выражения.
  • Основные возможности С++ стандарта 0x11/0х14.
  • Основные возможности библиотеки STL стандарта 0x11/0х14.
Элементы контроля

Элементы контроля

  • неблокирующий Аудиторные занятия 1
  • неблокирующий Домашняя работа
  • неблокирующий Экзамен 2 модуль
  • неблокирующий Лекции 3 модуль
  • неблокирующий Лекции 4 модуль
  • неблокирующий Семинарские занятия 3 модуль
  • неблокирующий Семинарские занятия 4 модуль
  • неблокирующий Лабораторные 3 модуль
  • неблокирующий Лабораторные 4 модуль
  • неблокирующий Контрольная работа 1
  • неблокирующий Лабраторные 5 модуль
  • неблокирующий Лабораторные 6 модуль
  • неблокирующий Зачет 5 модуль
  • неблокирующий Зачет 6 модуль
  • неблокирующий Аудиторные занятия 2
  • неблокирующий Экзамен 4 модуль
Промежуточная аттестация

Промежуточная аттестация

  • Промежуточная аттестация (2 модуль)
    0.06 * Аудиторные занятия 1 + 0.036 * Аудиторные занятия 2 + 0.024 * Домашняя работа + 0.1 * Зачет 5 модуль + 0.1 * Зачет 6 модуль + 0.036 * Контрольная работа 1 + 0.096 * Лабораторные 3 модуль + 0.06 * Лабораторные 4 модуль + 0.15 * Лабораторные 6 модуль + 0.15 * Лабраторные 5 модуль + 0.012 * Лекции 3 модуль + 0.012 * Лекции 4 модуль + 0.012 * Семинарские занятия 3 модуль + 0.012 * Семинарские занятия 4 модуль + 0.08 * Экзамен 2 модуль + 0.06 * Экзамен 4 модуль
Список литературы

Список литературы

Рекомендуемая основная литература

  • Дэвид М. Харрис, Сара Л. Харрис - Цифровая схемотехника и архитектура компьютера - Издательство "ДМК Пресс" - 2017 - 792с. - ISBN: 978-5-97060-522-6 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/97336
  • Математические основы информатики: элективный курс : учеб. пособие, Андреева, Е. В., 2007
  • Харрис Дэвид М., Харрис Сара Л. - Цифровая схемотехника и архитектура компьютера. Дополнение по архитектуре ARM - Издательство "ДМК Пресс" - 2019 - 356с. - ISBN: 978-5-97060-650-6 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/111431

Рекомендуемая дополнительная литература

  • Алексеев Е.Р., Злобин Г.Г., Костюк Д.А. - Программирование на языке С++ в среде Qt Creator - Национальный Открытый Университет "ИНТУИТ" - 2016 - 715с. - ISBN: - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100414