Министерство образования Российской Федерации
Московский физико-технический институт
(государственный университет)
УТВЕРЖДАЮ
Проректор по учебной работе
___________
«____» _____________ 2006 г.
по курсу Введение в программирование
по направлению 552800
факультет ФРТК
кафедра Прикладной информатики
курс 1
семестр 1,2
лекции 66 часов
семинарские занятия нет Четыре задания практические занятия 66 часов Экзамен
ВСЕГО ЧАСОВ 132
Программу составили: профессор, д.ф.-м.н. доцент, к.т.н.
Программа обсуждена на заседании кафедры прикладной информатики и кафедры информатики
15 апреля 2006 г.
Заведующий кафедрой В.И. прикладной информатики
Заведующий кафедрой информатики
1. Алгоритмы и решение задач.
1.1. Стратегии решения задач.
1.2. Понятие алгоритма.
1.3. Роль алгоритмов в процессе решения задач.
1.4. Блок-схемы алгоритмов. Редактор блок-схем «Дракон».
1.5. Стратегии реализации алгоритмов.
1.6. Стратегии отладки.
1.7. Концепции и свойства алгоритмов.
1.8. Оценки быстродействия алгоритмов.
2. Алгоритмические стратегии.
2.1. Стратегия «полного перебора» (метод грубой силы).
2.2. Стратегия «жадности».
2.3. Стратегия «разделяй и властвуй».
2.4. Стратегия «поиска с возвратом».
2.5. Стратегия «метода ветвей и границ».
2.6. Стратегия «динамического программирования».
2.7. Эвристики.
2.8. Сопоставление с образцом и алгоритмы обработки текста.
2.9. Алгоритмы численной аппроксимации.
3. Основные конструкции программирования (на примере языка программирования С).
(Примечание: поскольку некоторые конструкции языка могут иметь отличающиеся варианты в зависимости от версии и производителя компилятора, был выбран стандарт ISOC99).
3.1. Основы синтаксиса и семантики языков высокого уровня.
3.2. Типы, переменные, операции, выражения.
3.3. Основы ввода/вывода на консоль.
3.4. Конструкции проверки условия и цикла.
3.5. Массивы и строки.
3.6. Указатели. Динамическое выделение памяти.
3.7. Функции и передача параметров. Рекурсия.
3.8. Структуры, объединения, перечисления.
3.9. Файловый ввод-вывод.
3.10. Препроцессор.
3.11. Структурная декомпозиция.
4. Фундаментальные структуры данных.
4.1. Базовые типы данных.
4.2. Массивы и строки. Операции со строками.
4.3. Записи (структуры).
4.4. Представление данных в памяти.
4.5. Статическое, автоматическое и динамическое выделение памяти.
4.6. Управление памятью во время исполнения программы.
4.7. Указатели и ссылки.
4.8. Связанные структуры.
4.9. Методы реализации стеков, очередей и хэш-таблиц.
4.10. Методы реализации графов и деревьев.
4.11. Стратегии выбора подходящей структуры данных.
5. Фундаментальные вычислительные алгоритмы.
5.1. Простые численные алгоритмы.
5.2. Алгоритмы последовательного и бинарного поиска.
5.3. Квадратичные методы сортировки (сортировка методом выбора, сортировка вставками).
5.4. Алгоритмы сортировки за время О(N*logN) (быстрая сортировка, пирамидальная сортировка, сортировка слиянием).
5.5. Хэш-таблицы, включая методы уменьшения коллизий.
5.6. Бинарные деревья поиска.
5.7. Представление графов (матрица смежности, списки смежности).
5.8. Обходы в глубину и в ширину.
5.9. Алгоритмы поиска кратчайшего пути (алгоритмы Дейкстры и Флойда).
5.10. Транзитивное замыкание (алгоритм Уоршалла).
5.11. Минимальное остовное дерево (алгоритмы Прима и Крускала).
5.12. Топологическая сортировка.
Список литературы
Основная литература по алгоритмам
1. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Изд. дом "Вильямс", 2000.
Основная литература по языку С
1. Керниган Б., Ритчи Д. Язык программирования С. – СПб.: Невский диалект, 2000.
Дополнительная литература по языку С
1. Харбисон С.П., Стил Г.Л. Язык программирования С. Пер. с англ. М.: ООО «Бином-Пресс», 2004.
2. Шилдт Г. Полный справочник по С, 4-е издание.: Пер. с англ. – М.: Издательский дом «Вильямс», 2004.
Дополнительная литература по алгоритмам
1. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ, 2-е издание.: Пер. с англ. – М.: Издательский дом «Вильямс», 2005.
2. Кнут Д. Искусство программирования. Том 1. Основные алгоритмы. – М.: Изд. дом "Вильямс", 2002.
3. Левитин А.В. Алгоритмы: введение в разработку и анализ.: Пер. с англ. – М.: Издательский дом «Вильямс», 2006.
4. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си (+CD): Учебное пособие. – М.: Финансы и статистика, 2004.
5. Хэзфилд Р., Кирби Л. Искусство программирования на С: фундаментальные алгоритмы, структуры данных и примеры приложений. – СПб.: DiaSoft, 2001.
Задания
Задание 1
(срок сдачи 03 ноября 2006 г.)
В редакторе «Дракон» составить блок-схемы алгоритмов решения следующих задач:
1. Линейный поиск информации в массиве (перебор).
2. Бинарный поиск информации в массиве.
3. О выборе заявок (жадный алгоритм).
4. О маршруте шахматного коня (перебор с возвратом).
5. О восьми ферзях (метод проб и ошибок).
Задание 2
(срок сдачи 07 декабря 2006 г.)
Написать и отладить на языке программирования С следующие программы:
1. Уточнение корней уравнения методом касательных (или Ньютона).
2. Линейный поиск в массиве
3. Бинарный поиск в массиве.
4. Сортировки массивов выбором, вставками, обменом (квадратичные методы).
5. Сортировки массивов за время О(N*logN) (быстрая сортировка, пирамидальная сортировка, сортировка слиянием).
6. Стековый "Калькулятор".
7. Построения циклической очереди.
8. Построения кольцевого списка (задача Иосифа).
9. Построения хэш-таблицы, включая методы уменьшения коллизий (методом цепочек, методом открытой адресации), и поиска в хэш-таблице.
10. Построения бинарного дерева поиска и поиска в нем.
11. Построения АВЛ-дерева и поиска в нем.
Задание 3
(срок сдачи 29 марта 2007 г.)
Написать и отладить на языке программирования С следующие программы:
1. О выборе заявок (жадный алгоритм).
2. О маршруте шахматного коня (поиск с возвратом).
3. О восьми ферзях (метод проб и ошибок).
Задание 4
(срок сдачи 10 мая 2007 г.)
Написать и отладить на языке программирования С следующие программы:
1. Поиска кратчайшего пути в графе (алгоритмы Дейкстры и Флойда
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.