Ю. А. Самарский 10 июня 2008 г. Программа

Вид материала

Содержание

Список литературы
Указание по реализации
Указание по реализации
Дополнительные требования
Указание по реализации
Дополнительные требования
Указание по реализации
Указание по реализации
Указание по реализации

Подобный материал:

УТВЕРЖДАЮ

Проректор по учебной работе

Ю. А. Самарский

10 июня 2008 г.

ПРОГРАММА

по курсу ОСНОВЫ ИНФОРМАТИКИ (Введение в программирование)

по направлению 010600

факультеты ФИВТ

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

курс I

семестр 1 Два задания

лекции – 34 часа Две контрольные работы

практические занятия – 68 часов Зачет дифференцированный

ВСЕГО ЧАСОВ – 102

Программу составили: чл.-корр. РАН В.Л. Арлазаров,

доцент, к.ф.-м.н. Б.Г. Кухаренко,

к.т.н. Д.В. Полевой

Программа обсуждена

на заседании кафедры

информатики

28 августа 2008 г.

Заведующий кафедрой И.Б. Петров

1. Вводные понятия. Язык программирования С++. Управляющие инструкции С++. Консольный ввод и вывод. Компиляция и выполнение программы С++.

Вводные понятия.

Введение в булеву алгебру.
Интуитивное понятие алгоритма. Блок-схема. Подпрограмма.
Понятие типа данных. Абстрактные типы данных (АТД).
АТД число.

Системы счисления (двоичная, восьмеричная, десятичная, шестнадцатеричная).

Понятие переменной.

Язык программирования С++.

Язык программирования С++ (история, стандарт, обратная совместимость с С, место среди других языков программирования).
Структура программы С++.
Комментарии.
Директивы препроцессора.
Идентификаторы. Служебные слова.
Переменные. Встроенные типы данных (ВТД) языка С++.
Литералы (константы).
Функции.

Управляющие инструкции

Ветвления, циклы, переходы.
Бесконечные циклы.
Вложенные инструкции.
Объявления переменных в инструкциях.

Базовые функции консольного ввода/вывода.

Обзор механизмов компиляция и исполнение программы.

Препроцессор.
Синтаксический анализатор.
Компилятор. Оптимизатор.
Компоновщик.
Исполнение программы.

2. Операторы и выражения в С++. Организация вычислений в С++.

Операторы и выражения.

Обзор операторов.
Приоритет и ассоциативность операторов.
Оператор присвоения. Приведение типа при присвоении.
Арифметические операторы.
Сравнения и логические операторы.
Порядок вычислений. Расстановка пробелов и скобок.

Вычисления.

Арифметика с фиксированной и плавающей точкой. Проблемы округления.
Вычисление частичных сумм рядов.
Рекуррентные соотношения.

3. Указатели и массивы в С++. С-строки и функции стандартной библиотеки. Типизация. Вычисление многочленов в С++.

Указатели и массивы.

Модели памяти. Векторная (непрерывная) память.
Представление переменных в памяти компьютера.
Переменные–указатели базовых типов.
Операции взятия адреса и разъименования.
Адресная арифметика.
Понятие адресной константы.
Массивы. Связь указателей и массивов.

С-строки.

Простой строковый тип (С-строка) в С++.
Связь С-строк с массивами и указателями.

Типизация.

Типизированные и не типизированные языки программирования.
Явное и неявное приведение типа. Автоматическое приведение типов в выражениях.
Приведение типов для ВТД языка С++ (static_cast, const_cast).
Приведение типов переменных-указателей в С++ (reinterpret_cast).
Приведение типов в стиле С (использовать не рекомендуется).

Задача вычисления многочленов и реализация на С++.

Представление и вычисление многочленов.
Быстрое возведение в степень.
Схема Горнера.

4. Структура оперативной памяти программы С++. Динамическая работа с памятью. Файловый ввод/вывод. Обработка ошибок.

Структура оперативной памяти при программировании на языке С++.

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

Динамическое распределение памяти.

Операторы динамической работы с памятью.
Распределение памяти под массивы и ее освобождение.
Массивы указателей.
Двумерные и трехмерные массивы и их адресная арифметика.
АТД динамический массив.

Файловый ввод/вывод в языке С++.

АТД файл.
Файловые переменные и типы файлов. Режим использования файлов.
Стандартные файлы ввод/вывода (stdout, stdin, stderr).
Функции текстового ввода/вывода.
Функции бинарного вводавывода.

Обработка ошибок.

Общая проблема обработки ошибок.
Возврат кода ошибки.
Использование статуса.

5. Задачи поиска и анализ алгоритмов. Задача сортировки, алгоритмы и их реализация на С++.

Задачи поиска и оценки алгоритмов.

Задача поиска.
Линейный поиск.
Поиск в отсортированном массиве. Нерекурсивная и рекурсивная реализация бинарного поиска.
Сложность алгоритмов.
О-нотация.
Характеристики алгоритмов по сложности и требованиям к памяти.

Задача сортировки

Примеры алгоритмов и их характеристики (внутренняя и внешняя, неустойчивая и устойчивая сортировки).
Сортировка слиянием.
Быстрая сортировка Хоара.
Сортировка подсчетом.
Цифровая сортировка.

6. Пользовательские типы в С++ (структуры, перечисления). АТД: список. Реализация списков на С++.

Пользовательские типы

Структура
Перечисление
Массивы структур

Список. Реализация списка на С++.

Одно и двусторонние списки, кольцевые списки.
Реализация списка на языке С++. Списковая (фрагментированная) память. Структура узлов списка, содержащих указатели на узлы списка.
Списки со сторожевыми элементами.
Операции над списками (добавление/удаление элемента, создание/уничтожение списка, поиск).

7. АТД: очередь и стек. Реализация стеков и очередей на С++. Указатели на функции и их использование в С++. Сортировки в прикладных программах.

Стек (LIFO). Очередь (FIFO): простая и циклическая. Дэк.

Реализация очереди и стека в векторной (непрерывной) памяти.
Реализация очереди и стека в списковой (фрагментированной) памяти.
Двунаправленная очередь и ее реализация на двунаправленном списке.

Исключение рекурсии.

Указатели на функцию

Объявление и определение указателя на функцию.
Использование указателей на функции. Функции обратного вызова (call-back).
Массивы указателей на функции

Использование методов сортировки в прикладных программах на С++.

Функция быстрой сортировки в стандартной библиотеке.
Сортировка строк.
Сортировка "больших" структур данных.

8. Практика разработки ПО. Использование препроцессора. Модульное программирование: создание и использование библиотек. Утверждения, отладка и тестирование программ.

Практическое использование препроцессора.

Условная компиляция.
Константы времени компиляции.
Упаковка структур
Отключение предупреждений
Подмена функций с дополнительной диагностикой.

Модульное программирование.

Раздельная компиляция. Связывание (раннее и позднее).
Разделение интерфейса и реализации.
Бинарные интерфейсы модулей.
Стандартное устройство заголовочного файла.
Соглашения о порядке передачи параметров (cdecl).
Создание и использование библиотек.

Динамические библиотеки: создание и использование.

Адресное пространство процесса.
Статическая и динамическая линковка.
Изготовление объектных модулей.
Динамическая загрузка кода.

Приемы программирования.

Функция многих переменных.
POD и наследование структур.

Использование утверждений и макроса assert().

Защищенное программирование.
Предусловия. Постусловия. Инварианты.
Практические аспекты использования утверждений, макрос assert.

Приемы отладки и тестирования программ.

Трассировка.
Отладка.
Тестирование.

9. Бинарные отношения, таблицы и поиск по ключу. АТД: Хэш-таблицы. Алгоритмы разрешения коллизий и их реализация на С++.

Бинарное отношение (таблица).

Бинарное отношение.
Поиск по ключу.
Таблицы, хранящиеся как массивы структур. Оценки производительности различных стратегий поиска.

Хеш-функции и вычисление хеш-индекса по ключу:

метод деления
метод середины квадрата
мультипликативный метод
двойное хэширование.

Алгоритмы разрешения коллизий и их реализация на С++:

Открытая адресация с линейным опробыванием.
Метод цепочек (списки коллизий). Инициализация таблицы и поиск по ключу. Поиск в списке коллизий.

10. АТД дерево. Реализация дерева на С++. Обход дерева.

Дерево

Математическое понятие дерева.
Степени ветвления дерева.

Совершенные деревья и их определения.
Вырожденные деревья–списки.

Реализация дерева на языке С++.

Представление дерева с помощью массива.
Представление дерева списком сыновей.
Представление дерева по схеме "левый ребенок правый сосед".

Алгоритмы обхода дерева и их реализации на С++.

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

11. АТД: бинарное дерево. Деревья и поисковые структуры.

АТД бинарное дерево.

Деревья, упорядоченные относительно различных типов обхода.

Алгоритм создания дерева.
Алгоритм последовательного поиска в дереве.
Алгоритм удаления из дерева.
Оценка эффективности поиска по ключу.
Добавление и удаление вершин в совершенном упорядоченном бинарном дереве и проблема перевешивания его поддеревьев.

12. АТД: очередь с приоритетом. АТД множество. Реализация на С++.

АТД множество.

Реализация множеств в С++.

Реализация множеств с использованием двоичных векторов.
Реализация множеств с использование связных списков.
Реализация множеств как леса непересекающихся множеств и сжатие путей.

АТД очередь с приоритетом. Варианты реализаций.

Реализация очереди с приоритетами на основе массива.
Реализация очереди с приоритетами на основе неупорядоченных списков.
Реализация очереди с приоритетами на основе частично упорядоченных деревьев (пирамида).

13. АТД строка. Практические аспекты работы со строками. Поиск совпадения паттернов.

АТД строка.

Практическая работа со строками и локализация.

Кодовые страницы и юникод.
Представления строк (single byte, multi byte, wide char).
Локализация.
Функции стандартной библиотеки для работы со строками.

Совпадение паттернов:

Представление паттернов.
Простой определитель совпадения паттернов.

14. Поиск подстрок. Реализация алгоритмов поиска подстрок на С++.

Поиск подстрок.

Задача поиска подстрок.
Наивный алгоритм.

Эффективные алгоритмы поиска подстрок.

Алгоритм Рабина–Карпа /хэш подстроки/.
Алгоритм Кнута–Морриса–Пратта.

15. АТД граф. Реализация графов на С++. Алгоритмы поиска на графах.

Графы и способы их представлений на С++.

Математическое понятие графа.
Дуги с весами.
Матрица инциденций.
Списки смежных вершин.

Стратегии поиска, использующие дерево достижимости вершин.

Генерация дерева достижимости вершин.
Поиск в глубину. Использование стека для возврата из тупиков. Подсчет длины пути.
Полный перебор или поиск в ширину.

16. АТД разреженный массив. АТД мультисписок. Реализация разреженных массивов на С++. Слоеные списки.

Отношение "многие-ко-многим". АТД разреженный массив.

Способы реализации разреженных массивов на языке С++:

Представление разреженного массива массивом указателей.
Представление разреженного массива двусвязным списком.

Слоеные списки.

СПИСОК ЛИТЕРАТУРЫ

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

Шилдт Г. Полный справочник по С++, 4-е изд. – М.: Издательский дом «Вильямс», 2006.
Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд. – М.: Издательский дом «Вильямс», 2006.
Седжвик Р. Фундаментальные алгоритмы на С. – СПб.: ООО «ДиаСофтЮП», 2003.
Ахо А. В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. – М.: Издательский дом «Вильямс», 2000.

Дополнительная литература

ссылка скрыта. Язык программирования С++: Специальное издание, изд. 3-е, перераб. – М.: Бином, 2005.
Бентли Дж. Жемчужины программирования. 2-е издание. – СПб.: Питер, 2002.
Ниман Т. Краткое руководство по сортировке и поиску. Перевод П.Н. Дубнер. ссылка скрыта, ссылка скрыта

ЗАДАЧИ

(для разбора на семинарах)

Проверка числа на простоту.
Схема Горнера.
Нерекурсивное вычисление чисел Фибоначчи.
Поиск максимального элемента в массиве.
Инвертирование текстовой строки по месту.
Объединение текстовых строк.
Безопасное чтение из потоков.
Расчет простых статистических показателей.
Обработка матриц (сложение, вычитание, умножение).
Замена слов в текстовом файле.
Бинарный поиск.
Пузырьковая сортировка.
Сортировка пирамидой.
Сравнение характеристик алгоритмов.
Стек (на основе массива).
Программная библиотека (dll).
Многочлен (упорядоченный список).
Проверка скобочного выражения (стековая реализация).
Очередь (реализация кучей).
Локализация программы.
Создание и редактирование дерева.
Обход дерева и поиск ветвей с заданными параметрами.
Поиск подстрок.

ЗАДАНИЕ 1

(срок сдачи 13–17 октября)

Рекурсивное вычисление чисел Фибоначчи.

Реализовать консольное приложение, которое реализует нахождение N-го числа Фибоначчи и собирает статистику по рекурсивным вызовам. Числа Фибоначчи определяются соотношениями:

F_n = F_n_-1 + F_n_-2, F₁ = F₂ = 1.

Найденное число, максимальная глубина рекурсии и общее число рекурсивных вызовов выводится в консоль.

Указание по реализации: вычисления вести с помощью рекурсивных вызовов функции вычисления чисел Фибоначчи в соответствии с определением, для определения числа вызовов использовать статическую переменную уровня функции, для определения максимальной глубины рекурсии использовать статическую переменную уровня файла.

Расчет сумм значений функций в точках.

Написать консольное приложение для расчета суммы значений нескольких функций в некоторых точках. Параметры суммирования определяются в коде. Результат работы (параметры суммирования и таблица результатов) выводятся в консоль. В первом столбце таблицы строковое представлении суммируемой функции, а во втором столбце вычисленная сумма.

Указание по реализации: использовать массивы для хранения указателей на строковые представления суммируемых функций и указателей на сами суммируемые функции, для всех вариантов функций использовать общую функцию расчета и вывода суммы ряда, использовать указатель на функцию для передачи конкретной функции расчета члена ряда

Сортировка строк текстового файла

Реализовать консольное приложение, сортирующее строки текстового файла в лексикографическом порядке. Пути к входному и выходному текстовым файлам передаются через параметры командной строки. Если выходной файл уже существует, то он должен быть перезаписан. В случае любых проблем программа должна вывести соответствующее диагностическое сообщение (на английском языке) и завершить работу.

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

Указание по реализации: последовательно зачитывать строки из файла в динамически выделяемые фрагменты памяти параллельно формировать массив указателей на эти строки, отсортировать указатели в соответствии с лексикографическим порядком строк.

ЗАДАНИЕ 2

(срок сдачи 1–5 декабря)

Игра «угадай число».

Написать консольное приложения для игры “угадай число” со следующими правилами. Первый игрок загадывает число в диапазоне от 1 до N, второй называет числа от 1 до N и получает указание, является ли загаданное число больше или меньше. Игра заканчивается победой первого игрока, если второй отказался от продолжения. Игра заканчивается победой второго игрока, если он угадал число. В конце работы программы должен быть выведен итоговый результат (диапазон чисел, кто выиграл и почему, какое число было загадано, число попыток угадывания, общее время игры). Диапазон чисел определен в исходном коде программы. Компьютер может играть как за первого, так и за второго игрока.

Дополнительные требования: обратить внимание на корректность обработки вводимых данных, если вводимые данные некорректны, извещать об этом пользователя и продолжать игру.

Указание по реализации: реализовать выбор игрока за которого играет компьютер, стратегию игры за второго игрока реализовать с помощью бинарного поиска.

Библиотека «cтек».

Реализовать библиотеку (dll), позволяющую создавать, использовать и уничтожать стеки для целых чисел. Внутренняя реализация стека на основе связного списка. Дополнительно обеспечить в библиотеке возможность получения строкового представления текущего состояния заданного стека (значения элементов через запятую от верхнего к нижнему). Реализовать тестовое приложение, демонстрирующее возможности библиотеки.

Указание по реализации: для идентификации стеков использовать целые числа, которые присваиваются при создании, использовать явные функции инициализации и деинициализации библиотеки для захвата и освобождения ресурсов.

Вычисление арифметических выражений.

Написать консольную программу для вычисления арифметических выражений с целыми числами. Выражения состоят из цифр, знаков (‘+’, ’-‘, ’*’, ’/’), круглых скобок и пробелов. Выражение хранится в текстовом файле, путь к которому передается через параметры командной строки. Результаты работы программы (само выражение и результат вычисления) выводятся в консоль.

Указание по реализации: вычисления проводить в два этапа с использованием библиотеки стеков (задача 2), сначала реализовать преобразование выражения к обратной польской нотации (алгоритм Дейкстры или «сортировочная станция»), а затем вычислить записанное в обратной польской нотации выражение.

Исследование хэширующей структуры.

Написать консольное приложение для анализа зависимости суммарного числа столкновений и общего времени работы при добавлении в хэш-таблицу с открытой адресацией и двойным хешированием N случайных ключей K_i при размере таблицы T. Провести анализ эффективности двойного хеширования. Результатом работы является статистика для различных N и T при различных хеш-функциях.

Указание по реализации: для анализа двойного хеширования использовать h₂(K) = 0 и h₂(K) = K.

Blog