Основы информатики

запоминаемость;

передаваемость;

преобразуемость;

воспроизводимость;

стираемость

Информация как философская категория.

Понятие информации нельзя считать лишь техническим, междисциплинарным и даже наддисциплинарным термином. Информация это фундаментальная философская категория.

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

Социальная значимость информации.

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

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

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

Лекция 3. Основные парадигмы и технологии программирования

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

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

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

Предтечи программирования - английские математики Чарльз Бэббидж, который в 20-х годах XIX в. высказал мысль о предварительной записи порядка действий машины для последующей автоматической реализации вычислений - программе, которую можно было записывать на перфокартах. И Ада Августа Лавлейс, которая в 1843г. издала перевод на английский язык статьи итальянского ученого Минебраа о вычислительных машинах со своими комментариями.

В комментариях к статье излагались принципы, ставшие основой теории программирования

введено понятие цикла

сформулирован принцип экономии рабочих ячеек

сформулирован принцип хранимых данных

обозначена связь рекуррентных формул с циклическими процессами вычислений

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

Напоню, что вычислительная техника в XIX веке существовала, только это была механическая техника - арифмометры и подобные им вещи

Машинно-ориентированное программирование

На начальном историческом этапе возникновения в 40-х годах XX века первых электронных вычислительных машин, возникло машинно-ориентированное программирование, являющееся допарадигмальным.

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

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

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

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

Машинно-ориентированные языки называют также языками низкого уровня. В дальнейшем для облегчения труда программистов были созданы языки программирования, которые строились на основе определенного алфавита и строгих правил построения предложений. Отличительной особенностью этих языков является их ориентация не на систему команд той или иной ЭВМ, а на систему операторов, характерных для записи определенного класса алгоритмов. Такие языки принято называть языками программирования высокого уровня. К ним, в первую очередь, относят: Fortran, PL, Algol, C, Basic. С возникновением языков высокого уровня формируется первая парадигма программирования - императивная.

Императивная парадигма

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

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

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

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

Методология структурного программирования появилась как следствие возрастания сложности решаемых на компьютерах задач и соответственного усложнения программного обеспечения. В 70-е годы XX века объёмы и сложность программ достигли такого уровня, что «интуитивная» разработка программ, которая была нормой в более раннее время, перестала удовлетворять потребностям практики.

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

В соответствии с методологией структурного программирования любая программа представляет собой структуру, построенную из трёх типов базовых конструкций:

последовательного исполнение (следование) - однократное выполнение операций в том порядке, в котором они записаны в тексте программы;

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

цикл - многократное исполнение одной и той же операции до тех пор, пока выполняется некоторое заданное условие (условие продолжения цикла.

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

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

Разработка программы ведётся пошагово, методом «сверху вниз». Сначала пишется текст основной программы, в котором вместо каждого связного логического фрагмента текста вставляется вызов подпрограммы, которая будет выполнять этот фрагмент. Вместо настоящих, работающих подпрограмм, в программу вставляются «заглушки», которые ничего не делают. Полученная программа проверяется и отлаживается. После того, как программист убедится, что подпрограммы вызываются в правильной последовательности (то есть общая структура программы верна), подпрограммы-«заглушки» последовательно заменяются на реально работающие, причём разработка каждой подпрограммы ведётся тем же методом, что и основной программы. Разработка заканчивается тогда, когда не останется ни одной «заглушки», которая не была бы удалена. Такая последовательность гарантирует, что на каждом этапе разработки программист одновременно имеет дело с обозримым и понятным ему множеством фрагментов и может быть уверен, что общая структура всех более высоких уровней программы верна.

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

Первыми языками высокого уровня, относящиеся к этой пардигме были Fortran,PL/1, Ада, Бейсик.

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

Декларативная парадигма

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

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

Поясним это на следующем примере. Предположим, вам надо пройти в городе из пункта А в пункт Б. Декларативная программа - это план города, в котором указаны оба пункта, плюс правила уличного движения. Руководствуясь этими правилами и планом города, курьер сам найдет путь от пункта А к пункту Б. Императивная программа - это список команд примерно такого рода: от пункта А по ул. Садовой на север до площади Славы, оттуда по ул. Пушкина два квартала, потом повернуть направо и идти до Театрального переулка, по этому переулку налево по правой стороне до дома 20, который и есть пункт Б.

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

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

Наиболее существенными классами декларативных языков являются функциональные (functional) языки, например, Lisp (Лисп), и логические (logic) языки, например, Prolog (Пролог).

Функциональное программирование

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

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

Логическое программирование

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

Объектно-ориентированное программирование

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

Возникновение объектно-ориентированного программирования связано с ответом на вопрос: «что главное в программе - алгоритм или данные, которые он обрабатывает»? Вначале, когда компьютер умел работать только с числами, главным был алгоритм. Однако, по мере роста абстрактности данных (символы, строки, массивы, множества, звук, изображение) ошибки стали возникать из-за того, что правильный алгоритм применяли к неправильным (несоответствующим) данным. Стало ясно, что данные должны как-то храниться вместе с фрагментами алгоритма для их обработки. Так возникло понятие объекта.

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

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

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

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

Наследование как раз и позволяет выполнить какие-то стандартные процедуры немного по-другому, например, рисовать похожие, но разные окна, наследуя их от одного окна.

Третий принцип ООП - полиморфизм - возможность для каждого объекта иерархии выполнить одно и то же действие, но по-своему. Например, высветить объект «точка», объект «окно», и т.д.

Итак, в основе ООП лежат три основных понятия:

инкапсуляция (сокрытие данных в классе или методе);

наследование;

полиморфизм.

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

Наследование - это процесс, в результате которого один тип наследует свойства другого типа.

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

Объектно-ориентированное программирование - очень мощный метод при разработке больших программ, резко возрастает КПД работы программиста и снижается количество ошибок. Для большинства языков были созданы большие библиотеки готовых объектов. Практически все современные языки программирования, независимо от принадлежности к тому или иному стилю (императивному или декларативному), поддерживают концепцию ООП. Среди них Delphi, C++, Java, Ruby и Haskell. Существуют и версии объектно-ориентированного Пролога (например, Visual Prolog).

В языках С++, Delphi сменилась терминология: иерархии объектов называются классами, а сами объекты - экземплярами классов.

Визуальное программирование

Визуальное программирование основано на ООП и возникло вслед за возникновением и распространением графического интерфейса операционных систем. Основополагающая идея визуального программирования заключается в перетаскивании объектов мышкой из библиотеки (хранилища объектов) в нужное место программы. А система сама должна написать нужный для этого код. Так работают Delphi, C++ Builder, Visual C, Visual Basic и др.

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

Главная особенность визуального программировнаия - Возможность автоматической генерации программного кода

Параллельное программирование

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

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

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

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

Определение параллелизма: анализ задачи с целью выделить подзадачи, которые могут выполняться одновременно;

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

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

В настоящее время существует более 100 различных средств, позволяющих разрабатывать параллельные программы. Наиболее известные технологии: OpenMP, стандарт которой был разработан для языков Fortran, C и C++ ; система параллельного программирования PVM (Parallel Virtual Machine), позволяющая объединить набор разных компьютеров, связанных сетью, в общую вычислительную систему, называемую параллельной виртуальной машиной (поддерживает языки Fortran, C, C++, имеет средства сопряжения с языками Perl, Java); технология программирования CUDA (Compute Unified Device Architecture) - программно-аппаратное решение, позволяющее использовать видеопроцессоры NVIDIA для вычислений общего назначения; технология MPI - интерфейс передачи данных (message passing interface).

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

Сценарное программирование

Возникшее, с появлением глобальной сети Internet, Web-программирование и языки его реализующие, определяют формирование современной, сценарной технологии программирования. Первое из средств создания Web-страничек - это язык разметки гипертекстов HTML, с помощью которого можно было создавать несложные сайты, снабженные системой гиперссылок и необходимым компьютерным дизайном - различными стилями оформления, иллюстрациями (картинками) и фонами страничек. Для создания более сложных и функциональных интерактивных сайтов сейчас имеется довольно разнообразный выбор инструментальных средств - ASP, PHP, Perl, Pyton, Java-script и т.п.

Развитие языков программирования с точки зрения различных парадигм и технологий представлено на рис.2.2.

Рис. 2.2. Развитие языков программирования

Основные этапы решения задач на компьютере

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

Рассмотрим эти этапы на примере решения квадратного уравнения.

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

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

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

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

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

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

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

Замечание. Свойство детерминированности объединяет в себе одновременное выполнение свойств точности и понятности. Поясним эти свойства.

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

Понятность (для данного исполнителя) - алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно. Это означает, что одно и то же предписание после исполнения должно давать один и тот же результат. То есть запись алгоритма должна быть настолько четкой и полной, чтобы у исполнителя не возникало потребности в принятии каких-либо самостоятельных решений, не предусмотренных составителем алгоритма. Алгоритм всегда рассчитан на выполнение «не размышляющего» исполнителя.

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

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

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

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

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

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

Элементарные шаги алгоритма при укрупнении объединяются в алгоритмические конструкции: линейные (последовательные), ветвящиеся, циклические, рекурсивные. В 1969 году Эдсгер В. Дейкстра в статье «Структуры данных и алгоритмы» доказал, что для записи любого алгоритма достаточно трех основных алгоритмических конструкций: линейных (последовательных), ветвящихся, циклических.

Алгоритм Р реализован через последовательную алгоритмическую конструкцию, если каждый шаг алгоритма Р выполняется один раз, причем после каждого i-го шага выполняется (i +1)-й шаг, если i-й шаг - не конец алгоритма.

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

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

Алгоритм R называется рекурсивным, если на каком-либо шаге он прямо или косвенно обращается сам к себе.

существует много разных возможностей для представления (описания) одного и того же алгоритма:

словесное описание;

псевдокод;

запись в виде блок-схемы;

запись алгоритма на каком-либо языке программирования;

формальное представление алгоритма в виде машины Тьюринга или машины Поста.

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

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

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

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

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

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

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

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



Четвёртый этап - программирование.

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

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

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

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

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

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

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

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

Лекция 4. HTML

HTML (HyperText Markup Language) - язык разметки гипертекста. Отнести HTML к языкам программирования можно лишь с большой натяжкой, это все-таки язык РАЗМЕТКИ. Из названия становится понятным его предназначение - указывать браузеру, как разместить элементы на странице при ее отображении на экране монитора. Что такое html элемент? Да все, что мы размещаем: текст, рисунки, анимации и т.д. С помощью HTML мы можем указать браузеру где именно их разместить; какой текст сделать большим и жирным, а какой - маленьким курсивом; где начать новую строку, а где сделать переход на другую страницу. И многое другое

Тело документа - тег BODY

Все, что отображается на web-странице, находится в тегах <body> </body>. Это текст, картинки и исполняющиеся скрипты, а также теги для оформления всего этого. Обязательных параметров у тега нет, да и применение необязательных параметров тоже не приветствуется. Тем не менее, большинство параметров до сих пор поддерживается разными браузерами. Рассмотрим те, которые пока поддерживаются всеми браузерами:

alink - устанавливает цвет активной ссылки. Текущий цвет ссылки меняется на активный при нажатии на нее.

vlink - устанавливает цвет посещенной ссылки, т.е. той, по которой уже щелкали.

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

bgcolor - указывает фоновый цвет документа.

leftmargin - определяет отступ от левого края окна браузера до контента страницы.

rightmargin - определяет отступ от правого края окна браузера до контента страницы.

topmargin - определяет отступ от верхнего края окна браузера до контента страницы.

bottommargin - определяет отступ от нижнего края окна браузера до контента страницы.

text - устанавливает цвет текста для всего документа

Пример:

<html>

<head>

<title> пример использования фона</title>

</head>

<body background="images/fon.jpg" bgcolor="grey">

Здесь будет содержание странички

</body>

Форматирование текста

Для форматирования текста существует много тегов. Одни их них используются часто (и их вы быстро запомните), другие - редко (их и не надо запоминать). Здесь мы рассмотрим те, которые используются часто. Теги, делающие текст заголовками

<h1> </h1>

<h2> </h2>

<h6> </h6>

Эти теги выделяют текст в виде заголовков. Т.е. каждый заголовок начинается с новой строки, выделен полужирным шрифтом и имеет свой размер (заголовок первого уровня самый большой, шестого - самый маленький). Эти теги могут использоваться с параметром горизонтального выравнивания align. Возможные значения этого параметра: left - слева, right - справа, center - по центру, jastify - по ширине.

Теги разделения на абзацы и переноса строки

Тег <br>- тег принудительного перевода строки. Текст, после этого тега начинается с новой строки. Теги <p> </p>

разделяют текст на абзацы. Перед началом каждого абзаца следует поместить тег <p>

, закрывающий тег не обязателен. В отличии от тега <br> абзацы отделяются друг от друга пустой строкой. У тега<p> есть параметр align, который задает способ выравнивания текста внутри параграфа. Возможные значения этого параметра: left - слева, right - справа, center - по центру, jastify - по ширине.

Начертание текста

<b> </b> - жирный

<i> </i> - курсив

<u> </u> - подчеркнутый

Тег font и его параметры

Теги <font> </font> указывают параметры шрифта текста: face - название шрифта. Названий шрифтов можно привести несколько, через запятую. В этом случае, если первый указанный шрифт не будет найден (вы же не знаете, какие шрифты установлены на компьютере пользователя), браузер станет использовать следующий по списку. size - размер шрифта в условных единицах от 1 до 7. По умолчанию размер шрифта равен 3. color - цвет текста (по умолчанию - черный).

Тег center

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

Ссылки

Ссылка - тег a Ссылка - одно из важнейших понятий для html-документов. Бродя по интернету, вы щелкаете по кнопочкам и текстам и попадаете на нужные вам страницы. Эти страницы могут находиться на том же сервере, а могут и на сервере, находящемся на другом конце планеты. Но в обоих случаях переход осуществляется практически мгновенно. А как вы узнаете, куда надо щелкнуть, чтобы перейти на другую страницу? Либо визуально (цвет ссылки другого цвета и подчеркнут), либо по курсору мыши, который превращается в ладошку. За все эти преображения отвечает тег-контейнер . А за то, куда направить пользователя по щелчку - его атрибут - href. Рассмотрим подробнее:

Пример:

<html>

<head>

<title>Ссылки в html</title>

<head>

<body>

Здесь будет содержание страницы

<br>Открыть

<a href="primer.html" target="_blank">

пример

</a>

</body>

</html>

Если вы щелкните по ссылке, то перейдете на сайт www.yandex.ru. Обратите внимание, когда вы подводите курсор мыши к ссылке, внизу (в строке состояния) отображается адрес, на который ведет ссылка. Итак, между тегами пишется текст, при щелчке по которому осуществляется переход. А в качестве значения атрибута href выступает адрес страницы, на которую будет осуществлен переход. Об адресе следует поговорить подробнее.

Существуют два способа задания URL-адреса: абсолютный и относительный. О том, что такое URL читайте на странице что такое URL. Рассмотрим на примере. Пусть у нас есть сайт с зарегистрированным доменом - mysite.ru. Все страницы сайта у нас хранятся на сервере в двух папках public и private. При этом в папке public содержатся файлы index.html и articles.html, а в папке private - price.html и cinema.html. Т.е. наш сайт имеет следующую структуру

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

<a href=”http://www.mysite.ru/public/index.html”>

А страницы cinema.html

<a href=”http://www.mysite.ru/ private / cinema.html” >

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

<a href=” articles” >

Если же мы захотим сделать ссылку со страницы index.html на страницу price.html, то, учитывая, что страницы лежат в разных каталогах, она будет выглядеть следующим образом

<a href=”../ private / cinema.html” >

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

Вы знаете, что при щелчке по ссылки, документы могут открываться как в текущем окне, так и в новом. Этим процессом можно управлять. По умолчанию ссылки загружаются в то же окно, но если указать параметр target="_blank", то ссылка загрузится в новое окно

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

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

Пример

<html>

<head>

<title>Ссылки в html</title>

<head>

<body>

Здесь будет содержание страницы

<br>Открыть <a href="primer.html" target="_blank" title="показать пример">пример

</a>

<p><font size=10 color="red"><a name="top"></a>

<a href="#inf"> Информатика</a>

<br><a href="#cib"> Кибернетика</a>

</font>

</p>

<p>

<font size=5 color="blue">

<br><a name="inf"></a>Информатика - это наука, общие свойства и структуру информации,

<br>а также закономерности и принципы ее создания, преобразования,

<br>накопления, передачи и использования в различных областях

<br>человеческой деятельности. Понятно, что современный поток

<br>информации человечество может воспринять только с помощью

<br>компьютеров, которые осуществляют автоматическую обработку информации.

<br>Сразу отметим, что не создание вычислительной техники

<br>следует считать отправной точкой в возникновении информатики.

<br>Компьютер сам по себе является продуктом длительного развития

<br>вычислительных устройств и его можно рассматривать

<br>только лишь как инструмент, средство информатики.

<br>Появление компьютеров повлияло на темпы становления информатики,

<br>ее характер и содержание. Но связывать возникновение информатики

<br>только с появлением компьютеров или, наоборот, считать появление

<br>компьютера результатом развития информатики было бы неверно.

<br>Формирование исходных теоретических основ и понятий

<br>информатики началось еще до появления первых вычислительных

<br>машин. Своим развитием информатика обязана ряду наук,

<br>в том числе математике, теории связи, экономике, электронике,

<br>теории управления, лингвистике и особенно киберенетике

</font></p>

<p><font size=10 color="blue">

<br><a name="cib"></a>Кибернетика как наука об общих закономерностях в

<br>управлении и связи в различных системах: искусственных,

<br>биологических, социальных возникла и начала бурно развиваться

<br>после второй мировой войны. Рождение кибернетики принято

<br>связывать с опубликованием (1948г.) американским математиком

<br>Норбертом Винером ставшей знаменитой книги

<br>«Кибернетика или управление и связь в животном и машине".

</p>

<p><a href="#top"> Наверх</a></p>

</body>

</html>

Встраивание изображений

Для размещения на странице изображений используется тег <img>, имеющий единственный обязательный параметр src, определяющий URL-адрес изображения.

Пример

<html>

<head>

<title> пример использования фона</title>

</head>

<body background="images/fon.jpg" bgcolor="grey">

<img src="images/fon1.jpg" width=150 height=150>

Здесь будет содержание странички

</body>

</html>

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

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

align="left" Картинка слева, а текст обтекает ее справа и этот текст может занимать несколько строчек

align="right" Картинка справа, а текст обтекает ее слева и этот текст может занимать несколько строчек.

align="top" Верхняя граница изображения выравнивается по самому высокому элементу текущей строки. Изображение как бы встраивается в строчку. Если изображение большое, то и строка раздвигается на эту высоту.

align="middle" Выравнивание середины изображения по базовой линии текущей строки.

И т.п.

Если же мы хотим, чтобы текст располагался под картинкой, то необходимо использовать тег <br>

с параметром clear, который запрещает обтекание. Обтекание можно запретить с правой стороны (right), с левой стороны (left) и с обеих сторон (all).

Размеры изображений

Любое изображение имеет размер, заданный в пикселах. При встраивании изображения на страницу, возможно вам понадобиться уменьшить размер исходной картинки. Для этого у тега <img> существуют параметры width - ширина и height - высота. Они задаются в пикселах или в процентах (процент от ширины экрана) При загрузке изображения браузер будет автоматически масштабировать вашу картинку к заданным параметрам ширины и высоты. Только имейте в виду, что неаккуратное задание параметров, может привести к изменению пропорций рисунка, а следовательно, к его искажению

Отделение изображения от текста

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

Альтернативный текст

Если у пользователя отключен режим загрузки изображений, то вместо картинки он увидит красный крестик (в Internet Explorer) или другую иконку (в других браузерах). Неплохо было бы дать ему подсказку, что изображено на рисунке. Для этого используется параметр alt. Текст из этого параметра будет отображаться вместо картинки ( если отключен режим загрузки изображений). В случае же, если картинка отображается, этот параметр дает подсказку при наведении курсора мыши, правда, не во всех браузерах.

...