Оглавление

Предисловие

1.Вводные понятия

1.1.АЛГОРИТМЫ И ФУНКЦИИ

1.1.1.Что такое алгоритм? 1.1.2. Что такое ЭВМ? 1.1.3. Как можно определять функции? 1.1.4. Упражнения.

1.2. КАК МОЖНО ОПРЕДЕЛИТЬ ЯЗЫК ПАСКАЛЬ?

1.2.1. Два примера простых Паскаль-программ; 1.2.2. Синтаксис и семантика языка; 1.2.3. Алфавит и словарь языка Паскаль; 1.2.4. Синтаксические диаграммы; 1.2.5. Упражнения.

1.3. ЗАДАНИЯ

2. Простейшие программы

2.1. СТАНДАРТНЫЕ ТИПЫ ДАННЫХ

2.1.1. Типы данных, переменные и константы; 2.1.2. Операции и стандартные функции; 2.1.3. Логический тип (Boolean); 2.1.4. Тип целый (Integer); 2.1.5. Вещественный тип (Real); 2.1.6. Литерный тип
(Char); 2.1.7. Упражнения.

2.2. ВЫРАЖЕНИЯ, ОПЕРАТОРЫ И ФУНКЦИИ

2.2.1.Выражения; 2.2.2. Операторы; 2.2.3. Оператор присваивания; 2.2.4. Составной оператор; 2.2.5. Операторы ввода-вывода; 2.2.6. Общий вид Паскаль-программ; 2.2.7. Определяемые функции; 2.2.8. Упражнения.

2.3. ДОКАЗАТЕЛЬСТВО СВОЙСТВ ПРОГРАММ

2.3.1. Зачем нужны доказательства правильности? 2.3.2. Внешняя спецификация программы; 2.3.3. Утверждения как множества состояний; 2.3.4. Метод промежуточных утверждений; 2.3.5. Упражнения.

2.4. ПОСТРОЕНИЕ ЛИНЕЙНЫХ ПРОГРАММ

2.4.1. Периметр и площадь прямоугольного треугольника; 2.4.2. Симметричная буква; 2.4.3. Возведение в степень; 2.4.4. Площадь треугольника; 2.4.5. Упражнения.

2.5. ЗАДАНИЯ

3. Простые программы без циклов

3.1. СРЕДСТВА ДЛЯ ОРГАНИЗАЦИИ ВЕТВЛЕНИЙ

3.1.1. Блок-схемы; 3.1.2. Условный оператор; 3.1.3. Оператор выбора; 3.1.4. Доказательство свойств ветвящихся программ; 3.1.5. Упржнения.

3.2. ПОСТРОЕНИЕ ВЕТВЯЩИХСЯ ПРОГРАММ

3.2.1. Точка в треугольнике; 3.2.2. Максимум из трех чисел; 3.2.3. Табличное задание функции; 3.2.4. Анализ квадратного уравнения; 3.2.5. Тип треугольника; 3.2.6. Упражнения.

3.3. ЗАДАНИЯ

4. Итеративные программы

4.1. СРЕДСТВА ДЛЯ ОРГАНИЗАЦИИ ЦИКЛИЧЕСКИХ ВЫЧИСЛЕНИЙ

4.1.1. Оператор цикла с условием на продолжение; 4.1.2. Свойства оператора цикла; 4.1.3. Оператор цикла с условием на окончание; 4.1.4. Операторы цикла с параметрами; 4.1.5. Пошаговая разработка программ; 4.1.6. Упражнения.

4.2. НЕЗАВИСИМАЯ ОБРАБОТКА ЭЛЕМЕНТОВ ПОСЛЕДОВАТЕЛЬНОСТИ

4.2.1. Перекодировщик; 4.2.2. Выборка элементов последовательности; 4.2.3. Упражнения.

4.3. ПРОГРАММЫ ВЫЧИСЛЕНИЯ ЭЛЕМЕНТА ПОСЛЕДОВАТЕЛЬНОСТИ

4.3.1.Вычисление факториала; 4.3.2. Вычисление числа e; 4.3.3. Схема Горнера; 4.3.4. Упржнения.

4.4. ФУНКЦИИ НА ПОСЛЕДОВАТЕЛЬНОСТЯХ

4.4.1. Подсчет вхождений; 4.4.2. Количество максимумов; 4.4.3. Упражнения.

4.5. ОБРАБОТКА ПОСЛЕДОВАТЕЛЬНОСТИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ И ДВОЙНЫЕ ЦИКЛЫ

4.5.1. Обработка слов предложения; 4.5.2. Приближенное вычисление сумм рядов; 4.5.3. Упражнения.

4.6. ЗАДАНИЯ

5. Программы обработки структурированных данных

5.1. ПРОСТЫЕ ТИПЫ ДАННЫХ, ОПРЕДЕЛЯЕМЫЕ ПРОГРАММИСТОМ

5.1.1. Раздел определений типов; 5.1.2. Введение синонимических типов; 5.1.3. Задание отрезков типов; 5.1.4. Типы, заданные перечислением значений; 5.1.5. Упражнения.

5.2. СТРУКТУРИРОВАННЫЕ ТИПЫ ДАННЫХ

5.2.1. Записи; 5.2.2. Массивы; 5.2.3. Матрицы и таблицы; 5.2.4. Доказательство свойств программ со структурированными типами данных; 5.2.5. Упражнения.

5.3. ПРОГРАММЫ ОБРАБОТКИ ЗАПИСЕЙ

5.3.1. Обработка анкет; 5.3.2. Упражнения.

5.4. ПРОГРАММЫ ОБРАБОТКИ ВЕКТОРОВ

5.4.1. Векторная функция; 5.4.2. Поиск в упорядоченном векторе; 5.4.3. Подсчет количеств вхождений букв; 5.4.4. Свертка вектора; 5.4.5. Упражнения.

5.5. ПРОГРАММЫ ОБРАБОТКИ ТАБЛИЦ

5.5.1. Статистика; 5.5.2. Упражнения.

5.6. ПРОГРАММЫ ОБРАБОТКИ МАТРИЦ

5.6.1. Поиск максимума в матрице; 5.6.2. Произведение матриц; 5.6.3. Преобразование матриц; 5.6.4. Поиск номера строки-серии; 5.6.5. Упражнения.

5.7. ЗАДАНИЯ

6. Программы с процедурами и функциями

6.1. ПОДПРОГРАММЫ: ПРОЦЕДУРЫ И ФУНКЦИИ

6.1.1. Описание и вызов процедуры; 6.1.2. Блоки и локализация имен; 6.1.3. Изменение действия — входные параметры; 6.1.4. Получение результатов — выходные параметры; 6.1.5. Вычисление единственного значения — функции; 6.1.6. Использование процедур и функций для пошаговой разработки программ; 6.1.7. Рекурсивные подпрограммы; 6.1.8. Когда и как нужно использовать рекурсию; 6.1.9. Метод структурной индукции; 6.1.10. Упражнения.

6.2. ПОСТРОЕНИЕ ПРОГРАММ С ПРОЦЕДУРАМИ И ФУНКЦИЯМИ

6.2.1. Обработка последовательности векторов; 6.2.2. Ханойские башни; 6.2.3. Кратные суммы; 6.2.4. Быстрая сортировка; 6.2.5. Числа Фибоначчи; 6.2.6. Упражения.

6.3. ЗАДАНИЯ

7. Более сложные программы

7.1. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

7.1.1. Ссылки и динамическая память; 7.1.2. Стеки, очереди и бинарные деревья; 7.1.3. Упражнения.

7.2. АНАЛИЗ СЛОЖНОСТИ АЛГОРИТМА

7.2.1. Временная сложность алгоритма; 7.2.2. Упражнения.

7.3. ЗАДАЧИ ПОВЫШЕННОЙ ТРУДНОСТИ

7.3.1. Удаление вершины из поискового дерева; 7.3.2. Порядок вычисления произведения матриц; 7.3.3. Подсчет мощности одного подмножества чисел; 7.3.4. Упражнения.

7.4. ЗАДАНИЯ

8. Индивидуальные задания

8.1. РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ ЗАДАНИЙ

8.1.1. Требования к выполнению заданий; 8.1.2. Рекомендации преподавателю и студенту; 8.1.3. Дополнительная литература.

8.2. СЛОВАРЬ ПОНЯТИЙ, ИСПОЛЬЗУЕМЫХ В ЗАДАНИЯХ

8.2.1. Графы и системы дорог; 8.2.2. Грамматики, языки и автоматы; 8.2.3. Формулы и программы; 8.2.4. Геометрия; 8.2.5. Игры.

8.3. ОБЩИЕ РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ ЗАДАНИЙ

8.3.1. Анализ задачи; 8.3.2. Выбор представления данных; 8.3.3. Разработка алгоритма; 8.3.4. Обоснование алгоритма; 8.3.5. Анализ алгоритма и его сложности; 8.3.6. Кодирование алгоритма (программирование); 8.3.7. Выбор и обоснование набора текстов; 8.3.8. Отладка.

8.4. РАЗРАБОТКА АЛГОРИТМОВ

8.4.1. Основные типы данных, возникающие при выполнении заданий; 8.4.2. Язык описания алгоритмов; 8.4.3. Поиск с возвращением; 8.4.4. Алгоритм поиска с возвращением; 8.4.5. Обходы ордерева в глубину и в ширину; 8.4.6. Обходы графа в глубину и в ширину; 8.4.7. Усовершенствование поиска с возвращением; 8.4.8. Метод ветвей и границ; 8.4.9. Динамическое программирование; 8.4.10. Методы порождения объектов; 8.4.11. Порождение перестановок; 8.4.12. Порождение подмножеств множества; 8.4.13. Порождение сочетаний.

8.5. ВЫБОР ПРЕДСТАВЛЕНИЯ ДАННЫХ

8.5.1. Вопросы выбора представления данных; 8.5.2. Множество точек на плоскости; 8.5.3. Прямая на плоскости; 8.5.4. Окружность и многоугольник; 8.5.5. Последовательность; 8.5.6. Вектор; 8.5.7. Матрица; 8.5.8. Тексты; 8.5.9. Слова и предложения; 8.5.10. Граф; 8.5.11. Корневое дерево; 8.5.12. Система дорог; 8.5.13. Грамматика; 8.5.14. Автоматная диаграмма; 8.5.15. Логическая формула; 8.5.16. Логический фрагмент; 8.5.17. Простое выражение; 8.5.18. Полином; 8.5.19. Игры.

8.6. ФОРМУЛИРОВКИ ЗАДАНИЙ

8.6.1. Графы и системы дорог; 8.6.2. Грамматики, языки и автоматы; 8.6.3. Формулы и программы; 8.6.4. Геометрия; 8.6.5. Игры.

Библиографический список