Введение Основные понятия и концепции

Для чего полезно знать программирование? 1. Развитие алгоритмического мышления: чтение и исполнение алгоритмов; составление алгоритмов и документации; восстановление алгоритмов и документации; 4. Понимание моделей искусственного интеллекта. 3. Понимание моделей естественных языков. 2. Расширение функционала имеющихся программ.

Задачи, моделируемые методами искусственного интеллекта: распознавание образов (графической, графической текстовой, звуковой и т. п. информации); полуавтоматический перевод текста, написанного на естественных языках; определение местонахождения, идентификации, навигации и поиска; и т. д. и т. п.

Основные понятия Что такое программирование? Программирование решение задач при помощи ЭВМ.

Области применения программирования: решение математических задач; системное программирование; сетевое программирование; прикладное программирование; скриптовое программирование; программирование под Web.

Этапы разработки программ 1. Постановка задачи определение требований к программному продукту. 2. Анализ формализация постановки задачи и определение методов ее решения. 3. Проектирование выбор структуры программного продукта, структуры данных, построение и оценка алгоритмов подпрограмм и определение особенностей взаимодействия программы с внешней средой (другими программами, ОС и техническими средствами). 4. Реализация составление программы на выбранном языке программирования, ее тестирование и отладка. 5. Модификация выпуск новых версий программного продукта.

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

Блок-схемы

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

Программа и ее составляющие Программа решение поставленной задачи. 1. Функциональная составляющая. Составляющие: 2.Интерфейс. 3.Архитектура.

Этапы создания программы Исходный код (текст) программы Машинный код Компилирование Объектный код

Среда программирования Текстовый редактор Компилятор Система отладки и поиска ошибок Справочная система

Основные понятия Логическое выражение конструкция языка программирования, результатом вычисления которой может быть только два значения «истина» (true) или «ложь» (false). Операнд объект, над которым производится операция. (Встроенные) операции сравнения, арифметические, логические, побитовые и т. д. Идентификатор (имя) последовательность букв, цифр и специальных символов, начинающаяся с буквы или специального символа. Переменная специальный объект, в котором хранятся данные. По сути это именованное место памяти. Константа переменная, изменять значение которой в программе запрещено.

Принципы фон Неймана 1. Информация кодируется в двоичной форме и разделяется на единицы (элементы) информации слова. 2. Разнотипные слова различаются по способу использования, но не по способу кодирования. 3. Слова размещаются в ячейках памяти и идентифицируются номерами ячеек (адресами). 4. Алгоритм представляется в виде последовательности управляющих слов команд. Алгоритм в терминах машинных команд называется программой. 5. Выполнение вычислений сводится к последовательному выполнению команд в порядке, однозначно определяемом программой. Первой выполняется команда, задаваемая пусковым адресом программы (точка входа). Далее выполняется следующая команда или другая, если ей передается управление. Процесс вычислений выполняется до тех пор, пока не будет выполнена команда прекращения вычислений (точка выхода).

Основные типы данных 1. Числовые типы 2. Логический 3. Символьный 4. Строковый 6. Массив 7. Структура 5.Дата-время 8.Класс

Методология программирования Методология программирования это совокупность идей, понятий, принципов, способов и средств, определяющих стиль написания, отладки и сопровождения программ.

Императивное программирование 3. Структурное программирование методология разработки ПО, в основе которой лежит представление программы в виде иерархической структуры блоков. 4.Объектно-ориентированное программирование (ООП) методология, основой которой являются классы и объекты. 1. Иногда называется процедурным программированием. Это методология разработки ПО, в основе которой лежит процесс вычисления, описанный в виде инструкций. 2. Модульное программирование методология программирования, при которой вся программа разбивается на группу компонентов, называемых модулями, причем каждый из них имеет свой контролируемый размер, четкое назначение и детально проработанный интерфейс с внешней средой.

Концепции модульного программирования 1. Принцип утаивания информации. Всякий компонент утаивает единственное проектное решение. 2. Аксиома модульности. Модуль независимая программная единица, служащая для выполнения некоторой определенной функции программы и для связи с остальной частью программы. 3. Сборочное программирование. Модули это программные кирпичи, из которых строится программа.

Структурное программирование Методология структурного императивного программирования подход, заключающийся в задании хорошей топологии императивных программ, в том числе отказе от использования глобальных данных и оператора безусловного перехода, разработке модулей с сильной связностью и обеспечении их независимости от других модулей. Три основных метода, лежащих в основе структурного программирования: 1. Метод модульной организации частей программы заключается в разбиении программы на специальные компоненты, называемые модулями. 2. Метод структурного кодирования заключается в использовании при кодировании трех основных управляющих конструкций: последовательного исполнения, ветвления и цикла. 3. Метод алгоритмической декомпозиции сверху вниз заключается в пошаговой детализации алгоритма решения задачи от главной программы к подпрограммам самого нижнего уровня.

Примеры программ на BASIC Печать чисел от 1 до 10 и их квадратов. Неструктурированный код 10i = 0 20i = i IF i 10 THEN GOTO 50 50PRINT "Программа завершена." 60END 70PRINT i; " квадрат = "; i * i 80GOTO 20 Структурированный код FOR i = 1 TO 10 PRINT i; " квадрат = "; i * i NEXT i PRINT "Программа завершена."

Объектно-ориентированное программирование В объектно-ориентированном программировании базовыми единицами программ и данных являются объекты. Объект это осязаемая сущность, которая четко проявляет свое поведение. Объект состоит из следующих трех частей: 1. имя объекта; 2. состояние (переменные состояния или поля объекта); 3. методы (операции). Интерфейс объекта с его окружением полностью определяется его методами. К его состоянию нет другого доступа извне, кроме как через методы. Объект может посылать сообщения другим объектам и принимать сообщения от них.

Объекты и классы Структура системы (статическая составляющая) описывается в терминах объектов и связей между ними. Поведение системы (динамическая составляющая) в терминах обмена сообщениями между объектами. Сообщения могут быть как реакцией на события, вызываемые как внешними факторами, так и порождаемые самими объектами. Абстракция объектов с одинаковыми характеристиками, то есть с одинаковыми наборами переменных состояния и методов, образуют класс. Каждый класс в ООП задается своим описанием, которое включает информацию, необходимую для создания объектов данного класса и для их существования. (Это информация о его членах: полях и методах объекта). Класс это «чертеж» объекта. Объект экземпляр класса.

Основные концепции ООП 1. Инкапсуляция возможность объединить данные и методы, работающие с ними в классе, и скрыть детали реализации от пользователя. Инкапсуляция подразумевает наличие границы между внешним интерфейсом класса (открытыми членами, видимыми пользователям класса) и деталями его внутренней реализации. 2. Наследование возможность описать новый класс на основе уже существующего с частично или полностью заимствующейся функциональностью. Класс, от которого производится наследование, называется базовым, родительским или суперклассом. Новый класс потомком, наследником или производным классом. 3. Полиморфизм возможность использовать объекты с одинаковым интерфейсом без информации о типе и внутренней структуре объекта. Иначе это функциональная возможность, позволяющая старому коду вызвать новый.

Декларативное программирование Этот термин употребляется в двух смыслах. Первый декларативная программа описывает каково нечто, а не как его создать. Второй программа написана в соответствии с одной из трех следующих методологий: 1. Логическое программирование основано на автоматическом доказательстве теорем и принципах логического вывода информации на основе заданных фактов и правил вывода. 2. Функциональное программирование методология, трактующая процесс вычислений как вычисление значений функций, понимаемых в математическом смысле, а не в смысле процедурного программирования (как подпрограмм) 3. Программирование в ограничениях методология, в которой отношения между переменными указываются в форме ограничений.

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

Алгоритм быстрой сортировки 1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом. 2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный справа от него. Обычный алгоритм операции: Два индекса l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно. Вычисляется индекс опорного элемента m. Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному. Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному. Если r = l найдена середина массива операция разделения закончена, оба индекса указывают на опорный элемент. Если l < r найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает свое выполнение. 3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента. 4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения. Поскольку в каждой итерации длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута обязательно, и обработка гарантированно завершится.

Быстрая сортировка (Pascal) procedure qSort(var ar: array of real); // Вложенная функция сортировки для рекурсивного вызова // Нужна, чтобы не передавать в вызов основной функции границы массива procedure sort(var ar: array of real; low, high: integer); var i, j: integer; m, wsp: real; begin i:=low; j:=high; m:=ar[(i+j) div 2]; // Взятие среднего опорного элемента repeat while ar[i] m do Dec(j); // поменяв > j; if low<j then sort(ar, low, j-1); if i<high then sort(ar, i+1, high); end; begin sort(ar, 0, High(ar)); end;

Быстрая сортировка (Haskell) % алгоритм на функциональном языке Haskell qsort([]) -> []; qsort([Pivot|Rest]) -> qsort([ X || X = Pivot]). 1. Если список пуст, то результатом также будет пустой список. 2. Иначе выделяется «голова» (первый элемент Pivot) и «хвост» (список из оставшихся элементов, который может быть пустым Rest). В этом случае результатом будет конкатенация (сращивание) отсортированного списка из всех элементов «хвоста» меньших «головы», списка из самой «головы» и списка из всех элементов «хвоста» больших либо равных «голове».

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

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

Области применения языков программирования Решение математических задач: C++, Assembler, редко Pascal. Системное программирование: C++, Assembler. Сетевое и интернет-программирование: JavaScript, PHP, ASP.Net, C#, Flash и т. п. Скриптовое программирование: VBA, JavaScript, Apple Script, 1C, Oracle и т. п.