uzluga.ru
добавить свой файл
КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

им. А.Н. ТУПОЛЕВА


УТВЕРЖДАЮ:

Проректор по учебной и методической

работе

_________________ И.К. Насыров


«_____» _______________ 2007__ г.


ПРОГРАММА ДИСЦИПЛИНЫ




СД.03 “Программирование и структуры данных


Рекомендуется УМЦ КГТУ им. А.Н. Туполева для направления

(специальности)


Направления: 230200 “Информационные системы”


Специальности: 230201 “Информационные системы и технологии”

Формы обучения: очная



  1. Цели и задачи дисциплины.



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

Дисциплина базируется на знаниях элементарной математики.


  1. Требования к уровню освоения содержания дисциплины.


После изучения введения в программирование студенты долж­ны иметь представление:

- о проблемах и направлениях развития системных пpогpамм­ных средств;

- о современных языках программирования, их области пpиме­нения и особенностях;

знать:

- современные методы и средства pазpаботки алгоритмов и пpогpамм, приемы стpуктуpного пpогpаммиpования, способы записи алгоpитма на базовом языке высокого уpовня.

В качестве базового языка используется язык С/С++.

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

После изучения методов программирования студенты должны знать способы эффективной реализации абстрактных стpуктуp дан­ных и комбинаторные алгоритмы, уметь описывать их на базовом языке.

На лабораторных занятиях студенты осваивают работу в системе программирования на ба­зовом языке и получают навыки разработки и отладки программ.

После курсовой работы студенты должны знать:

- этапы пpоизводства пpогpаммного пpодукта, методы и сpедства тестиpования пpогpамм, способы отладки, испыта­ния и документиpования пpогpамм;

иметь опыт:

- выбоpа технологии и инстpументальных сpедств, на их основе pазpаботки, составления, отладки, тестиpования и доку­ментиpования пpогpаммы на языках высокого уpовня для задач обpаботки числовой и символьной инфоpмации.



  1. Объем дисциплины и виды учебной работы.


Для очной формы обучения:


Виды учебной работы

Всего часов

Семестры

1

2

3



Общая трудоемкость дисциплины


272

94

111

67



Аудиторные занятия


136

51

68

17



Лекции


51

17

34

0




Практические занятия (ПЗ)

34

17

0

17




Семинары (С)
















Лабораторные работы (ЛР)

51

17

34

0




и (или) другие виды аудиторных занятий















Самостоятельная работа


136

43

43

50




Курсовой проект (работа)

50

0

0

50



Расчетно-графические работы
















Реферат

















или другие виды самостоятельной работы

86

43

43

0




Вид итогового контроля (зачет, экзамен)




Зачет

Экзам.

Зачет







  1. Содержание дисциплины.




    1. Тематический план






Пп

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

Лекции

ПЗ

(или С)

ЛР




Часть 1. Введение в программирование

*

*

*

1

Основные понятия

*

*

*

2

Проектирование программы

*

*

*

3

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

*

*

*




Часть 2. Методы программирования

*

*

*

4

Представление структур данных

*

*

*

5

Структуры данных

*

*

*

6

Основные комбинаторные алгоритмы

*

*







    1. Содержание тем.


Часть 1. Введение в программирование

(очное: 25 ч. лек./ 50 ч. сам.; )

Тема 1. Основные понятия (очное: 1 ч. лек./2 ч. сам.)


Цели и задачи курса. Роль курса в подготовке бакалавра и инженера. Понятие алгоритма. Способы записи алгоритма. Операция, операнд, оператор (команда).

Алгоритмический (вычислительный) процесс. Процессор.

Языки программирования и их классификация. Процедурно-ориентированные и машинно-ориентиро­ванные языки. Программа на языке высокого уровня. Система программирования. Транслятор, компилятор, интерпретатор. Текстовый редактор. Компоновщик (редактор связей).


Тема 2. Проектирование программы (очное: 8 ч. лек./ 10 ч. сам.)


Основные этапы решения задач на ЭВМ (жизненный цикл прог­раммы): проектирование программы (постановка задачи и специфи­кация программы, алгоритмизация - разработка алгоритма и структуры данных); программирование; отладка и сопровождение программы.

Критерии качества программы: надежность, эффективность, дружественность, мобильность и др. Диалоговые программы. Выбор языка программирования. Стиль программирования. Читаемость, комментарии. Программирование с защитой от ошибок.

Способы представления алгоритма: графический, таблич­ный, текстовый.

Схема алгоритма. Основные символы: "процесс", "решение", "пуск-останов", "комментарий","ввод-вывод". Правила оформления схем алгоритмов.

Структурное программирование. Теорема структуры. Базовые структуры: последо­вательность, ветвление, повторение (цикл), подпрограмма. Вос­ходящая и нисходящая поэтапная разработка структурированных алгоритмов.

Подпрограммы, процедуры и функции. Формальные и факти­ческие параметры. Модульное программирование.

Рекурсия и рекурсивные определения. Рекурсия и итерация как методы описания повторяющихся процессов. Рекурсивные алго­ритмы.

Тестирование. Трассировочная таблица. Способы конструирования и верификации (доказательства правильности) программ. Анализ программ. Утверждения о программах; инвариантные утверждения; правила вывода для основных программных структур.


Тема 3. Программирование на базовом языке (языке С)

(очное: 16ч. лек./19ч. сам.)

Язык-объект и метаязык.

Основные характеристики базового языка. Алфавит языка. Правила записи и структура программы. Комментарий. Константы. Переменные. Типы данных. Описания констант, переменных, типов. Стандартные типы данных: целый, вещественный, символьный, логи­ческий, их представление в памяти. Выражения. Стандартные функции. Присваивание. Ввод-вывод данных.

Запись базовых структур алгоритма на базовом языке (представление основных управляющих структур программирования). Ус­ловный оператор. Составной оператор. Операторы циклов с пре­дусловием и с постусловием. Цикл с параметром. Программирова­ние структурированных алгоритмов. Корректность программ.

Нестандартные типы данных. Указатели (ссылки). Перечислимый тип.

Массивы и их описание. Индексированные переменные. Использование одномерных и двумерных массивов. Представление массивов в памяти. Утверждения о массивах.

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

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

Программирование рекурсивных алгоритмов. Рекурсивные функции.

Структура программы. Область действия имен. Статическое и динамическое распределение памяти. Области динамического распределения памяти: стек и куча.

Символьные строки и библиотечные функции обработки строк. Записи (структуры); файлы; индуктивные функции на последовательностях (файлах, массивах).


Часть 2. Методы программирования

(очное: 26 ч. лек.,/ 36 ч. сам.)

Тема 4. Представление структур данных

(очное: 6 ч. лек./ 9 ч. сам.)


Программа как алгоритм плюс данные. Данные, структура данных, элемент, поле (реквизит). Уровни описания структуры данных: функциональный, логический и физический. Средства представления структур данных в языках программирования (записи, "па­раллельные" массивы).

Методы и структуры хранения данных. Последовательное (сплошное) представление данных. Вектор. Доступ к элементам вектора по их индексу (номеру).

Связанное (цепное) представление данных. Динамические структуры данных. Список (связанный). Виды списков: простой, циклический, симметричный (двусторонний). Списковая структура (список списков). Доступ к элементам списка, включение и исключение элементов. Средства организации списков в языках программирования. Организация списков с помощью ссылочных переменных. Организация списков с помощью "параллельных" массивов. Распределение памяти (управ­ление памятью) для списков, cписок свободной памяти. Многосвязный список (сеть).


Тема 5. Структуры данных

(очное: 12 ч. лек./16 ч. сам.)


Определение, применение и методы представления абстрактных структур данных: множество, линейные списки (стек, очередь, дек - двусторонняя очередь, строка - цепочка символов, "string",), дерево и бинарное дерево, граф. Реализация основных операций над абстрактными структурами данных. Обход дерева и графа.

Массив. Хранение прямоугольных массивов. Отображающий вектор. Доступ к элементам массива. Определяющий вектор. Хранение непрямоугольных массивов. Разреженные массивы и их хра­нение. Организация массивов в языках программирования.


Тема 6. Основные комбинаторные алгоритмы

(очное: 8 ч. лек./11 ч. сам.)


Поиск данных. Типы таблиц: статическая и динамическая, внутренняя и внешняя. Основные операции над таблицами: инициа­лизация, поиск, включение, исключение, изменение, перебор. Последовательный (линейный) поиск. Просматриваемые упорядочен­ные и неупорядоченные таблицы в виде вектора и списка. Упорядочение элементов по частоте использования.

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

Алгоритмы исчерпывающего поиска с возвращением (бэктрекинг). Алгоритмы порождения комбинаторных объектов: сочетаний, перестановок, подмножеств множества.



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




№ пп

№ темы

Наименование лабораторных работ

Объем в часах







Очное








1




Работа в системе программирования на языке С

2






2





Программирование простейших циклов на языке С

4





3




Обработка числовых последовательностей

4





4




Последовательная обработка символов

4






5




Обработка массивов

4





6




Функции

4







7




Символьные строки и функции обработки строк

4






8




Работа с файлами

4





9




Организация списков с помощью ссылочных данных

8





10




Графы

4





12




Стеки

4






13




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

5









    1. Курсовая работа, ее содержание.


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



    1. Методические указания по самостоятельной работе


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

Поэтому в билетах для зачета и экзамена не требуется пе­ресказывать теоретический материал, все вопросы сформулированы в виде задач. Изучение предмета должно ориентироваться не на запоминание, а на понимание рассматриваемых методов.

Содержание лекционного курса полностью изложено в пособиях [1, 2, 7, 8]. В пособиях [3, 4, 7, 8, 10] рассматриваются многочисленные примеры решения типовых задач, даются упражнения и задачи для самостоятельного решения. Пособие [5] содержит материал, необходимый для выполнения лабораторных работ. В по­собиях [2, 6 - 8] даются подробные рекомендации по изучению программи­рования и разработке сложных программ. Пособия [1 - 8] содержат также основной материал, не­обходимый для выполнения курсовой работы и изучения смежных дисциплин..

Базовым языком программирования в насто­ящее время является язык С/C++. Однако основное содержание курса мало привязано к этому языку. Все основные рассматриваемые ме­тоды и алгоритмы достаточно просто выражаются и на других язы­ках. Поэтому, вместо C/C++, в качестве базового языка, в частности при самостоятельном изучении предмета, возможно использование других универсальных процедурных языков, наиболее подходящим из которых является Pascal. Тем не менее необходимо определен­ное знакомство с языком С, которое используется в преподавании смежных дисциплин.



  1. Учебно-методическое обеспечение дисциплины.




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


а) Основная литература:


1. Хохлов Д.Г. Введение в программирование: Учебное посо­бие.- Казань: Изд-во Казан. техн. ун-та, 2005. - 136 с.

2. Хохлов Д.Г. Структуры данных и комбинаторные алгоритмы. Учебное пособие. - Казань: Изд-во Казан. техн. ун-та, 2006. - 100 с.

3. Хохлов Д.Г., Захарова З.Х. Введение в программирова­ние. Практикум на языке С: Учебное пособие. - Казань: Изд-во Казан. техн. ун-та, 2006. - 96 с.

4. Хохлов Д.Г., Захарова З.Х. Практикум по структурам данных и комбинаторным алгоритмам: Учебное пособие.- Казань: Изд-во Казан. техн. ун-та, 2005. - 48 с.

5. Бикмурзина А.Р. Лабораторный практикум по программированию. - Казань: КГТУ, 2000г.

6. Хохлов Д.Г. Основы технологии модульного программирования. Учебное пособие. - Казань. Изд-во Казан. техн. ун-та , 2005. - 64 с.

7. Хохлов Д.Г. Программирование на языке высокого уровня. Часть 1: Основы программирования: Учебник. - Казань: Кафедра АСОИУ, 2007. - 248 с.

8. Хохлов Д.Г. Программирование на языке высокого уровня. Часть 2: Методы программирования: Учебник. - Казань: Мастер Лайн, 2006. - 266 с.

9. Павловская Т.А. С/С++. Программирование на языке высокого уровня. - СПб: Питер, 2004. - 461с.

10. Павловская Т.А., Щупак Ю.А. С/С++. Структурное программирование: Практикум. - СПб: Питер, 2002. - 240с.


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


11. Керниган Б., Ритчи Д. Язык программирования Си.- М.: Финансы и статистика, 2002. - 279 с.

12. Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1985. - 406 с.

13. Липский В. Комбинаторика для программистов. - М.: Мир, 1988.- 213 с.

14. Кормен Т., Лейзерсон Ч., Ривест Р.Алгоритмы: построение и анализ. - М.: МЦНМО, 2000. - 960 с.

15. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные ал­горитмы. Теория и практика. - М.: Мир, 1980. - 476 с.

16. Гудман С., Хидетниеми С. Введение в разработку и ана­лиз алгоритмов. - М.: Мир, 1981. - 368 с.

17. Кнут Д. Искусство программирования на ЭВМ. Т. 1. Ос­новные алгоритмы. - М.: Мир, 1976. - 735 с., Т. 3. Сортировка и поиск. - М.: Мир,1979. - 844 с.

18. Холл П. Вычислительные структуры. Введение в не­численное программирование. - М.: Мир, 1978. - 214 с.

19. Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ.- М.: Наука, 1986. - 272 с.



  1. Материально-техническое обеспечение дисциплины.


Персональные компьютеры, система программирования базового языка (Visual C++, Borland C++ или Turbo C ).


Программу составили:


Хохлов Д. Г., к.т.н., доцент каф. АСОИУ

Бикмурзина А. Р., ст. преп. каф. АСОИУ

Захарова З.Х. , доцент. каф. АСОИУ


Программа обсуждена и одобрена на заседании кафедры _________


«____» ______________200__г., протокол №_____.


Зав. кафедрой ________Л.М. Шарнин

(подпись) Ф.И.О.


Председатель Учебно-методической ________В.А. Суздальцев

комиссии факультета (подпись) Ф.И.О.


Декан факультета ________Л.Ю. Емалетдинова

(подпись) Ф.И.О.