Информатика и программирование

1. Алгоритмы, их типы и свойства. Формы записи алгоритмов.

2. Визуальное объектно-ориентированное программирование. Инкапсуляция, наследование, полиморфизм. Основные объекты и их свойства, методы и события.

3. Информация: определение, свойства и количественные оценки объемов информации. Типы данных и их сравнительный анализ.

4. Классификация языков программирования и их сравнительный анализ. Этапы проектирования программной системы.

5. Общий порядок подготовки программ к выполнению.

6. Определение и типы данных: элементарное данное, массив, запись, очередь, стек, список, таблицы, строки.

7. Определение, назначение, функции объектов, наборов объектов, двумерных файлов, отношений (таблиц), строк (кортежей), идентификаторов, первичных и вторичных ключей, инвертированных списков, элементарных данных, схем, подсхем, экземпляра схемы.

8. Языки программирования. Классификация языков по уровню ав­то­­матизации программирования. Основные термины языка программирования.

Билет 1

Алгоритмы, их типы и свойства. Формы записи алгоритмов.

1.1. Алгоритмы

Алгоритм ‑ это понятное и точное предписание исполнителю со­вер­шения определенных последовательных действий для достижения ука­занной цели.

Свойства алгоритма

Дискретность ‑ последовательность выполнения одного за другим отдельных законченных шагов.

Массовость ‑ применимость к целому классу задач.

Определенность ‑ однозначное толкование каждого шага.

Результативность ‑ получение результата через конечное число шагов.

Формальность ‑ способность любого исполнителя выполнить все шаги алгоритма, не понимая их смысла.

Например, инструкция по использованию утюга является алго­рит­мом, а инструкция как встретить и устроить в гостинице гостя фирмы не является алгоритмом (нет свойства массовости).

Существует теорема, доказывающая, что любой алгоритм есть ком­би­нация трех базовых команд: следование, развилка (“если”), цикл. Команда безусловного перехода (Gоto) не является базовой, и ее можно исключить из языков программирования (FoxPro).

Алгоритмы бывают сходящимися и расходящимися.

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

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

Пример. Задача определения эквивалентности двух программ (две различные программы вычисляют одну функцию) является алгоритмичес­ки неразрешимой.

Алгоритмический язык ‑ это язык формализованной записи алгоритма.

Формы записи алгоритма

1. Словесная форма

Пример описания алгоритма Евклида ‑ нахождения наибольшего общего делителя двух чисел (НОД).

Шаг 1-й. Ввести два числа.

Шаг 2-й. Если числа равны, то взять первое и закончить выполнение алго­ритма, иначе ‑ перейти на следующий шаг.

Шаг 3-й. Определить большее число. Заменить большее число на разность большего и меньшего и перейти на шаг 2-й.

Достоинство ‑ универсальность, недостаток ‑ неформальность.