Geum.ru

Программа курса «Программирование на языке высокого уровня»

Вид материалаПрограмма курса

Содержание


1.3Требования к уровню освоения содержания курса.
1.4Формы контроля
Текущий контроль
2Содержание дисциплины. 2.1Новизна.
2.2Тематический план курса.
Всего часов
2.3Содержание отдельных разделов и тем.
2.4Перечень примерных контрольных вопросов и заданий для самостоятельной работы. 3Учебно-методическое обеспечение дисциплины
3.2Образцы вопросов для подготовки к экзамену.
3.3Список основной и дополнительной литературы.
Подобный материал:

Кафедра общей информатики ФИТ НГУ

Программа курса «Программирование на языке высокого уровня»

2003-2004 учебный год

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

1.1Название курса.


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

Направление - 552800 Информатика и вычислительная техника.

Раздел – обще профессиональные дисциплины

Компонент - ОПД.Ф.05 федеральный.

1.2Цели и задачи курса.


Цели курса:
  • Совершенствование владения языками программирования высокого уровня и техникой программирования;
  • знакомство с типовыми задачами программирования и основными моделями и методами их решения.


Задачи курса:
  • освоить язык программирования С;
  • дать представление информации в ЭВМ и различных структур данных, способы кодирования информации;
  • представить способы программирования: итерационный, рекурсивный, полного перебора и с отсечением, динамического программировния;
  • рассмотреть такие важные понятия, как перестановки, поиск, сортировки, оценить сложность рассмотренных алгоритмов;
  • научить оценивать объем требуемой для реализации памяти и быстродействие программ.



1.3Требования к уровню освоения содержания курса.


По окончании изучения указанной дисциплины студент должен


иметь представление

о различных стилях программирования;

о способах оценки объема памяти и быстродействия программ.

способах кодирования информации в ЭВМ.


знать

все основные конструкции и стандартные функции языка С;

основные структуры данных и способы их реализации;

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


уметь

реализовать представленные методы и алгоритмы на языке С;

уметь использовать стандартные функции языка С;

владеть техникой раздельной компиляции, отладчиком и другими возможностями системы Visual C++.

1.4Формы контроля


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

1 семестр – дифференцированный зачет

2 семестр - экзамен и зачет

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

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

2.1Новизна.


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

2.2Тематический план курса.


1 семестр


Наименование разделов и тем
К о л и ч е с т в о ч а с о в


Лекции

Семинары
Лаборатор-

ные работы
Самостоятель-ная работа
Всего

часов

Понятие программы, выполнение программы
3
3
3
3
12

Язык программирования <<С>>
3
3
3
3
12

Простые типы данных языка <<С>>
3
3
3
3
12

Выражения
3
3
3
3
12

Функции
3
3
3
3
12

Операторы
3
3
3
3
12

Массивы
3
3
3
3
12

Указатели
3
3
3
3
12

Структуры и перечисления
3
3
3
3
12

Списки
3
3
3
3
12

Графы
3
3
3
3
12

Деревья
3
3
3
3
12

Итого по курсу:
36
36
36
36
144


2 семестр


Наименование разделов и тем
К о л и ч е с т в о ч а с о в


Лекции

Семинары
Лаборатор-

ные работы
Самостоятель-ная работа
Всего

часов

Оценка сложности вычислительных алгоритмов
2
1






3

Общие методы решения вычислительных задач
4
4



2
10

Перестановки набора
2
2



2
6

Задачи поиска и сортировки (П/С)
4
4



2
10

Классические модели динамической памяти
2
4



2
8

Абстрактные структуры данных
4
4



2
10

Алгоритмы перебора на абстрактных динамических структурах
6
6



2
14

Элементы теории языков
2
1



2
5

Элементы теорий вероятностей, информации и кодирования
4
6



4
14

Итого по курсу:
32
32
0
18
82



2.3Содержание отдельных разделов и тем.


1 семестр:
  • Понятие программы, выполнение программы

Этапы создания программ. Проектирование. Написание исходного текста. Компиляция исходного текста. Сборка. Тестирование и отладка.
  • Язык программирования <<С>>

Общие сведения, область применения.
  • Простые типы данных языка <<С>>

Простые типы данных. Ограничения на основные типы данных. Машинное представления данных.

Системы исчисления (представление чисел). Инициализация и константы.
  • Выражения

Выражения и подвыражения. Типы выражений. Преобразование типов. Операции над объектами различных типов данных.

Понятие логического выражения. Приоритеты операций.
  • Функции

Понятие функции. Параметры функции. Возвращаемое значение функции. Неопределённое число передаваемых

параметров. Время жизни и область видимости переменных. Рекурсия.
  • Операторы

Понятие оператора. Условные операторы (if, switch). Операторы цикла (for, while, do while, break, continue).

Оператор возврата (return). Условный оператор (?:).
  • Массивы

Определение массива в языке <<С>>. Многомерные массивы. Обращение к массивам.

Инициализация массива. Строки в языке <<С>>.
  • Указатели

Определение и понятие указателя на область памяти. Тип указателя. Индексация указателей и арифметика указателей. Связь понятия массивов и указателей.
  • Структуры и перечисления

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

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

Понятие графа. Представления и реализация графа.
  • Деревья

Деревья и их реализация. Применение деревьев.


2 семестр:
  • Оценка сложности вычислительных алгоритмов

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

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

Перестановки и инверсии. Число инверсий, как мера сложности упорядочения набора; таблицы инверсий; алгоритм восстановления перестановки по таблице инверсий; таблица инверсий как число в особой с.с.; итерационный алгоритм генерации всех таблиц инверсий. Алгоритмы перебора перестановок: рекурсивный, итерационный (через перебор таблиц инверсий), итерационный с лексикографическим упорядочением.
  • Задачи поиска и сортировки (П/С)

Постановка задач П/С записей в произвольном наборе данных, внешняя и внутренняя постановка задачи П/С (при не/доступности всего набора). Методы простого поиска в массиве: линейный поиск, бинарный поиск, оценки сложности. Методы поиска подстроки в строке: алгоритм прямого перебора, алгоритм Бойера-Мура, Рабина-Карпа, оценки сложности. Методы сортировки массива: метод простого подсчета для различных чисел; метод простых вставок; метод бинарных вставок; метод простого выбора; метод пузырька»; шейкер-сортировка; метод Шелла; быстрая сортировка Хоара; пирамидальная сортировка; сортировка слиянием; оценки сложности. Достоинства организации исходного набора в виде древовидной структуры для совместного решения задач П/С.
  • Классические модели динамической памяти

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

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

Модели представления в ЭВМ: матрицы смежности и инцидентности, динамическая структура со списками дуг, табличное представление. Дерево, как частный вид графа. Классические типы деревьев: корневые, бинарные, упорядоченные, уравновешенные. Алгоритмы включения и удаления, сравнение их эффективности с известными алгоритмами на массивах.
  • Алгоритмы перебора на абстрактных динамических структурах

Способы перебора. Итерационный, полный, с отсечением. Примеры. Классические задачи на графах: транзитивное замыкание, задача коммивояжера (размеченные дуги), раскраска графа (размеченные вершины). Алгоритмы с возвратом. Классические задачи с отсечением: задача о рюкзаке, обход шахматной доски. Обходы деревьев (в ширину, в глубину, в пре/пост/инфиксном порядке, слева направо). Обход всех вершин графа - метод поиска в глубину. Эйлеров граф. Способ определения Эйлерова цикла. Потоки в сетях, алгоритмы Форда-Фалкерсона и Кинга-Пратта. Алгоритм поиска максимального потока методом поднятия вершин. Паросочетания, поиск максимальных паросочетаний.
  • Элементы теории языков

Символьные формализмы для описания синтаксиса языков (БНФ, РБНФ, синтаксические диаграммы) Формальные грамматики. Классификация грамматик по Хомскому. Синтаксический анализатор. Нисходящий и восходящий разбор. Полный перебор правил подстановки. Определение языков с помощью автоматов.
  • Элементы теорий вероятностей, информации и кодирования

Модель информационной системы Шеннона. Алфавит источника как формализация языка сообщений. Кодирование как преобразование сообщения при переходе в среду с другим алфавитом. Среднестатистическая информационная емкость сообщений для эргодических источников с заданным распределением частот символов. Формулы Шеннона и Хартли для удельной емкости на символ. Код как функция взаимнооднозначного отображения алфавитов. Типы кодирования Проблемы однозначного декодирования. Избыточность кодирования.Метод Хафмана построения кода с минимальной избыточностью.

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

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

3.1Темы курсовых работ.

  • Разработка и реализация архиватора на основе метода Хаффмана.

3.2Образцы вопросов для подготовки к экзамену.

  • Препроцессор языка С. Включаемые файлы. Макроопределения и условная компиляция.
  • Оценка сложности вычислительных алгоритмов. Классы вычислительной сложности алгоритмов. Нижние и верхние оценки для изученных классов задач.
  • Функции с переменным числом параметров. Получение переменных передаваемых после фиксированных параметров.
  • Рекурсия как общий метод сведения задачи к самой себе. Ветвящаяся рекурсия.
  • Функции printf, sprintf, fprintf. Форматная строка (целые знаковые и беззнаковые в десятичном и шестнадцатеричном виде, числа с плавающей запятой, буквы, строки).
  • Рекурсивный алгоритм перебора перестановок.
  • Строки в языке С. Понятие длины строки. Статическая инициализация строк. Функции работы со строками: определение длины строки, копирование строк, слияние строк.
  • Постановка задач поиска и сортировки записей в произвольном наборе данных, внешняя и внутренняя постановка задачи. Методы простого поиска в массиве: линейный поиск, бинарный поиск, оценки сложности.
  • Понятие времени жизни и области видимости переменных. Глобальные и локальные переменные. Модификаторы области видимости и времени жизни.
  • Понятие указателя. Операции над указателями. Индексация указателей (два способа). Функции работы с динамической памятью.
  • Функции. Описание функций. Возвращаемые значения. Передаваемые параметры. Порядок передачи параметров через стек.
  • Методы сортировки массива, имеющие оценку O(n2).
  • Понятие типа выражения. Преобразование типов. Структуры. Синтаксис описания структур. Обращение к полям структур для объектов и к полям по указателю на объект типа структура. Статическая инициализация структур.
  • Список, как универсальная модель линейно упорядоченных структур данных последовательного доступа. Разновидности списков.
  • Понятие указателя. Операции над указателями. Индексация указателей (два способа). Функции работы с динамической памятью.
  • Б-деревья, алгоритмы включения новых вершин.



3.3Список основной и дополнительной литературы.

    1. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов.
    2. Вирт Н. Алгоритмы + Структуры Данных = Программы.
    3. Дейкстра Э. Дисциплина программирования.
    4. Керниган Р. Язык «С».
    5. Кнут Д. Искусство Программирования для ЭВМ. Т.1. Основные алгоритмы.
    6. Кнут Д. Искусство Программирования для ЭВМ. Т.3. Сортировка и Поиск.
    7. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.
    8. Программирование на языке С: Учебное пособие. Тамбов: Тамбовский гос. Университет, 1996.
    9. Скопин И.Н. Основы конструирования программ и языки программирования.
    10. Цикоза В.А.,Чурина Т.Г. Методическое пособие к курсу «Методы программирования»



3.4Для изучения дисциплин, которые предусматривают использование нормативно-правовых актов, указывать источник опубликования.


Не предусмотрено.