Вучебниках информатики в общем виде информацион­ный процесс

Вид материала

Учебник

Содержание Язык программирования. Типы данных. Реализация основных алгоритмических структур на языке програм­мирования. Основные этапы разр Типы данных Реализация основных алгоритмических структур на языке программирования Основные этапы разработки программ Постановка и анализ задачи. Тестирование и отладка программы. Составление документации. Технологии программирования Этапы решения сложной задачи X Пример декомпозиции задачи (разбиения задачи на подзадачи). Процедуры и функции Основные понятия и операции алгебры логики Алгебра высказываний (алгебра логики)

Подобный материал:

• 3. Процесс восприятия и управление впечатлением, 191.28kb.
• Понятие о программах и программировании, 592.28kb.
• Поволжская Государственная Академия Телекоммуникаций и Информатики задания и методические, 262.31kb.
• Общеобразовательный стандарт по информатике является нормативным документом, определяющим, 237.91kb.
• Финансы предприятий, 2102.05kb.
• Исходные технические данные, 34.3kb.
• Тема: Личность в системе современного, 42.1kb.
•     После то­го как я на­пи­сал «Счас­т­лив по соб­с­т­вен­но­му же­ла­нию», как-то, 1995.16kb.
• Компьютерная технология обучения и опережающая подготовка преподавателей, 49.99kb.
• Активизация познавательной деятельности школьников на уроках информатики, 32.08kb.

Билет № 5

Язык программирования. Типы данных. Реализация основных алгоритмических структур на языке програм­мирования. Основные этапы разработки программ.

Языки программирования

Первые компьютеры (ЭВМ) разрабатывались прежде все­го как вычислительные машины, т. е. устройства, выполня ющие операции над числами. Сегодня компьютеры позволя­ют обрабатывать информацию всех видов — текстовую, гра­фическую, числовую, мультимедийную. Для решения задачи на компьютере необходимо создать программу, т. е. последовательность команд, входящих в систему команд компьютера.

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

Важным этапом в развитии программирования явилась разработка языков программирования высокого уровня (ЯПВУ) — специальных искусственных языков, прибли­женных к обычному разговорному языку (английскому). Примеры таких языков: FORTRAN, Basic, Pascal, С. Боль­шинство языков высокого уровня универсальны, т. е. пред­назначены для решения широкого круга задач.

Первая цель создания ЯПВУ — облегчить создание про­грамм. Вторая цель — сделать программы переносимыми, т. е. уменьшить количество труда по адаптации программ для новых типов компьютеров.

Поскольку компьютер (а точнее, его процессор) оперирует не конструкциями ЯПВУ, а двоичными командами, то пе­ред выполнением программа должна быть превращена в ма­шинный код. Выполняют эту операцию программы-трансля­торы. В зависимости от порядка подготовки программы на языке высокого уровня к исполнению, трансляторы делятся на компиляторы и интерпретаторы.

Компилятор — это программа, автоматически преобразу­ющая (компилирующая) исходный код ЯПВУ в машинный код и создающая таким образом исполняемый файл. Он мо­жет быть запущен на исполнение операционной системой. В ОС Microsoft такие файлы могут иметь расширения ехе, com, dll.

Интерпретатор — это программа, преобразующая код ЯПВУ в машинный код шаг за шагом, т. е. каждая коман­да преобразуется интерпретатором и сразу выполняется компьютером, затем интерпретатор преобразует следую­щую команду, компьютер ее выполняет и т. д. (интерпрета-

тор — «синхронный переводчик»). Недостаток интерпрета­торов — низкая скорость выполнения программ. Примеры: интерпретаторы языков Basic и Java Script. Для языка Basic в настоящее время существуют как интерпретаторы, так и компиляторы.

Типы данных

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

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

Константа — это именованное значение, которое остает­ся неизменным на протяжении всего времени выполнения программы. Числовая константа представляет собой ка­кое-либо число (7; 3.14), а строковая константа — произ­вольную строку ("количество учеников в классе").

В любом ЯПВУ переменные и константы характеризуют­ся своими типами. Тип данных — это правила хранения и формат данных. Во время работы программы тип данных будет определять, каким образом данные будут извлекаться из оперативной памяти (ОП), интерпретироваться и сохра­няться в ОП. Например, величины 2 05 и -45 относятся к целочисленному типу и их можно складывать, вычитать, перемножать и делить. Величины "цвет" и "ок" относятся к строковому типу, их можно сцеплять, но над ними нельзя выполнять арифметические операции.

В языкe Basic существуют следующие типы данных.



Примечание. Массив — индексированный набор элементов одного типа¹; string (англ.) — ряд, последовательность, це­почка; строка — последовательность символов.


Реализация основных алгоритмических структур на языке программирования












Основные этапы разработки программ

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

1. Постановка и анализ задачи. Четкое определение за­дачи и наборов входных и выходных данных.
   
2. Разработка алгоритма. Определение зависимости между входными и выходными данными, создание процедуры их преобразования.
   
3. Разработка пользовательского интерфейса. Опреде­ление того, что пользователь должен видеть на экране, как будут вводиться данные, где и в каком формате бу­дут представлены выходные данные.
   
4. Написание программного кода. Преобразование алго­ритма в компьютерную программу на языке высокого уровня.
   
5. Тестирование и отладка программы. Тестирование -— прогон программы на наборе тестов, для которых изве­стен результат, с целью проверки правильности ее ра­боты. Отладка (debug) — процесс выявления и устра­нения ошибок в программе.
   
6. Составление документации. Подготовка документов, содержащих описание программы, включая техниче­ское задание, блок-схемы, предположения, список входных и выходных переменных (часто совмещается с программным кодом), руководства пользователя.
   

Билет № 6

Технология нисходящего программирования. Разбиение задачи на подзадачи. Процедуры и функции.

Технологии программирования

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

Существуют разные типы языков программирования. Одни из них — структурные языки, особенностью которых является, во-первых, организация программы в виде команд­ных структур, а, во-вторых, обособление кода и данных.

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

Структурные языки: Pascal, Ada, Java, C#, C++, С, Modula-2.

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

Декларативные языки: Prolog, Lisp, XSL.

К неструктурным языкам программирования относится также ассемблер.

Существуют различные технологии программирования. Технология восходящего программирования («снизу вверх») реализуется так:

1. Вначале создаются и отлаживаются самые элементар­ные подпрограммы (скорее всего используя созданные ранее, хранимые в модулях-библиотеках).
   
2. Реализуется более крупный блок задачи путем вызова та­ких подпрограмм.
   
3. Повторяется пункт 2 до тех пор, пока не реализуется вся задача.
   

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

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

Технология нисходящего программирования — это со­здание программы «сверху вниз». Сначала разрабатывается основная программа (точнее, ее общая структура) и в ней за­писываются обращения к пока еще не написанным вспомо­гательным подпрограммам; и так далее — до самых простых «неделимых» подпрограмм.

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

При этом для ускорения процесса работы над задачей ру­ководитель может разрабатывать основную программу, а другие сотрудники — подпрограммы. Если какая-то под­программа не готова, ее заменяют подпрограммой-«заглуш­кой», которая при заданных входных данных дает разум­ный результат (хотя фактически подпрограмма не работает). Технология нисходящего программирования (метод после­довательной детализации) лежит в основе технологии структурного программирования и широко применяется при использовании структурных языков программирова­ния, таких как Pascal или C++.

Алгоритм решения основной задачи называется основным алгоритмом. Алгоритм решения некоторой подзадачи по отно­шению к исходной (основной) задаче называется вспомогатель­ным алгоритмом.

Таким образом, структурное программирование естест­венно возникает во многих классах задач, прежде всего в та­ких, где задача естественно расщепляется на подзадачи, а информация — на достаточно независимые структуры дан­ных.

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

Итак, особенности структурного программирования:

• модульность — создание программы из более мелких составляющих — модулей, блоков, подпрограмм. Один из этих модулей является в проекте главным и содер­жит нечто вроде конспекта всей программы. Обычно этот модуль содержит только вызовы подчиненных мо­дулей или блоков;
  
• структурность — составление программ как комбина­ции базовых структур трех типов: следования, ветвле­ния, цикла.
  

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

Этапы решения сложной задачи X сверху вниз:

1. Разбиваем задачу X на несколько функциональных подзадач XI, Х2, ХЗ и т. д., т. е. выполняем ее деком­позицию.
   
2. Предполагаем, что впоследствии эти части будут разра­ботаны, создаем их спецификации:
   

• вид подпрограммы (процедура или функция);
  
• ее имя;
  
• имена и типы формальных параметров, их порядок;
  
• для функции — тип возвращаемого значения;
  
• комментарии, описывающие назначение подпрог­раммы.
  

3. Пишем программу решения задачи X, заменив каж­
дую из подпрограмм XI, Х2, ХЗ «заглушками», и от­
лаживаем ее в таком виде.

4. Параллельно работаем с каждой из подпрограмм XI, Х2, ХЗ, при необходимости так же разбивая каждую из них на подзадачи еще более низкого уровня, т. е. используя методику, начиная с п. 1. Каждую подзада­чу можно решать независимо от других.
   
5. Проводим комплексную отладку постепенно, по одной заменяя заглушки на автономно отлаженные подпрог­раммы.
   

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



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

Достоинства метода программирования «сверху вниз» — серьезные ошибки с большой вероятностью отыскиваются уже на ранних стадиях проекта; тестирование систематично.

Недостаток — при отладке поглощается больше машин­ных ресурсов. Необходимо снижать трудоемкость тестирова­ния и отладки программы.

Процедуры и функции

Подпрограмма (subroutine) — именованная последовате­льность операторов языка, предназначенная для решения некоторой подзадачи. Часто подпрограмма имеет свои пере­менные, не пересекающиеся с переменными других под­программ или самой программы (если только переменные не были объявлены специальным образом или переданы под­программе). Каждая подпрограмма имеет имя, по которому к ней можно обратиться. В языках Turbo Pascal и QBasic ме­ханизм подпрограмм реализуется в виде процедур (procedu­re) и функций (function) с такой же структурой, как и основная программа. Они различаются назначением и спосо­бом использования.

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

Подпрограммы вводятся в основную программу с помо­щью соответствующего описания, затем к ним можно вы­полнять обращение. Создание подпрограмм облегчает про­граммирование, так как: 1) не требует многократно повто­рять в тексте программы аналогичные фрагменты; 2) улучшает структуру, облегчая ее понимание; 3) уменьша­ет вероятность появления ошибок (отлаживается отдельно);

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

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

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

Функция предназначена для того, чтобы возвращать одно значение, оно и является ее результатом. Описание функции начинается с заголовка, за ним следует имя, а в круглых скобках — список формальных параметров:

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


Билет № 7

Структуры данных. Обработка массивов. Поиск в масси­ве. Основные алгоритмы сортировки массивов.

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

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

Самый простой случай такой структуры данных — мас­сив. В компилируемых языках высокого уровня массив определяют как упорядоченный набор однотипных пере­менных. Такой набор переменных объявляется заранее, с указанием типа переменных и их количества — для отведе­ния нужного объема памяти. Переменные в массиве назы­ваются его элементами. Каждый элемент массива имеет индекс — целое число, задающее его положение по поряд­ку в массиве.

Основная операция с массивом — обращение к его эле­ментам. Элементы массива используются и изменяются как обычные переменные.

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

Часто возникает задача поиска (определения индекса) элемента в массиве по заданному критерию. Простейший способ такого поиска: перебор всех элементов до нахожде­ния нужного. В качестве ответа можно хранить значение, а можно — индекс найденного элемента.



Если в массиве выдержан какой-то принцип расположе­ния элементов (упорядочение), то все операции поиска мож­но ускорить. Упорядоченным по неубыванию считается мас­сив, в котором каждый следующий элемент не меньше пре­дыдущего, упорядоченным по невозрастанию — тот, где каждый следующий элемент не больше предыдущего.

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

Алгоритмов сортировки массивов достаточно много, наи­более простой в реализации — метод пузырька. Этот алго­ритм предполагает многократный проход по массиву; на каждом проходе (итерации цикла) циклически обменива­ются местами попарно элементы, стоящие в неправильной последовательности. В результате самый «легкий» элемент (минимальный или максимальный) «всплывает» и занима­ет свое место. На каждой итерации количество обрабатыва­емых элементов уменьшается на единицу. Итерации повто­ряются, пока требуется выполнить хотя бы одну переста­новку:

Другой пример — сортировка вставками. На i-й итера­ции считается, что часть масива с 1-го по (i - 1)-й элемент уже упорядочена. Далее i-й элемент вставляется в отсорти­рованную часть массива без нарушения упорядоченности. И так далее.


Билет № 8

Основные понятия и операции формальной логики. Зако­ны логики. Логические переменные. Логические выраже­ния и их преобразования. Построение таблиц истинности логических выражений.

Основные понятия и операции алгебры логики

Формальной логикой принято называть античную логи­ку, основанную Аристотелем. Это название происходит от основного принципа логики как науки, который гласит, что правильность рассуждения (умозаключения) определяется только его логической формой, или структурой, и не зависит от конкретного содержания входящих в него суждений [16].

Логика изучает формы мышления с точки зрения их структуры, законы и правила получения некоторого знания. Формами мышления являются: понятие, суждение, умоза­ключение.

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

Суждение — форма мышления, в которой что-либо утвер­ждается или отрицается о наличии предмета, его свойствах и действиях. Характеризуется содержанием и формой. Со­держанием суждения является его смысл. Форма — способ построения. Суждения бывают истинными и ложными.

Умозаключение — форма мышления, в которой из одно­го или нескольких суждений на основании определенных правил вывода получается новое суждение (вывод, или за­ключение).

В своем развитии логика прошла ряд этапов. Современную логику называют математической. Алгебра высказываний (алгебра логики) — раздел математической логики.

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

Учение о высказываниях, называемое алгеброй выска­зываний (алгеброй логики), является первой из формаль­ных логических теорий. Объектами алгебры логики явля­ются высказывания.

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


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

Исходные высказывания могут быть логическими кон­стантами (если имеют постоянное значение «истина» или «ложь») или логическими переменными.

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

Логические операции позволяют каждой формуле при за­данных значениях входящих в нее высказываний приписать одно из двух значений: 0 или 1. Тем самым каждая формула может рассматриваться как некоторый способ задания или реализации функции алгебры логики. Логическая функ­ция — это функция, определенная на множестве значений (истина, ложь) и принимающая значение из того же множе­ства [16]. Например: Л = А&В, F2 = AvB.

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