Программа Языки и технологии программирования

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования «Уральский государственный университет им. А.М. Горького»

Математико-механический факультет

Кафедра информатики и процессов управления

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

ЯЗЫКИ И ТЕХНОЛОГИИ ПРОГРАММИРОВАНИЯ

Программа дисциплины (Стандарт ОПД.Ф.15)

Екатеринбург

2010

2

I. Введение

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

2.Задачи дисциплины: обучающийся должен освоить способы представления данных, методы построения алгоритмов решения задач различных классов, выработать навыки разработки алгоритмов, работы в различных средах программирования, решения учебных задач на компьютере в некоторой современной среде. Практическое использование знаний по алгоритмизации требует изучения средств описания алгоритмов решения задач. Первым языком программирования выбран язык Си++. Этот язык отличается с одной стороны простотой и логичностью структуры, доступностью реализации и литературы. В то же время, язык Си часто рассматривается как профессиональный и его изучение позволяет глубже освоить синтаксис и семантику процедурных языков программирования высокого уровня. В третьем семестре рассматривается язык Java. Ставится задача освоить основные понятиф ООП на примере двух языков программирования: С++ и Java. В итоге студенты должны познакомиться с важнейшими шаблонами построения программных систем и получить навыки работы в рамках программных проектов среднего размера.

3.Место дисциплины в системе высшего профессионального образования

Вкачестве основы для дисциплины «Языки и технологии программирования используются школьные знания обучаемых, некоторые знания из курсов

введение в информатику (большинство тем курса),

скрипты (ряд классических алгоритмов и подходов к программированию),

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

аналитической геометрии (расстояние между точками, уравнение плоской прямой, уравнение окружности, преобразование системы координат);

линейной алгебры (линейное пространство, вектор, скалярное и векторное произведения векторов, матрица, определитель матрицы, ранг матрицы, система

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

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

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

приобрести навыки в способах представления данных задач в алгоритмах их решения,

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

приобрести навыки в разработке алгоритмов решения задач,

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

3

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

5.Методическая новизна курса

Использование презентаций для проведения части лекций

Наличие различных электронных материалов поддержки курса, например, часть констпектов лекций, примеры программ, литература в электронном виде

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

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

Использование большого архива задач и проверяющей системы http://acm.timus.ru, поддерживаемой сотрудниками УрГУ

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

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

1. Разделы курса, темы, их краткое содержание

1 семестр

1.Понятие алгоритма решения задачи.

Свойства, характеристики алгоритмов (емкостная, временная сложности). Способы записи алгоритмов. Этапы разработки алгоритма.

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

2.Общие сведения о языке Си. Алфавит, лексика, синтаксис, семантика языка. Общая сруктура записи программы. Комментарии.

3.Понятие типа данных. Основные положения концепции типов данных. Совместимость типов. Преобразования типов.

4.Целые, вещественный типы и работа с ними. Описание констант и переменных.

5.Выражения в Си. Понятие оператора, операции.

Приоритет операций. Префиксные и постфиксные операции.

6.Логические переменные и выражения. Условный оператор. Оператор выбора.

7.Циклические алгоритмы. Виды циклов. Кратные циклы. Замена одного цикла другим.

4

8.Массивы. Описание, инициализация, использование. Двумерные массивы. Передача массивов в функции. Связь массивов и указателей.

9.Понятие ссылок. Работа с ними. Использование в функциях.

10.Указатели. Понятие адреса. Операция разыменования.

11.Функции в Си.

Место и способ описания. Вызов на выполнение. Механизм обмена данными. Прототипы. Формальные и фактические параметры.

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

12.Тип char. Работа с символами.

13.Работа со строками. Особенности инициализации и хранения. Основные функции для обработки строк.

Преобразование символьной информации в числовую и наоборот.

14.Алгоритмы поиска: линейный поиск, поиск с барьером,

двоичный (бинарный) поиск: 2 варианта.

15.Понятие хэш-функции.

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

16.Алгоритмы сортировки: сoртировка выбором, обменом (с модификациями),

включением (разные способы поиска места включения), сортировка Хоара (быстрая сортировка).

(для каждого алгоритма оценка его вычислительной сложности). Сортиpовка по упорядочивающей функции. Многокритериальная сортировка.

Применение вектора индексов к любому алгоритму сортировки.

17.Рекурсия (явная и неявная). Понятие глубины рекурсии.

18.Алгоритмы формирования перестановок. Рекурсивный вариант.

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

19.Ввод-вывод информации. Работа с клавиатурой и экраном. Работа с файлами.

Контроль ошибок ввода-вывода.

5

2 семестр

1. Системы счисления(СС).

Алфавит, база и основание СС. Условия корректности задания СС. Правила перехода от CC с основанием P к СС с основанием Q:

-P произвольное, Q = 10;

-P = 10, Q произвольное;

-P = R^n, Q = R^m;

-P и Q произвольные, используя СС P или Q.

-Работа с периодическими дробями. Примеры программ:

-перевод десятичного числа в СС с основанием P.

-перевод числа из СС с основанием P<10 в десятичную.

-перевод целого десятичного числа в двоичную СС с

2. Внутреннее представление чисел.

- Хранение целых чисел. Прямой и дополнительный код. Диапазоны. - Хранение действительных чисел. Нормализованный вид числа.

Мантиса и порядок. Оценка точности и диапазона.

- Особенности машинной арифметики: набор аварийных ситуаций.

3. Побитовые операции - Операции & | ^ << >>

- Тип union - Тип struct

4. Алгоритмы - Алгоритм быстрого возведения в степень.

- Представление множеств с использованием побитовых операций - Перебор подмножеств данного множества.

- Сортировка слиянием.

5. Абстрактные типы данных.

-Процедуры для работы с памятью: new, delete

-Динамическое выделение памяти (основные принципы)

-Понятия: Стек, Очередь Дэк.

-Создание и использование односвязных и двусвязных списков.

-Циклические списки.

-Организация АТД на основе массивов и динамических списков.

-Организация данных типа "дерево".

6. Дополнительные алгоритмы.

- Топологическая сортировка. (с помощью бинарного дерева) - Пирамидальная сортировка.

- Понятие графа, способы задания графов.

- Алгоритмы поиска в ширину и в глубину на графах.

7. Основы объектно-ориентированного программирования

- Тип class

- Отличия public и private

- Понятие конструктора, деструктора - Константные методы

6

-Статические поля и методы

-Динамические поля классов и динамическое объекты

-Поверхностное и глубинное копирование, конструктор-копировщик.

-Перегрузка операций (унарные, бинарные, присваивание)

-Операторы преобразования типов.

3 семестр

1. История появления ООП.

Рассматривается краткая история развития языков программирования от ассемблеров до современных языков, поддерживающих объектно-ориентированный подход к программированию. Обсуждаются причины появления новых языков программирования.

2. Основы языка Java.

Рассматриваются основные вопросы, связанные с написанием программ на языке Java (синтаксические конструкции для описания объектов, базовые конструкции для управления ходом выполнения программы, встроенные типы данных).

3. Основные понятия ООП.

Рассматриваются понятия инкапсуляции, программных абстракций, интерфейсов и полиморфизма. Изучаются базовые шаблоны: неизменный объект, интерфейс, суперкласс, делегирование.

4. ООП и структурированная обработка ошибок.

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

5. Библиотеки ввода-вывода.

Рассматриваются библиотеки потокового ввода-вывода. Обсуждаются вопросы, связанные с представлением текстовой информации в памяти машины. Вводится понятие кодировки символов, рассматриваются кодировки Unicode и UTF-8. На примере библиотеки ввода-вывода платформы Java рассматривается шаблон фильтр.

6. Библиотеки контейнеров.

Рассматриваются стандартные библиотеки контейнеров, предлагаемые языками C++ (STL) и Java. Сравниваются подходы организаций этих библиотек на C++ (шаблоны) и Java (абстракции-обобщения, generics). На примере коллекций рассматривается шаблон итератор.

7. Управление памятью.

Рассматриваются механизмы управления памятью в C++ и Java. Исследуются сложности управления памятью в C++. Изучается работа сборщика мусора в Java. Сравнивается влияние подходов управления памятью на быстродействие программ.

8. Событийно управляемые программы.

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

7

2. Темы лабораторных, семинарских занятий и коллоквиумов

1.Линейные алгоритмы. Арифметические и логические выражения. Счет по формуле. Оптимизация линейных алгоритмов. Чтение данных от пользователя, выдача информации для пользователя.

2.Алгоритмы с развилками. Оператор if. Оптимизация развилок. Развилки по многим направлениям.

3.Элемент алгоритма – цикл. Виды циклов. Операторы используемые для описания циклов. Оптимизация циклов. Кратные циклы.

4.Вспомогательные алгоритмы.

5.Литерный, строковый типы. Строковое выражение. Обработка строковой информации. Оператор switch.

6.Перечисляемый, ограниченный типы. Тип массив. Использование типа для представления информации.

7.Использование массивов.

8.Задача поиска.

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

10.Работа с файлами. Создание и обработка файлов.

11.Командная строка. Параметры командной строки. Их использование в программе.

12.Ссылочный тип – средство увеличения объема информации, обрабатываемой программой.

13.Типы динамической структуры (ТДС) и их представление средствами языка С++. Представление ТДС на основе одномерного массива (размещенного в динамической переменной), на основе связанного списка динамических переменных.

14.Рекурсивные процедуры и функции.

15.Знаккомство с внутренним представлением данных.

16.Потоковый ввод-вывод.

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

Java.

18.Процедурное программирование на Java.

19.Наследование и полиморфизм.

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

21.Использование библиотеки контейнеров.

22.Потоковый ввод-вывод в C++ и Java.

23.Безопасное управление памятью в C++.

24.Создание собственной реализации контейнера.

25.Реализация декодера текстовых файлов (автоподбор русской кодировки).

26.Использование фабрик классов.

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

1.Разработка циклических программ на примере обработки значений целого типа.

2.Процедуры и функции.

3.Обработка строковой информации. Выделение фрагментов текста.

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

5.Массивы.

6.Задачи поиска, сортировки.

7.Использование файлов для хранения информации.

8.Ссылочный тип.

9.Связанные списки динамических переменных.

8

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

11.Использование алгоритмов с возвратом, поиска в графе в глубину/ширину для решения задач.

12.Использование шаблонов и библиотек классов.

4. Примерный перечень вопросов к экзамену (зачету)

1.Счет по формулам.

2.Вычисление значения функции, задаваемой несколькими формулами.

3.Решение квадратного уравнения, системы линейных алгебраических уравнений 2 порядка с исследованием возможных ситуаций.

4.Выбор наибольшего, наименьшего из 2, 3 значений. Упорядочивание значений 2, 3 величин.

5.Поиск с точностью ерs предела последовательности.

6. .Вычисление сумм, произведений конечного числа членов, с точностью ε бесконечного числа членов. Особенности обработки рекуррентных последовательностей.

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

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

9.Работа с целыми данными: проверка делимости N на K, проверка числа на простоту, разложение числа на простые множители, выделение значений цифр в p-ичной записи числа, поиск нок(а,в), нод(а,в).

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

11.Обработка значений сложных типов. Представление комплексных чисел. Действия над комплексными числами. Представление объектов задачи в алгоритме (точек плоскости, окружностей, треугольников, N-угольников, полиномов, абитуриентов, студентов, книг,

...). Полином, его представление, вычисление значения (схема Горнера) полинома. Операции над полиномами (сложение, умножение, деление, интегрирование, дифференцирование полиномов, поиск НОК, НОД).

12.Вектор, его представление. Действия над векторами (сумма векторов, скалярное произведение векторов, нормирование вектора. Проверка вектора на обладание некоторым свойством,...). Вектор записей. Вектор окружностей, треугольников,...

13.Представление матриц. Матрица – совокупность строк/столбцов. Операции над матрицами. Поиск в матрице. Треугольные, симметрические, диагональные матрицы. Cпециальные матрицы. Вектор из матриц, векторов, слов, строк, полиномов,....

14.Решение систем линейных алгебраических уравнений. Поиск обратной матрицы, ранга матрицы. Получение характеристического полинома матрицы.

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

16.Возведение в степень. Возведение в целую степень, основанное на двоичном представлении показателя степени.

17.Вычисление с точностью eps приближенного значения корня уравнения f(x)=0, отделенного промежутком [a,b], методами половинного деления, хорд, касательных.

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

9

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

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

21.Данные динамической структуры и их представление на основе

-одномерного массива,

-связанного списка динамических переменных.

Использование типов динамической структуры при решении задач

-с разреженными полиномами,

-с разреженными матрицами,

-с много разрядными числами,

-c накоплением слов текста,...

22.Рекурсивные алгоритмы (N!, поиск НОД, вычисление определителя, числа Фибоначчи, Ханойcкие башни, генерирование перестановок,...). Рекурсивное и циклическое описания алгоритмов.

23.Основные понятия ООП. Инкапсуляция. Примеры применения.

24.Основные понятия ООП. Абстракции, интерфейсы и полиморфизм.

25.Наследование и делегирование, как способы повторного использования кода.

26.Наследование и делегирования: существенные различия в шаблонах и в использовании.

27.Шаблон "неизменный класс". Применение в ядре Java.

28.Библиотека контейнеров. Реализации интерфейса List в Java.

29.Библиотека контейнеров. Реализация интерфейса Map в Java.

30.Библиотека контейнеров. Использование обобщенных типов (generics) в Java.

31.Контейнерные шаблоны в STL.

32.Библиотека ввода-вывода в Java. Отличия Reader-ов от Stream-ов.

33.Шаблон "фильтр". Примеры применения.

34.Множественное наследование в C++. Сложности применения.

35.Управление памятью в C++ и Java. Проблемы и решения.

36.Зачем нужны символьные кодировки. Примеры использования.

37.Шаблоны "фабричный метод" и "абстрактная фабрика". Примеры использования.

38.Шаблон "одиночка". Примеры использования.

39.Шаблон "итератор". Примеры использования.

40.Шаблон "адаптер". Примеры использования.

41.Событийно-управляемые программы.

42.Шаблон "наблюдатель".

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

№	Наименование	ВСЕГО	Аудиторные занятия			Самостоятельная
п/п	разделов и тем	(часов)		(час)		работа
				в том числе
			Лекции		Практические
					(семинары,
					лабораторные
					работы)
1	Данные и алгоритмы.	124	36		72	25
	Язык С (основные
	конструкции).
	Семестр 1.
2	Данные и алгоритмы.	118	34		51	25

10