Вопросы к экзамену по курсу «Информатика» (стр. 3 )

Изучение системы осуществляется с помощью построения ее модели. Модель сложного объекта также будет сложной структурой, это значит, что сама модель может быть системой.

Выделение систем связано с постановкой и решением следующих задач:

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

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

3. Построение новой системы.

4. Использование существующей системы в практических целях.

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

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

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

44. Классификация систем.

Система называется статической если множество компонентов, из которых она состоит, множество их свойств и взаимосвязей, а также множество системных свойств не изменяется с течением времени.

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

Статическую систему можно рассматривать как мгновенное состояние динамической системы.

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

Система считается замкнутой, если ее компоненты не взаимодействуют с внешним миром, с объектами, не принадлежащими системе. Это значит, что отсутствуют потоки вещества, энергии и информации из системы или в систему. В противном случае система считается незамкнутой.

Различают естественные, искусственные и информационные системы. Естественные и искусственные системы материальны, информационные системы нематериальны.

Частным случаем информационных систем являются формальные системы. Точнее, формальная система является разновидностью математической модели. В формальной системе фиксируется исходное множество компонентов и связей (отношений) между ними, а также множество правил порождения новых объектов. Формальные системы служат для создания различных математических дисциплин (математическая логика, теория множеств), а также являются важным инструментом информатики, служащим для создания языков программирования и трансляторов.

45. Различные аспекты понятия алгоритм. Фундаментальный аспект

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

Фундаментальный аспект понятия алгоритм.

Некоторые этапы построения математики:

Дедуктивный (аксиоматический) подход Пифагора (580-500 г. г. до н. э.). Арифметический подход, середина XIX века. Нуль, отрицательные числа и дроби, можно представлять парами натуральных чисел: 0->{1,1}; -5->{1,6}; 2/3->{2,3}, и т. д. Подход теории множеств, конец XIX - начало XX века. Конструктивное направление теории множеств. Следует использовать только такие математические объекты, для которых существует или для которых можно разработать алгоритм их построения.

46. Логические теории алгоритмов. Тезис Черча.

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

Задача о квадратуре круга: требуется найти метод (алгоритм) построения с помощью циркуля и линейки квадрата равновеликого данному кругу.

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

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

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

Любой объект может быть представлен, закодирован цепочкой символов в некотором алфавите. Следовательно, можно считать, что алгоритм - это правило преобразования кодов в некотором алфавите. Любой код в любом алфавите может быть представлен двоичным кодом, который в свою очередь может трактоваться как целое неотрицательное число. Следовательно, любому алгоритму может быть поставлена в соответствие функция, отображающая множество целых неотрицательных чисел в себя.

Тезис Черча

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

Таким образом проблема существования или не существания алгоритма сводится к решению вопроса о существовании или не существовании соответствующей рекурсивной функции.

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

47. Машина Поста.

Машина Поста представляет собой идеальное, воображаемое устройство, состоящее из неограниченной в обе стороны ленты и каретки, способной перемещаться вдоль ленты. Лента разбита на клетки. Любая клетка может быть отмеченной или нет. За один шаг каретка может переместиться на одну клетку вправо или на одну клетку влево. Каретка может определить отмечена текущая клетка или нет, а также поставить в текущую клетку отметку или же стереть её.

Машина Поста задается:

1.начальным распределением отмеченных клеток;

2.начальным положение каретки;

3.программой, определяющей последовательность действий каретки.

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

Структура команды машины Поста:

<порядковый номер команды>. <операция> <номер следующей команды>

Невыполнимые команды:

Ø  стереть отметку, если текущая клетка не отмечена;

Ø  поставить отметку, если текущая клетка уже отмечена.

Выполнение программы может:

Ø  не завершится никогда (безостановочная работа);

Ø  завершится безрезультатно на невыполнимой команде;

Ø  завершится результативно на команде Стоп.

Требование к программе машины Поста

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

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

48. Интуитивное понятие алгоритма. Роль алгоритмов в обществе и в информатике.

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

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

Исполнителем алгоритма называется субъект или объект, осуществляющий исполнение алгоритма.

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

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

Алгоритмы являются:

1. формой изложения научных результатов;

2. руководством к действию при решении ранее изученных проблем;

3. необходимым этапом при автоматизации обработки информации и решения различных задач.

49. Основные свойства алгоритмов.

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

2. Конечность. Подразумеваются три аспекта свойства.

a. Конечность общего количества этапов. Пример: правило вычисления значения 1+1/4+1/9+…? задает бесконечное количество этапов, а правило 1+1/4+1/9+1/16+1/25+1/36+1/49+1/64+1/81+1/100 ? задает конечное количество этапов.

b. Конечность общего количества выполнений этапов.

c. Явное задание всех этапов. Пример неявного задания этапов: 1+1/4+1/9+…+1/100 ? подразумеваются действия по аналогии.

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

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

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

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

50. Основные типы алгоритмов.

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

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

Циклы. Отличительным свойством является наличие этапа или группы этапов алгоритма, которые выполняются неоднократно.

51. Способы задания алгоритмов. Алгоритмические языки.

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

Словесный способ задания алгоритма состоит в его формулировке средствами естественного языка - русского, английского, китайского и т. д. Основное достоинство способа: наиболее приемлемая для человека, естественная форма. Важнейший недостаток - неоднозначность конструкций, предложений, слов естественного языка.

В общем случае алгоритм есть сообщение, заданное в некотором алфавите. Известно, что его можно закодировать в двоичном алфавите. Достоинство - это способ являющийся в конечном счете единственным, который непосредственно воспринимается компьютером. Недостаток - непосредственное восприятие человеком алгоритма, заданного в двоичном алфавите, затруднено.

Блок-схемой называется графическое изображение структуры алгоритма. Блок –схема представляет собой группу геометрических фигур строго определенного начертания, соединенных стрелками. Каждая фигура изображает некоторое действие, а стрелки, соединяющие фигуры, определяют последовательность действий. Основными достоинствами этого способа является его простота, гибкость, высокая степень наглядности. Однако, задание достаточно сложных алгоритмов на этом уровне затруднено из-за существенно возрастающей громоздкости. Кроме того, алгоритмы, заданные в таком виде непосредственно не воспринимаются компьютером.

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

52. Понятие переменной. Имя, тип и значение переменной.

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

Имя (идентификатор) переменной

Переменные принято обозначать именами. Имя представляет собой произвольную последовательность букв или цифр, которое обычно начинается с буквы. Конкретные правила образования имен регламентируются в описании алгоритмического языка и в различных языках различны. Примеры имен: A, I, counter, z56y%.

Тип переменной

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

Наиболее часто используемые типы: целый (integer), вещественный (real), символьный (char), логический (boolean).

Тип integer

Целочисленные точные значения. Примеры: 73, -98, 5, 19674.

Машинное представление: формат с фиксированной точкой. Диапазон значений определяется длиной поля. Операции: +, -, *, div, mod,=, <, и т. д.

Тип real

Нецелые приближенные значения. Примеры: 0.195, -91.84, 5.0

Машинное представление: формат с плавающей точкой. Диапазон и точность значений определяется длиной поля. Операции: +, -, *, /, =, <, и т. д.

Тип char

Одиночные символы текстов. Примеры: ‘a’, ‘!’, ‘5’.

Машинное представление: формат ASCII. Множество значений определяется кодовой таблицей и возможностями клавиатуры. Операции: +, =, <, и т. д.

Тип boolean

Два логических значения false и true. Причем, false<true.

Машинное представление - нулевое и единичное значение бита: false кодируется 0, true - 1. Операции: отрицание, \/,/\, =, < и т. д.

Типы бывают скалярные и структурированные. Значение скалярного типа представлено ровно одним компонентом (время, температура). Значение структурированного типа представлено более чем одним компонентом (вектор).

Типы целый, вещественный, символьный и логический относятся к скалярным.

Структуры аналогичные векторам и матрицам в информатике принято называть массивами, а структуры аналогичные строке таблицы называют записями. Различные структуры отличаются друг от друга количеством компонентов в значении, способом их обозначения и выборки. Для выделения отдельного компонента массива в квадратных скобках справа от названия указывается его индекс (номер) или несколько индексов через запятую: w[5]; w[i+2]; A[1,2].

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

53. Присваивание.

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

<Имя переменной> : = <Правило определения нового значения>

Порядок выполнения присваивания

1. Вычисляется значение выражения в правой части.

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

3. Вычисленное значение закрепляется за переменной или компонентом.

В действии присваивания необходимо различать два состояния:

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

2. после завершения действия переменная имеет новое текущее значение.

Правила задания присваивания

1. Тип переменной в левой части и тип значения в правой должны соответствовать друг другу, например, совпадать. Имеются и другие случаи соответствия, зависящие от используемого языка программирования.

2. Все переменные в правой части должны иметь типы, обеспечивающие возможность вычисления значения выражения.

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

Присваивание это действие, в котором переменная изменяет значение, сравнение это операция, которая не изменяя значений устанавливает факт равенства или не равенства правой и левой частей.

В операции сравнения левая и правая части равноправны, а в действии присваивания - не равноправны. В присваивании выражение слева писать нельзя, а в сравнении - можно.

54. Основные управляющие конструкции. Следование. Задача обмена значениями.

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

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

Переменная N должна получить новое значение, равное старому значению переменной M, в свою очередь переменная M должна получить новое значение, равное старому значению переменной N,

Решение задачи обмена значениями

Чтобы решить задачу старое значение любой из переменных перед первым же присваиванием следует где-то сохранить. Такое сохранение в алгоритме может быть выполнено только с помощью какой-либо переменной.

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

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

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

2. Выяснить что нужно получить, какие величины являются искомым результатом.

3. Определить тип всех используемых величин и закрепить за каждой величиной название.

4. Выбрать или построить метод решения задачи.

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

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

7. Проанализировать полученный алгоритм с точки зрения его правильности, эффективности и т. д. Выполнить тестирование алгоритма.

56. Решение системы двух алгебраических уравнений с двумя неизвестными.

Известно, что решение системы можно получить по правилу Крамера:

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

Для задания действий, связанных с вычислением числителей и знаменателя следует использовать для них какие-либо обозначения. Пусть D - переменная, служащая для обозначения знаменателя, Dx - числителя первой дроби и Dy - числителя второй дроби.

, ,

,

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

Для определения величин, значения которых подлежат вводу можно использовать следующие соображения:

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

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

57. Управляющие конструкции ветвлений. Общий порядок построения ветвлений.

Полное ветвление

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

Сокращенное ветвление

Сокращенное ветвление используется, если в одном из вариантов никаких действий выполнять не нужно

*58. Примеры организации полного и неполного ветвлений.

*59. Организация ветвлений с большим количеством ветвей.

60. Циклы. Общий порядок построения циклов.

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

<тут типа перечисление Положим k=1, тогда, зная a0 можно найти a1 такого вида :)>

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

k:=k+1

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

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

Общие правила организации циклов

1. Выявить группу повторяющихся действий? сформировать тело цикла.

2. Установить условия повторения этих действий.

3. Установить начальные значения величин, участвующих в условии и в теле цикла? выполнить инициализацию цикла.

*61. Пример алгоритма работы с рекуррентными последовательностями.

62. Алгоритмы накопления сумм и произведений.

Исходной величиной задачи является переменная N целого типа - количество слагаемых, величина i - номер текущего слагаемого - является промежуточной также целого типа, а величина S - искомая сумма вещественного типа.

Мы можем рассматривать переменную S как текущее значение накапливаемой суммы, вычислять и по очереди добавлять к ней каждое слагаемое. Тогда после добавления последнего слагаемого значение S будет представлять собой искомый результат

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

Условие, при котором выполняются эти действия - наличие еще не вычисленных и не добавленных слагаемых.

До начала вычислений уже накопленное значение суммы равно нулю, а накапливать сумму можно начать с первого слагаемого.

Суммирование с рекуррентным соотношением между слагаемыми

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

62. Алгоритмы определения экстремального элемента массива.

Пусть задан массив x ={x1,x2,…,xn}. В простейшем случае необходимо найти его наибольший (наименьший) элемент.

Пусть max - переменная, которая играет роль «кандидата на должность» наибольшего элемента, i - номер очередного элемента массива. Если элементы массива, относятся к целому типу, то и max тоже величина целого типа.

Короче сравниваем каждый с max если больше max то присваиваем max значение .

63. Задача поиска. Алгоритмы линейного поиска.

Общая постановка. В заданной совокупности элементов требуется найти элемент, обладающий заданным набором свойств.

Важнейший частный случай. Задан массив x, нужно определить имеет ли в нем элемент, совпадающий с заданным числом a. Если такой элемент обнаружен, то в качестве дополнительной информации следует получить номер совпадающего с заданным элемента массива

a) Классический алгоритм

Предлагается очевидный подход к решению задачи: последовательное сравнение каждого очередного элемента массива с заданным. Такой способ называется линейным поиском.

б) Быстрый алгоритм

Идея быстрого алгоритма состоит в том, что выражения flag и x[i]=a эквивалентны. Следовательно, в условии в заголовке цикла вместо not flag можно использовать x[i]<>a, и отказаться от использования индикатора flag.

в) Алгоритм с барьером

Следующее улучшение состоит в упрощении условия в заголовке цикла. Целевым является условие x[i]<>a, которое убрать или упростить невозможно. Следовательно, можно рассматривать только условие i<=N, обеспечивающие прекращение просмотра после исчерпания всех элементов цикла. Идея состоит в выставлении в конце массива «барьера». Для этого в массив добавляется N+1 элемент, значение которого приравнивается к искомому.

В алгоритмах линейного поиска максимальное количество операций, которое приходится проделать для определения результата поиска пропорционально N.

64. Бинарный поиск.

Если данные упорядочены, то поиск можно сделать значительно более эффективным. Если x[i]<=x[i+1], i=1,2,…,N-1, то массив называется упорядоченным (отсортированным) по возрастанию.

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

Если они совпадают, то задача уже решена. Так как массив упорядочен, то при не совпадении элементов, в дальнейшем поиске можно не рассматривать одну из половин массива.

А именно, если средний элемент массива больше искомого, то все элементы, расположенные правее его, также будут больше искомого и дальнейший поиск следует осуществлять в левой половине массива.

В противном случае, если средний элемент массива меньше искомого, то все элементы, расположенные левее, будут также меньше его и дальнейший поиск следует выполнять в правой половине массива.

Итак, во время поиска приходится повторять следующие действия: 1) выбирать средний элемент массива; 2) сравнивать его с искомым; 3) при необходимости уменьшать рассматриваемую часть массива в два раза выбором его правой или левой половины.

Так как начальный и конечный элементы рассматриваемой части массива при отбрасывании одной из половин массива будут изменяться, то для записи алгоритма следует использовать переменные, имеющие смысл номеров начального (левого) L и конечного (правого) R элементов массива. Поскольку в начале рассматривается весь массив, то L=1, а R=N. Номер среднего элемента M можно найти стандартным способом: M=(R+L) div 2.

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

На первом шаге количество K рассматриваемых элементов массива равно N

После первого шага количество K рассматриваемых элементов массива уменьшается в два раза K=N/2.

После второго шага - в четыре раза

Вообще, после шага с номером m:

В худшем случае процесс поиска закончится после того, как останется один элемент: . Отсюда:

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

66. Построение кратных циклов.

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

67. Задача сортировки. Сортировка прямым выбором.

Сортировкой в информатике называется переупорядочение рассматриваемых объектов по некоторому признаку или системе признаков. Например, упорядочение слов по алфавиту называется лексикографической сортировкой.

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

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

68. Понятие верификации алгоритмов. Инварианты циклов.

Инвариантом цикла называется выражение, значение которого остается постоянным во время всех выполнений тела цикла.

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

Если такой инвариант существует и, кроме того, показано, что цикл выполняется конечное число раз, то можно утверждать, что алгоритм правильный и результаты его выполнения являются верными искомыми результатами. Такие рассуждения называются верификацией алгоритма

В стандартных операторах цикла while B do S требование конечности означает, что после конечного количества проходов по циклу условие B должно стать ложным. Для доказательства оканчиваемости с циклом обычно связывается некоторая ограниченная целочисленная убывающая функции или последовательность, элементы которой зависят от переменных программы, и показывается, 1) что ее начальное значение или начальный элемент положительны и при этом B=true; 2) при каждом выполнении цикла значение функции уменьшается (происходит переход к следующему элементу последовательности); 3) при достижении конечного значения (элемента последовательности) (обычно 0 или -1) условие В=false

69. Сложность алгоритмов. Классы сложности Р и ЕХР.

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

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

Практически важный аспект анализа сложности связан с классификацией алгоритмов по типу зависимости T(V) по скорости ее роста. Существуют алгоритмы, в которых T(V) растет линейно, квадратично, имеет кубическую зависимость и т. д. Такие алгоритмы принято называть полиномиальными или алгоритмами с полиномиальной сложность и говорить, что алгоритм относится к классу сложности P. Существую алгоритмы, временная сложность которых растет быстрее полинома любой степени, как c некоторым основанием a. Такие алгоритмы принято называть алгоритмами с экспоненциальной сложностью и говорить, что алгоритм относится к классу сложности EXP.

В качестве образцов скорости роста можно взять следующий набор функций, следующую шкалу сложности алгоритмов:

*70. Примеры оценки сложности алгоритмов.

71. Понятие подпрограммы.

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

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

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