Последовательный и бинарный поиск, поиск в двоичном дереве; оценки сложности, лучшие и худшие случаи; хеширование, устранение коллизий.
3.2.2. Рекурсивные алгоритмы. Понятие и применение рекурсивных алгоритмов при решении задач. Связь с математической индукцией; сравнение рекурсивных и итеративных алгоритмов. Анализ сложности алгоритмов. Понятие вычислительной сложности (по времени и памяти) и его применение для анализа алгоритмов. Классы сложности. Обзор классов сложности (P и NP), верхние, средние и нижние оценки. Разрешимые и неразрешимые задачи. NP-полнота.
3.2.3. Технология программирования. Основные конструкции языков программирования и их реализации. Методы разработки алгоритмов и программ.
3.2.4. Данные и типы. Классификация данных. Атрибуты данных и средства их описания. Характеристики, связанные с типом (класс значений, множество операций). Базисные типы данных.
3.2.5. Операторный базис традиционных языков программирования. Средства определения подпрограмм. Правила передачи параметров. Процедурные абстракции. Понятие модуля. Инкапсуляция. Абстрактные типы данных. Имя в языках программирования. Описания и области действия. Правила видимости. Параметризация типов.
3.2.6. Ввод - вывод.
3.2.7. Отладка сложных программных комплексов. Понятие правильности и надежности программного комплекса. Тестирование и испытание программных продуктов. Методика поиска ошибок.
Преимущество вычислительных машин - но в то же время и трудность их использования – состоит в том, что они без труда выполняют операции, которые весьма трудоемки или даже практически невыполнимы людьми. И наоборот, действия, которые нам кажутся столь очевидными, что мы не пытаемся их анализировать, зачастую становятся проблемой, когда предпринимается попытка из запрограммировать.
Естественноестремление разработчиков программ – сократить время разработки, облегчить повторное использование отлаженных модулей и снизить издержки на сопровождение и модификацию программ.
Для достижения этих целей в отрасли создания программных комплексов используют методы и подходы управления процессом разработки. На разных этапах развития программной инженерии использовались различные технологии программирования – императивное программирование; модульное программирование; структурное программирование; программирование, управляемое данными; программирование, управляемое событиями; функциональное программирование; логическое программирование и т.п. Теперь невозможно принять участие в дискуссии, посвященной программированию, если не использовать термин «объектно – ориентированное программирование».
Что нового оно привнесло в методы разработки программ? На чем базируется? В каком направлении развивается? Вот вопросы, на которые мы попытаемся ответить (или, по крайней мере, выразим свое мнение на это счет).
Начнем с истории.
Императивное программирование с ростом сложности программ переросло в модульное, которое достигло своего расцвета в структурном. Структурное программирование сформировалось на основе теоретических выкладок при непосредственном участии крупного теоретика информатики Э.Дейкстры.
Бём и Якопини доказали в 1966г. следующий результат:
Для всякой программы, выраженной произвольной блок-схемой, существует эквивалентная ей программа (то есть выполняющая те же преобразования данные à результаты с помощью тех же вычислений), так что:
- операции над переменными те же, что и в исходной программе;
- сохраняются все переменные исходной программы. Возможно добавление некоторого числа логических переменных (имеющих два возможных значения – ИСТИНА и ЛОЖЬ);
- единственными используемыми управляющими структурами являются цепочка и цикл ПОКА.
Объектно – ориентированное программирование стало закономерным результатом развития и обобщения теории абстрактных типов данных.
Базовая парадигма в подходе к решению любой задачи ясна: «разделяй и властвуй». К сожалению, буквальное следование этому макиавеллевскому принципу по-прежнему предполагает долгий путь к решению задачи. Самым важным является то, каким образом мы осуществим это разделение.
Макиавелли Никколо ди Бернардо 1469-1527. В основе развития общества лежит материальный интерес и сила. Выступал за создание сильного национального государства, свободного от национальных междоусобиц. В политической борьбе считал допустимым во имя великих целей пренебрегать законами морали и применять любые средства.
Нашей целью при разделении программы является создание модулей
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
