Поиск по базе сайта:
Рабочая программа по курсу Программирование icon

Рабочая программа по курсу Программирование




Скачати 184.87 Kb.
НазваРабочая программа по курсу Программирование
Дата конвертації02.02.2013
Розмір184.87 Kb.
ТипРабочая программа

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ


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

УТВЕРЖДАЮ

Декан факультета информатики

_________________ С.П. Сущенко

« » 2010 г.


ПРОГРАММИРОВАНИЕ

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


Специальность 351500 – МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ И АДМИНИСТРИРОВАНИЕ ИНФОРМАЦИОННЫХ СИСТЕМ


Статус дисциплины:

федеральный компонент специальности

Томск - 2010 г.

ОДОБРЕНО кафедрой теоретических основ информатики


Протокол №05/10 от 01.09.2010


Зав. кафедрой, профессор _________________Ю.Л.Костюк


РЕКОМЕНДОВАНО методической комиссией факультета информатики


Председатель комиссии, профессор _____________________ Б.А.Гладких


“___”_____________2010 г.


Рабочая программа по курсу “Программирование” составлена на основе требований Государственного образовательного стандарта высшего профессионального образования по специальности 351500 – МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ И АДМИНИСТРИРОВАНИЕ ИНФОРМАЦИОННЫХ СИСТЕМ, утвержденного 10 марта 2000 г. Общий объем курса 312 часов. Из них: лекции – 66 часов, лабораторные занятия – 166 часов, самостоятельная работа студентов – 80 часов. Зачет в первом, втором, третьем семестре. Общая трудоемкость курса 8,8 зач. ед.


СОСТАВИТЕЛЬ:

Костюк Юрий Леонидович – доктор технических наук, заведующий кафедрой теоретических основ информатики



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

Выписка

из Государственного образовательного стандарта высшего профессионального образования по специальности 351500 – МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ И АДМИНИСТРИРОВАНИЕ ИНФОРМАЦИОННЫХ СИСТЕМ (квалификация – математик-программист).
^

ОПД.Ф.01 Программирование


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

  1. ^ Цель курса

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

  1. Задача учебного курса

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

  1. Требования к уровню освоения курса

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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


13. Технология программирования


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

Контрольные вопросы

1. Трудоемкость алгоритмов

2. Вычисление рекуррентных оследовательностей, сумм, произведений

3. Вычисление полинома по схеме Горнера

4. Поиск корня функции методом дихотомии

5. Минимальные и максимальные элементы в массиве

6. Простые алгоритмы упорядочения элементов в массиве

7. Косвенная упорядоченность

8. Упорядочение массивов строк

9. Поиск элементов в массиве

10. Дихотомический алгоритм поиска, его трудоемкость

11. Алгоритм слияния упорядоченных массивов

12. Простые рекурсивные функции. Выполнение рекурсии с помощью стека

13. Рекурсивный алгоритм генерации перестановок чисел, его трудоемкость

14. Рекурсивный алгоритм сортировки слиянием, его трудоемкость.

15. Алгоритм “Ханойские башни”

16. Текстовые файлы, их описание, открытие, ввод и вывод, закрытие

17. Стандартные процедуры и функции для работы с файлами и файловой системой

18. Выполняемая программа с параметрами. Обработка параметров

19. Программа из модулей, трансляция программы по частям

20. Работа с динамическими массивами

21.Списочные структуры. Выделение и удаление элементов списка

22. Моделирование списков с помощью массивов

23. Реализация стека и очереди с помощью списка, с помощью массива

24. Представление множества в виде логического (битового) массива

25. Вычисление мощности множества, объединения, пересечения, разности множеств

26. Множество в виде массива упорядоченных номеров, алгоритмы над ним

27. Представление графа матрицей смежности или матрицей расстояний.

28. Представление графа массивом списков ребер

29. Алгоритм просмотра графа вширь для обоих способов представления.

30. Рекурсивный алгоритм просмотра графа вглубь и его трудоемкость

31. Алгоритм топологического упорядочения вершин графа и его трудоемкость

32. Действия с векторами и матрицами: сложение, умножение, произведение

33. Вычисление определителя приведением матрицы к диагональному виду

34. Определение ранга матрицы

35. Решение системы линейных уравнений методом Гаусса

36. Решение системы для недоопределенной и переопределенной матрицы

37. Тестирование методом черного ящика

38. Тестирование методом белого ящика

39. Методы доказательства правильности: перебор вариантов, матиндукция

40. Использование абстракции при доказательстве вложенных алгоритмов

41. Доказательство сверху-вниз и снизу-вверх

42. Доказательство рекурсивных алгоритмов

43. Использование пред и постусловия при тестировании

44. Программный продукт. Программная документация

45. Этапы разработки программного продукта

46. Проектирование и разработка сверху-вниз и снизу-вверх. Заглушки

47. Одновременное проектирование, разработка и тестирование

48. Независимое тестирование. Тестирование документации

49. Организационные проблемы создания больших программных систем

50. Бригадный метод организации труда при создании программного продукта

Контрольные задания

1. Дан массив Х из n числовых элементов. Написать алгоритм нахождения самой длинной группы подряд идущих упорядоченных по возрастанию элементов массива (вычислить номер начального и номер конечного элемента такой группы). Алгоритм должен состоять из одного цикла (а также нескольких других операторов – присваиваний, условных). Записать инвариант и доказать правильность алгоритма.


2. Дан массив Х из n числовых элементов и число d. Написать алгоритм, который переставляет в массиве Х элементы, равные d, в начало массива, а все остальные – в конец массива Х (при этом должен быть вычислен номер последнего из элементов, равного d, в переставленном массиве). Алгоритм должен состоять из одного цикла (а также нескольких других операторов – присваиваний, условных). Записать инвариант и доказать правильность алгоритма. Нельзя использовать другой массив.


3. Дан массив Х из n упорядоченных по возрастанию числовых элементов. Написать алгоритм нахождения самой длинной группы подряд идущих элементов массива с одинаковым значением (вычислить номер начального и номер конечного элемента такой группы). Алгоритм должен состоять из одного цикла (а также нескольких других операторов – присваиваний, условных). Записать инвариант и доказать правильность алгоритма.


4. Дан массив Х из n упорядоченных по возрастанию числовых элементов и число d. Написать алгоритм, который переставляет в массиве Х элементы, не равные d, подряд в начало массива и вычисляет их количество. Алгоритм должен состоять из одного цикла (а также нескольких других операторов – присваиваний, условных). Записать инвариант и доказать правильность алгоритма. Нельзя использовать другой массив.


5. Дан упорядоченный массив Х из n числовых элементов и упорядоченный массив Y из m числовых элементов. Написать алгоритм вычисления симметрической разности этих элементов в массиве Z. Алгоритм должен состоять из одного цикла (и нескольких других операторов – присваиваний, условных). Записать инвариант и доказать правильность алгоритма.


6. Дан упорядоченный массив Х из n числовых элементов и упорядоченный массив Y из m числовых элементов. Написать алгоритм слияния всех этих элементов в массиве Z. Алгоритм должен состоять из одного цикла (а также нескольких других операторов – присваиваний, условных). Записать инвариант и доказать правильность алгоритма.


7. Дан упорядоченный массив Х из n числовых элементов и упорядоченный массив Y из m числовых элементов. Написать алгоритм вычисления разности множеств элементов Х и Y в массиве Z. Алгоритм должен состоять из одного цикла (и нескольких других операторов – присваиваний, условных). Записать инвариант и доказать правильность алгоритма.


8. Дан упорядоченный массив Х из n числовых элементов и упорядоченный массив Y из m числовых элементов. Написать алгоритм объединения всех этих элементов в массиве Z. Алгоритм должен состоять из одного цикла (а также нескольких других операторов – присваиваний, условных). Записать инвариант и доказать правильность алгоритма.

9. Дан упорядоченный массив Х из n числовых элементов и упорядоченный массив Y из m числовых элементов. Написать алгоритм пересечения всех этих элементов в массиве Z. Алгоритм должен состоять из одного цикла (а также нескольких других операторов – присваиваний, условных). Записать инвариант и доказать правильность алгоритма.

10. Простейший алгоритм упорядочивания (сортировки) из одного цикла и одного IF. Доказательство правильности, трудоемкости. Его усовершенствование для уменьшения трудоемкости.

11. Алгоритм сортировки методом выбора максимального элемента. Доказательство правильности, трудоемкости.

12. Алгоритм сортировки массива методом слияния. Доказательство правильности, трудоемкости, глубины рекурсии.

13. Алгоритм дихотомического поиска. Доказательство правильности, трудоемкости.

14. Алгоритм слияния двух упорядоченных массивов в один. Доказательство правильности, трудоемкости.

15. Алгоритм решения игры «Ханойские башни». Доказательство правильности, трудоемкости.

16. Алгоритм обменной сортировки. Доказательство правильности, трудоемкости (в худшем и в лучшем случаях).

17. Алгоритм слияния двух упорядоченных списков в один список. Доказательство правильности, трудоемкости.

18. Алгоритм сортировки списков методом слияния. Доказательство правильности, трудоемкости, глубины рекурсии.

19. Рекурсивный алгоритм генерации всех возможных перестановок из n чисел. Доказательство правильности, трудоемкости.


20. Рекурсивный алгоритм генерации всех возможных сочетаний из n чисел по m. Доказательство правильности, трудоемкости.

Лабораторные работы

1. Напишите программу с использованием оператора CASE, которая вводит число от 0 до MAXLONGINT и выводит это число прописью с указанием единицы измерения.

2. Написать программу, которая переводит целое положительное число, заданное в Р-ичной системе счисления в Q-ичную систему счисления. Для ввода чисел в системе счисления с основанием Р использовать цифры от 0 до Р-1 и вводить их через пробел. Для вывода чисел в Q-ичной системе счисления использовать цифры от 0 до Q-1 и выводить их тоже через пробел. Ограничение: исходное число в диапазоне longint, Q и Р от 2 до 10000.

3. Написать программу, которая:
· вводит множество некоторого заранее не известного количества символов в массив;
· преобразует данные к представлению в виде логического массива;
· исходное множество символов упорядочивается по убыванию;
· исходное множество преобразуется в переменную множественного типа;
· из представления в виде переменной множество опять преобразуется к логическому массиву.
Каждое преобразование должно сопровождаться выводом данных в соответствии с имеющимся представлением.

4. Напишите программу, которая:
· вводит дуги неориентированного графа, строит матрицу смежности и выводит ее на экран;
· используя матрицу смежности, строит двумерный массив всех дуг и выводит его на экран;
· используя построенный массив всех дуг, строит списки смежных вершин и выводит их на экран;
· упорядочивает построенные списки смежных вершин по убыванию и выводит результат на экран;
· используя матрицу смежности, строит списки смежных вершин, упорядоченные по убыванию номера смежной вершины.

5. Написать программу, которая содержит процедуры выполнения следующих операций над множествами целых чисел:
· объединение
· пересечение
· разность
· симметрическая разность
· дополнение (универсум: 1.2....,М).

6. Написать программу генерации перестановок (использовать рекурсивную процедуру) и сочетаний.

7. Написать программу, которая строит график заданной функции с возможностью масштабирования изображения, запрашивает интервал изоляции корня и находит этот корень методом дихотомии.

8. Написать программу вычисления определителя порядка n методом Гаусса.

9. Написать программу вычисления определителя порядка n методом Лапласа.

10. Написать программу обращения матрицы размера n*n по определению. Если определитель матрицы равен

0, вывести сообщение об этом. Предусмотреть проверку правильности результата.

11. Программа решения системы из n линейных уравнений с m неизвестными
методом Гаусса. Предусмотреть варианты:
а) единственное решение;
б) нет решений;
в) множество решений. В этом случае программа должна вывести формулы вычисления значений зависимых неизвестных по независимым и запросить ввод значений независимых неизвестных. По введенным данным вычисляется частное решение.

12. Программа определения эйлерова пути и цикла в графе. Если в графе обнаружен эйлеров цикл, выводится сообщение об этом.


13. Написать программу обращения матриц методом Гаусса.

14. Написать программу обращения матриц методом Фадеева.

15. Написать программу поиска гамильтонова пути в ориентированном графе.

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





Наименование тем

Всего часов

Аудиторные занятия (час)

Самостоя-

тельная










в том числе

работа










лекции

семинары

лабора-торные

занятия




1

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

26

4




14

8

2

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

52

8




34

10

3

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



28

6




14

8

4

Файлы в Паскале. Взаимодействие с ОС системой

20

4




12

4

5

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

22

4




12

6

6

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

40

8




24

8

7

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

38

8




22

8

8

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


18

4




10

4

9

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

18

2




12

4

10

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

20

6




6

8

11

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

14

4




6

4

12

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

12

6






6

13

Технология программирования

4

2






2

ИТОГО




312

66



166

80

^ IV. Форма итогового контроля


Теоретический зачет и зачет по лабораторным работам


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


1. Брукс Ф. мл. Как проектируются и создаются программные комплексы. Мифический человеко-месяц. – М.: Мир, 1976.
2. Костюк Ю. Л. Основы алгоритмизации: Учебное пособие. – Томск: Изд-во Томского ун-та, 1996.
3. Епанешников А. М., Епанешников В. А. Программирование в среде Turbo Pascal 7.0. – 3-е изд., стер. – М.: ДИАЛОГ-МИФИ, 1995.
4. Уэйт М., Прата С., Мартин Д. Язык Си. Руководство для начинающих. – М.: Мир, 1988.
5. Касаткин А. И., Вальвачев А. М. Профессиональное программирование на языке Си: от Turbo C до Borland C++. Справочное пособие. – Минск: Высшая школа, 1992.
6. Вирт Н. Систематическое программирование. – М.: Мир, 1975.



Схожі:




База даних захищена авторським правом ©lib.exdat.com
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації