Введение в теорию алгоритмов и

АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ

Методические указания и задания

К выполнению контрольной работы

для студентов заочной формы обучения

Направление 09.03.03 Прикладная информатика

Профиль «Прикладная информатика в информационной сфере»

введение в теорию алгоритмов и - student2.ru

Чита

УДК 681.5

ББК 32.81

Г 64

Методические указания и задания к выполнению контрольной работы для студентов заочной формы обучения направления 09.03.03Прикладная информатика профиль «Прикладная информатика в информационной сфере»составлены доцентом кафедры прикладной информатики ЗИП СибУПК Л. Г. Гомбоевым в соответствии с требованиями Федерального государственного образовательного стандарта высшего профессионального образования.

Рецензент: старший преподаватель кафедры прикладной информатики ЗИП СибУПКЮ. Е. Хохлова.

Методические указания и задания к выполнению контрольной работы для студентов заочной формы обучения направления 09.03.03Прикладная информатика профиль «Прикладная информатика в информационной сфере» обсуждены на заседании кафедры прикладной информатики ЗИП СибУПК. Протокол № 5 от 20.01.2012.

Рекомендованы к переизданию на заседании кафедры прикладной информатики ЗИП СибУПК.

Протокол № 9 от 09.04.2015.

Методические указания и задания к выполнению контрольной работы обсуждены и рекомендованы к переизданию советом экономического факультета ЗИП СибУПК.

Протокол № 8 от 29.04.2015.

Г 64Введение в теорию алгоритмов и алгоритмические языки : методические указания и задания к выполнению контрольной работы для студентов заочной формы обучения : направление 09.03.03Прикладная информатика профиль «Прикладная информатика в информационной сфере»/ Л. Г. Гомбоев. – Чита : ЗИП СибУПК, 2015. – 32 с.

УДК 681.5

ББК 32.81

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ……………………………………………………
1.	Общие положения…………………………………………
	1.1. Цель и задачи дисциплины, ее место в учебном процессe………………………………………………
	1.2. Требования к уровню освоения содержания дисциплины…………………………….
2.	Основные вопросы курса………………………………….
3.	Методические указания по самостоятельному изучению тем…………………….
4.	Правила выполнения и оформления контрольной работы……………………..
5.	Правила выбора варианта…………………………………
6.	Методические указания по выполнению контрольной работы………………………
7.	Задания контрольной работы……………………………...
БИБЛИОГРАФИЧЕСКИЙ СПИСОК………………………

ВВЕДЕНИЕ

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

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

ОБЩИЕ ПОЛОЖЕНИЯ

«Введение в теорию алгоритмов и алгоритмические языки» – одна из основополагающих дисциплин направления 09.03.03Прикладная информатика профиль «Прикладная информатика в информационной сфере». Она дает студентам необходимые знания, способствующие успешному изучению дисциплин, относящихся к проектированию и организации компьютерной обработки данных и внедрению автоматизированных геоинформационных технологий в различных сферах человеческой деятельности.

1.1. Цель и задачи дисциплины,

Ее место в учебном процессе

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

Основными задачами при изучении дисциплины «Введение в теорию алгоритмов и алгоритмические языки» являются:

- освоение основных алгоритмов обработки данных;

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

- изучение основных структур данных и алгоритмов их обработки;

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

Дисциплина «Введение в теорию алгоритмов и алгоритмические языки» относится к базовой части цикла Б.2.В.02 направления 09.03.03Прикладная информатика профиль «Прикладная информатика в информационной сфере».

Изучение дисциплины «Введение в теорию алгоритмов и алгоритмические языки» является основой для дальнейшего изучения дисциплин «Программирование», «Операционные системы», «Базы данных», «Программная инженерия».

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

содержания дисциплины

В результате изучения дисциплины «Введение в теорию алгоритмов и алгоритмические языки» студент должен:

знать:

- конструкции языка программирования высокого уровня;

- основные структуры данных;

- алгоритмы сортировки и поиска данных;

- базовые концепции парадигм объектно-ориентированного и параллельного программирования.

Уметь:

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

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

Иметь навыки:

- разработки программ на языке высокого уровня;

- проектирования инфологических и семантических моделей данных.

ОСНОВНЫЕ ВОПРОСЫ КУРСА

Тема 1. Общее понятие алгоритма.

Управляющие конструкции алгоритмического языка.

Понятие переменной

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

Тема 2. Основные конструкции программирования

Алфавит, синтаксис и семантика языка программирования. Средства определения синтаксиса: расширенные формулы Бэкуса-Наура (РБНФ), синтаксические диаграммы. Классификация языков программирования по уровню абстракции. Обзор основных элементов языка программирования высокого уровня.

Тема 3. Теория алгоритмов

Интуитивное определение алгоритма. Основные свойства алгоритмов. Понятие исполнителя алгоритма. Основные методы разработки алгоритмов. Формальное определение алгоритма. Машина Тьюринга. Операции над машинами Тьюринга. Тезис Тьюринга. Нормальные алгоритмы Маркова. Принцип нормализации Маркова. Понятия самоприменимости алгоритма и алгоритмической неразрешимости.

Тема 4. Рекурсия

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

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

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

Тема 6. Сортировка

Внутренняя сортировка (сортировка массивов). Понятие сложности алгоритма сортировки. Основные алгоритмы внутренней сортировки: пузырьковая сортировка, шейкерная сортировка, сортировка простым выбором, сортировка простыми вставками, сортировка Шелла, сортировка слиянием, быстрая сортировка. Внешняя сортировка (сортировка файлов). Отрезки файла. Операции разделения файла и слияния файлов. Некоторые алгоритмы внешней сортировки: многофазная сортировка, сбалансированное слияние. Использование алгоритмов внутренней сортировки в сортировке последовательных файлов.

Тема 7. Поиск

Поиск в массиве. Линейный поиск. Бинарный поиск. Поиск в таблице. Хеширование. Выбор хеш-функции. Разрешение коллизий: метод открытой адресации, метод цепочек.

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

Парадигма объектно-ориентированного программирования (ООП): концепции объекта и класса, инкапсуляции, наследования и полиморфизма. Спецификация видимости атрибутов и методов объекта. Механизмы раннего и позднего связывания. Статические и виртуальные методы. Иерархии классов. Шаблоны классов.

Тема 9. Событийное программирование

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

Событийно-управляемое программирование. Пользовательские и системные события в программе. Методы обработки и распространение событий. Управление параллелизмом с помощью механизма обработки событий. Прикладной программный интерфейс (Application Programming Interface), API-программирование. Методы обработки данных, основанные на компонентных технологиях. Промежуточное программное обеспечение (middleware).

Тема 10. Параллельные вычислительные технологии

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

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

ПО САМОСТОЯТЕЛЬНОМУ ИЗУЧЕНИЮ ТЕМ

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

Тема 1. Общее понятие алгоритма.

Управляющие конструкции алгоритмического языка.

Понятие переменной

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

При изучении данной темы следует обратить внимание на источники: [1], [2].

Контрольные вопросы для самопроверки:

1. Понятие алгоритма. Свойства.

2. Формы записей алгоритмов.

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

4. Основы алгебры логики.

5. Законы логических операций. Таблицы истинности.

Тема 2. Основные конструкции программирования

При изучении данной темы следует обратить внимание на источники: [1], [2], [3].

Контрольные вопросы для самопроверки:

1. В чем состоит расширенный формализм Бэкуса-Наура (РБНФ)?

2. Синтаксис и семантика языка программирования Компонетный Паскаль.

3. Приведите классификацию языков программирования по уровню абстракции.

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

Тема 3. Теория алгоритмов

Интуитивное определение алгоритма. Основные свойства алгоритмов. Понятие исполнителя алгоритма. Основные методы разработки алгоритмов. Формальное определение алгоритма. Машина Тьюринга. Операции над машинами Тьюринга. Тезис Тьюринга. Нормальные алгорифмы Маркова. Принцип нормализации Маркова. Понятия самоприменимости алгоритма и алгоритмической неразрешимости.

При изучении данной темы следует обратить внимание на источники: [1], [2], [3].

Контрольные вопросы для самопроверки:

1. Дайте формальное определение понятию алгоритма. Как работает машина Тьюринга?

2. Какие операции допустимы над машиной Тьюринга?

3. Определите нормальный алгоритм Маркова.

4. В чем состоит принцип нормализации Маркова?

5. Поясните понятие самоприменимости и алгоритмической неразрешимости.

Тема 4. Рекурсия

При изучении данной темы следует обратить внимание на источники: [1], [2], [3].

Контрольные вопросы для самопроверки:

1. Дайте определение понятию рекурсии.

2. Приведите примеры рекурсивного определения.

3. Поясните реализацию перебора с возвратом с помощью рекурсии.

4. Сравните рекурсию с итерацией.

5. Поясните алгоритм обхода бинарного дерева.

6. Как реализуются операции по обработке бинарных деревьев?

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

При изучении данной темы следует обратить внимание на источники: [1], [2], [3].

Контрольные вопросы для самопроверки:

1. Определите абстрактный тип данных.

2. Приведите классификацию фундаментальных структур данных.

3. Дайте определение типу записи.

4. Как определяется тип список?

5. Поясните редактирование списка.

6. Как задать циклический список?

7. Приведите пример задания двунаправленного списка.

8. Приведите примеры стека, очереди, дека.

9. Что такое матрица смежности?

10. Что такое матрица инцидентности?

11. Приведите примеры списков смежных вершин, список ребер графа.

12. Какие знаете методы реализации графов?

Тема 6. Сортировка

При изучении данной темы следует обратить внимание на источники: [1], [2], [3].

Контрольные вопросы для самопроверки:

1. Поясните операцию сортировки элементов массива.

2. Какие показатели эффективности алгоритма сортировки можете перечислить?

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

4. Дайте определение логарифмическому алгоритму сортировки.

5. Дайте определение линейному алгоритму сортировки.

6. Поясните сортировку пузырьком и оцените показатели эффективности.

7. Поясните сортировку вставками.

8. Дайте определение сортировки выбором.

9. Приведите примеры сортировки выбором.

Тема 7. Поиск

При изучении данной темы следует обратить внимание на источники: [1], [2], [3].

Контрольные вопросы для самопроверки:

1. Дайте определение задачи поиска в массиве.

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

3. Оцените количество элементарных операций в линейном поиске.

4. Выполните сравнительный анализ эффективности линейного и бинарного алгоритмов поиска.

5. Как реализуется поиск в таблице?

6. В чем состоит хеширование?

7. Как выполняется выбор хеш-функции?

8. Раскройте понятие коллизии.

9. В чем состоит метод открытой адресации?

10. Опишите метод цепочек.

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

При изучении данной темы следует обратить внимание на источники: [1], [2], [3].

Контрольные вопросы для самопроверки:

1. Раскройте понятия объекта и класса.

2. Что понимают под инкапсуляцией?

3. Что такое наследование?

4. В чем состоит полиморфизм поведения класса?

5. Приведите спецификацию видимости атрибутов и методов класса.

6. В чем состоит механизм раннего (позднего) связывания?

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

Тема 9. Событийное программирование

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

При изучении данной темы следует обратить внимание на источники: [1], [2], [3].

Контрольные вопросы для самопроверки:

1. В чем заключается событийно-управляемое программирование?

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

3. Какие методы обработки и распространения событий можете назвать?

4. В чем состоит параллелизм обработки событий?

5. Что называют прикладным программным интерфейсом?

6. Что такое промежуточное программное обеспечение?

Тема 10. Параллельные вычислительные технологии

Контрольные вопросы для самопроверки:

Наши рекомендации

Введение в теорию журналистики

Введение в теорию финансов

Введение в микроэкономическую теорию

Введение в экономическую теорию

I.Введение в экономическую теорию

Введение в экономическую теорию

Введение в макроэкономическую теорию

Введение в экономич. теорию.

Введение в экономическую теорию

ДЕ 7. Введение в экономическую теорию

← Предыдущая страница | Следующая страница →