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

МИНОБРНАУКИ

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ИНФОРМАТИКИ

УТВЕРЖДАЮ

Декан факультета

« » 2010 г.

ОСНОВЫ ПРОГРАММИРОВАНИЯ

(ЕН. Ф.2.01)

РАБОЧАЯ ПРОГРАММА

трудоемкость дисциплины 6 зачетных единиц

НАПРАВЛЕНИЕ 010400 – ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ

Томск

2010

УТВЕРЖДЕНО кафедрой теоретических основ информатики. Протокол №05/10 от 01.01.2001 Зав. кафедрой, профессор

СОСТАВИТЕЛЬ д. т.н., зав. кафедрой теоретических основ информатики

I. Организационно-методический раздел

Цель курса – обучение началам профессионального программирования.

Задача учебного курса. Студент должен научиться программировать на профессиональном уровне с использованием алгоритмических языков Си и Паскаль.

Дисциплины-предшественники. Для изучения курса требуется знание математики и информатики в объеме программы общеобразовательной средней школы.

Требования к уровню освоения дисциплины. Студент должен знать: языки программирования Си и Паскаль, основные базовые алгоритмы на этих языках, методы доказательства правильности и исследования трудоемкости программ, методы тестирования. Студент должен уметь: разрабатывать программы умеренной сложности, их тестировать, проводить исследование трудоемкости, доказывать правильность.

II. Содержание курса

II.1.  Лекционный курс

1. Программирование на языке Паскаль

Трансляция и выполнение программы на языке Паскаль. Арифметические и символьные переменные, константы в Паскале, операции над ними, присваивание значений. Стандартные средства ввода и вывода. Логические значения, переменные, операции над ними. Условные и выбирающие операторы, циклы с параметром и с условием. Массивы. Описание типа в Паскале. Процедуры и функции, их вызов и описание. Подстановка параметров по значению, по ссылке. Символьные переменные, строки, операции над ними. Структуры (записи), действия над ними. Управление процессом трансляции, использование стандартных библиотек. Стандартные математические функции, датчик случайных чисел.

2. Основные алгоритмы и их трудоемкость

Трудоемкость алгоритмов. Вычисление рекуррентных последовательностей, сумм, произведений. Вычисление полинома по схеме Горнера. Поиск корня функции методом дихотомии. Минимальные и максимальные элементы в массиве. Простые алгоритмы упорядочения элементов в массиве. Косвенная упорядоченность. Упорядочение массивов строк. Поиск элементов в массиве. Дихотомический алгоритм поиска, его трудоемкость. Алгоритм слияния упорядоченных массивов.

3. Рекурсивные алгоритмы

Простые рекурсивные функции. Локальные и глобальные переменные. Выполнение рекурсивного алгоритма с помощью стека. Глубина рекурсии. Трудоемкость рекурсивных алгоритмов. Рекурсивный алгоритм генерации перестановок чисел, его трудоемкость. Рекурсивный алгоритм сортировки слиянием, его трудоемкость и глубина рекурсии. Алгоритм “Ханойские башни”.

4. Файлы в Паскале. Взаимодействие с операционной системой

Файлы в операционной системе. Файловая система, действия над файлами. Стандартные файлы ввода и вывода в Паскале. Переназначение стандартных файлов. Текстовые файлы, их описание, открытие, ввод и вывод, закрытие. Двоичные файлы. Прямой доступ к двоичным файлам. Стандартные процедуры и функции для работы с файлами и файловой системой. Выполняемая программа с параметрами. Обработка параметров. Программа из модулей, трансляция программы по частям.

5. Указатели и распределение памяти

Тип указатель. Указатель на массив. Операторы выделения и аннулирования памяти. Работа с динамическими массивами. Списочные структуры. Выделение и удаление элементов списка. Моделирование списков с помощью массивов. Реализация стека и очереди с помощью списка, с помощью массива.

6. Алгоритмы над множествами и графами

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

7. Алгоритмы с векторами и матрицами

Действия с векторами и матрицами: сложение, умножение, скалярное произведение. Вычисление определителя приведением матрицы к диагональному виду. Определение ранга матрицы. Решение системы линейных уравнений методом Гаусса с выбором главного элемента. Решение системы для недоопределенной и переопределенной матрицы.

8. Диалоговые программы

Библиотека процедур и функций для работы с консолью и экраном. Вывод символов в определенное место на экране. Коды основных и расширенных (управляющих) символов, их ввод. Алгоритм диалога с использованием меню. Прокрутка текста на экране. Цвет на экране. Задание цвета символов и цвета фона.

9. Графический вывод

Графическая библиотека процедур и функций в Паскале. Режим VGA, графическое разрешение, цвет. Включение/выключение графического режима. Рисование отрезков, закрашивание фигур. Задание цвета, типа линии. Рисование текста.

10. Программирование на языке Си

Трансляция, редактирование и выполнение программы на языке Си. Арифметические и символьные переменные, константы в Си, операции над ними, присваивание значений. Стандартные средства ввода и вывода. Логические и битовые значения, операции над ними. Условные и выбирающие операторы, циклы с параметром и с условием. Указатели и массивы. Процедуры и функции, их вызов и описание. Подстановка параметров по значению, по ссылке. Структуры (записи), действия над ними. Описание типа. Структура программы, макросы. Управление процессом трансляции, использование стандартных библиотек. Библиотека стандартных математических функций. Символьные переменные, строки, библиотека функций для выполнения над ними операций. Файлы, библиотека функций для работы с ними. Библиотека функций распределения памяти. Библиотеки функций для взаимодействия с DOS и с файловой системой. Библиотека для работы с консолью и экраном. Графическая библиотека в Си.

11. Тестирование и отладка программ

Технологический процесс разработки программы. Задачи тестирования. Создание тестов. Пошаговая отладка. Исчерпывающее тестирование и его ограничения. Принцип черного ящика. Тестирование методом белого ящика. Тестирование по частям.

12. Доказательство правильности программ

Вход и выход алгоритма. Пред - и постусловие алгоритма. Доказательство завершимости алгоритма. Методы доказательства правильности: последовательный просмотр, перебор вариантов, математическая индукция. Использование абстракции при доказательстве вложенных алгоритмов. Доказательство сверху-вниз и снизу-вверх. Доказательство рекурсивных алгоритмов. Использование пред - и постусловия при тестировании.

13. Разработка больших программ

Программный продукт. Программная документация. Этапы разработки программного продукта. Проект системы. Проектирование и разработка сверху-вниз и снизу-вверх. Использование заглушек. Одновременное проектирование, разработка и тестирование. Независимое тестирование. Тестирование документации. Организационные проблемы создания больших программных систем. Система на выброс. Эффект второй системы. Бригадный метод организации труда при создании программного продукта.

14. Объектно-ориентированное программирование

Модульное программирование. Модульное программирование в Паскале и Си. Парадигмы объектно-ориентированного программирования. Описание классов в Паскале и Си. Примеры объектно-ориентированных программ.

15. Программирование на языке C++.

Понятие класса, понятие объекта. Инкапсуляция: спецификаторы public, protected, private. Функции-друзья, классы-друзья (спецификатор friend). Наследование, множественное наследование. Полиморфизм, виртуальные функции. Конструкторы и деструкторы. Перегрузка функций и операторов. Параметры функций по умолчанию. Ссылки, отличие ссылок от указателей. Потоки ввода/вывода С++. Обработка исключений (try/catch). Работа с памятью с помощью операторов new и delete. Шаблоны.

II.2.  Лабораторный практикум

1.  Итеративное вычисление бесконечных сумм.

2.  Перевод чисел из одной системы счисления в другую.

3.  Алгоритмы сортировки.

4.  Основы организации пользовательского интерфейса.

5.  Построение графиков функций.

6.  Последовательности данных.

7.  Комбинаторные алгоритмы.

8.  Алгоритмы обработки символьных данных.

9.  Алгоритмы на графах.

10.  Алгоритмы линейной алгебры.

Программирование на языке C++.

11.  Решение квадратных уравнений.

12.  Организация ввода-вывода переменных величин разного типа.

13.  Обработка одномерных массивов. Сортировка и поиск в массиве.

14.  Задачи с переменными файлового типа.

15.  Двумерные массивы. Сортировка и поиск в таблице.

16.  Списки.

17.  Задачи с объектами "строка".

18.  Задачи с объектами "матрица".

III. Распределение часов курса по темам и видам работ

№№ пп	Наименование тем	Всего часов	Аудиторные занятия (час), в том числе	Самостоятельная работа
			лекции	семинары	лабораторные занятия
1	Программирование на языке Паскаль	12	6			6
2	Основные алгоритмы и их трудоемкость	12	8			4
3	Рекурсивные алгоритмы	12	6			6
4	Файлы в Паскале. Взаимодействие с операционной системой	4	2			2
5	Указатели и распределение памяти	6	4			2
6	Алгоритмы над множествами и графами	20	10			10
7	Алгоритмы с векторами и матрицами	34	18			16
8	Диалоговые программы	4	2			2
9	Графический вывод	4	2			2
10	Программирование на языке Си	8	4			4
11	Тестирование и отладка программ	4	2			2
12	Доказательство правильности программ	6	4			2
13	Разработка больших программ	4	2			2
14	Объектно-ориентированное программирование	18	8			10
15	Программирование на языке C++	56	30			26
	Лабораторные работы на языке Паскаль	144			144
	Лабораторные работы на языках С и C++	36			36
ИТОГО		384	108		180	96

IV. Учебно-методическое обеспечение курса

IV.1.  Основная литература

1.  Захаров программирование. – Томск: Изд-во НТЛ, 2007. – 296 с.

2.  Костюк программирования. Разработка и анализ алгоритмов: Учебное пособие. – Томск: Изд-во Томского ун-та, 2004.

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

1.  Microsoft Software Developer Network Library – July 2005.

2.  Алгоритмы + структуры данных = программы. – М.: Мир, 1985.

3.  Систематическое программирование. – М.: Мир, 1975.

4.  Дисциплина программирования. – М.: Мир, 1978, 275 c.

5.  , Епанешников в среде Turbo Pascal 7.0. – 3-е изд., стер. – М.: ДИАЛОГ-МИФИ, 1995.

6.  , Вальвачев программирование на языке Си: от Turbo C до Borland C++. Справочное пособие. – Минск: Высшая школа, 1992.

7.  Теория графов. Алгоритмический подход. – М.: Мир, 1978.

8.  , Фомин на языке Си. – Москва: Финансы и статистика, 1999. – 600 с.

9.  Язык Си. Руководство для начинающих. – М.: Мир, 1988.

10.  Программирование на BORLAND C++ для профессионалов. – Мн.: , 1999. – 800 с.

IV.3.  Программное обеспечение лабораторного практикума

Интегрированная среда разработки Lazarus 0.9.22 для компилятора Free Pascal.

Интегрированная среда разработки Microsoft Visual C++ 2005.