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

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


Смотрите также:
Программа вступительных испытаний по «Методам вычислений»...
Средства программирования...
Учебно-методический комплекс «информационные технологии в рекламе» для специальности 032401...
Рабочая программа По дисциплине «Разработка программного обеспечения» По специальности 230102...
Авторская программа элективного курса по информатике для учащихся 9-х классов «Ветвление на...
Учебная программа по дисциплине параллельное программирование астрахов А. В...
Отчет о научно-исследовательской работе разработка математического и программного обеспечения...
Разработка алгоритмического и программного обеспечения библиотеки программ для решения...
Лекция содержит фундаментальные понятия машинных алгоритмов и их использование для...
Разработка методики и программы для оценки последствий столкновений ка с космическим мусором >...
Методические указания по лабораторным работам По дисциплине...
«Исследование и разработка программного обеспечения понимания неструктурированной текстовой...



Загрузка...
скачать
Алгебра логики в информатике


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

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

  • булева логика и алгебра для разработки аппаратного обеспечения компьютеров;

  • фундаментальные понятия и представления для компьютерных наук, которые являются естественной областью для формальной логики. Например, семантика языков программирования[3];

  • логика для описания пространственного положения и перемещения;

  • логика для эквивалентного преобразования объектов. Например, λ-исчисление;

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

  • Эффективность логики в компьютерных науках

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

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

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

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

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

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

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

  • Наибольший эффект в освоении технологий доказательного программирования наблюдается в олимпиадах по информатике и программированию, где победителями и призёрами становятся те студенты, которые освоили технику тестирования программ на ЭВМ и составления алгоритмов и программ без ошибок.

  • ^ Алгебра логики (булева алгебра) – это раздел математики, возникший в XIX веке благодаря усилиям английского математика Дж. Буля. Поначалу булева алгебра не имела никакого практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем. Законы и аппарат алгебры логики стал использоваться при проектировании различных частей компьютеров (память, процессор). Хотя это не единственная сфера применения данной науки.

  • Что же собой представляет алгебра логики? Во-первых, она изучает методы установления истинности или ложности сложных логических высказываний с помощью алгебраических методов. Во-вторых, булева алгебра делает это таким образом, что сложное логическое высказывание описывается функцией, результатом вычисления которой может быть либо истина, либо ложь (1, либо 0). При этом аргументы функции (простые высказывания) также могут иметь только два значения: 0, либо 1.

  • Что такое простое логическое высказывание? Это фразы типа «два больше одного», «5.8 является целым числом». В первом случае мы имеем истину, а во втором ложь. Алгебра логики не касается сути этих высказываний. Если кто-то решит, что высказывание «Земля квадратная» истинно, то алгебра логики это примет как факт. Дело в том, что булева алгебра занимается вычислениями результата сложных логических высказываний на основе заранее известных значений простых высказываний.
  • ^

    Логические операции. Дизъюнкция, конъюнкция и отрицание


  • Так как же связываются между собой простые логические высказывания, образуя сложные? В естественном языке мы используем различные союзы и другие части речи. Например, «и», «или», «либо», «не», «если», «то», «тогда». Пример сложных высказываний: «у него есть знания и навыки», «она приедет во вторник, либо в среду», «я буду играть тогда, когда сделаю уроки», «5 не равно 6». Как мы решаем, что нам сказали правду или нет? Как-то логически, даже где-то неосознанно, исходя из предыдущего жизненного опыта, мы понимает, что правда при союзе «и» наступает в случае правдивости обоих простых высказываний. Стоит одному стать ложью и все сложное высказывание будет лживо. А вот, при связке «либо» должно быть правдой только одно простое высказывание, и тогда все выражение станет истинным.

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

  • Алгебра логики предусматривает множество логических операций. Однако три из них заслуживают особого внимания, т.к. с их помощью можно описать все остальные, и, следовательно, использовать меньше разнообразных устройств при конструировании схем. Такими операциями являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ). Часто конъюнкцию обозначают &, дизъюнкцию - ||, а отрицание - чертой над переменной, обозначающей высказывание.

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

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

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

    Таблицы истинности


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


  • ^

    Логические основы компьютера


  • В ЭВМ используются различные устройства, работу которых прекрасно описывает алгебра логики. К таким устройствам относятся группы переключателей, триггеры, сумматоры.

  • Кроме того, связь между булевой алгеброй и компьютерами лежит и в используемой в ЭВМ системе счисления. Как известно она двоичная. Поэтому в устройствах компьютера можно хранить и преобразовывать как числа, так и значения логических переменных.
  • ^

    Переключательные схемы


  • В ЭВМ применяются электрические схемы, состоящие из множества переключателей. Переключатель может находиться только в двух состояниях: замкнутом и разомкнутом. В первом случае – ток проходит, во втором – нет. Описывать работу таких схем очень удобно с помощью алгебры логики. В зависимости от положения переключателей можно получить или не получить сигналы на выходах.
  • ^

    Вентили, триггеры и сумматоры


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

  • Триггеры и сумматоры – это относительно сложные устройства, состоящие из более простых элементов – вентилей.

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

  • Сумматоры широко используются в арифметико-логических устройствах (АЛУ) процессора и выполняют суммирование двоичных разрядов.
^

Решение задач


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

Содержание



Стадии решения задачи


Процесс решения задачи состоит из таких основных подпроцессов, как:

  • Обнаружение проблемной ситуации;

  • Постановка задачи: выявление и более или менее строгое определение исходного (данного) — его элементов и отношений между ними — и требуемого (цели);

  • Нахождение решения задачи.

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

^ Стадии решения задачи в теориях О. Зельца, К. Дункера, Грино

О. Зельц

^ К. Дункер

Грино

1. Образование комплекса, в который входят: а) характеристики известного и б) отношения известное-неизвестное, определяющие в) место неизвестного в комплексе. Незавершённость этого комплекса — суть проблемности.

1. Проникновение в проблемную ситуацию — понимание её внутренних связей, восприятие её как целого, заключающего в себе некий конфликт.

1. Построение когнитивной сети, состоящей из элементов известного (данного) и неизвестного (отношения между элементами известного и неизвестного пока не установлены).

2. Запуск интеллектуальных операций: припоминание или создание решения.

2. Нахождение функционального значения решения.
3. Реализация (воплощение) функционального значения в конкретное решение.

2. Построение связей (отношений) между элементами , модификация сети при помощи дополнительной информации из памяти.
^

Психологические факторы


На ход решения задачи и успешность её решения влияют следующие факторы.[5]

  • Установка:

  • «Решение определённого числа задач одним способом побуждает испытуемого использовать тот же способ для решения последующих задач, даже если этот способ становится неэффективным». Как показал Найт[6], установка тем сильнее, чем труднее были задачи, её сформировавшие.

  • Функциональная закреплённость: используемый определенным образом предмет трудно потом использовать иначе при решении задачи.

  • Характеристики субъекта:

  • Эмоциональное (мотивационное) состояние:

  • Предшествующая неудача снижает эффективность решения;

  • Наилучшие результаты имеют место при средней интенсивности мотивации; чрезмерная или недостаточная мотивация приводит к ухудшению результатов (закон Йеркса — Додсона).

  • Знания: могут как повышать, так и снижать эффективность решения (из-за стереотипизации, привычки).

  • Интеллект: люди с низким интеллектом более восприимчивы к установке.

  • Личность: показано, что успешность решения задач связана с 1) гибкостью, 2) инициативой, 3) уверенностью, 4) нонконформизмом, 5) способностью сдерживать движения (очень медленно чертить линии и и т. п.).
^

Теории решения задач

Информационный подход


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

Представители информационного подхода исходили из того, что человек, так же как компьютер, оперирует символами (знаками), следовательно, вычислительные машины можно «использовать как устройства для имитации процесса человеческого мышления»[7]. Модели решения задач, которые они создавали, зачастую одновременно представляли собой компьютерные программы (наиболее известный пример — «Универсальный решатель задач» (англ.) Ньюэлла и Саймона, созданный в 1957 году).
^

Линдсей и Норман


Линдсей и Норман описывают решение задач следующим образом.[8]

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

Возможны две стратегии решения: прямой и обратный поиск. 1. При прямом поиске «человек сначала испытывает какой-то метод подхода к задаче, а затем смотрит, продвинулся ли он вперёд в результате его применения». 2. При обратном поиске «человек рассматривает искомое решение, задаваясь вопросом: какой предварительный шаг необходим для того, чтобы прийти к нему? После определения этого шага определяется шаг, непосредственно ему предшествующий, и т. д., в лучшем случае — вплоть до отправной точки, заданной в постановке исходной задачи». Обратный поиск осуществляется с помощью анализа средство-результат (сопоставления средств и целей): на каждом шаге данная промежуточная цель сравнивается с наличным состоянием осведомлённости и находится оператор — средство, уменьшающее разрыв.

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

Психофизиологические данные

Исследование О. К. Тихомирова


Появлению в сознании решения задачи предшествует эмоциональная активация и чувство близости решения.

Это установил О. К. Тихомиров, изучая процесс решения шахматных задач.[9] Он предлагал испытуемым рассуждать во время решения задачи вслух и параллельно регистрировал их кожно-гальваническую реакцию (КГР), которая служила признаком эмоциональной активации.

Эксперименты показали, что сначала возникает эмоциональная активация. За ней — обычно через 0—0.5 секунд — следуют эмоциональные восклицания («Ага!», «Ой!» и т. п.). За эмоциональными восклицаниями обычно следуют слова, обозначающие чувство близости решения: приближение к неосознанной ещё идее («так-так-так-так», «вот-вот-вот-вот», «наверное…») или ещё неясные результаты поиска («что-то мелькнуло», «что-то есть», «кажется, нашёл», «кажется, решено»); реже это выражение необходимости попробовать («попробуем-попробуем», «интересно-интересно»), сомнения («„а“… „а“… или не „а“?») или сигналы самоостановки («стоп-стоп-стоп-стоп»); ещё реже сразу называется решение. За этим следует решение — называние конкретного принципиального для решения задачи хода, — через 1.5—13.5 секунд после появления эмоциональной активации, в среднем — через 5.5 секунд.
^

Решение задач животными


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

Метод проб и ошибок


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

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

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

Однако некоторые данные самого Торндайка говорят против его теории. Так, в случаях с некоторыми «ленивыми» кошками Торндайка «внимание, которое нередко сочетается с недостатком энергии, позволяло кошке быстрее образовать ассоциацию после первой удачи»[10]. А заменив впоследствии (1901) кошек обезьянами, Торндайк обнаружил, что почти все задачи решались «путём быстрого, нередко казавшегося мгновенным, оставления безуспешных движений и выбора правильного... Естественно заключить, что обезьяны, внезапно переходящие от множества беспорядочных движений к одному определенному действию с крючком или задвижкой, имеют понятие о крючке, о задвижке или о том движении, которое они производят»…

Р. Вудвортс отмечает, что «не было обнаружено ни одного случая такого поведения в проблемной ситуации, когда животное бросалось бы на все окружающее без всякого учета объективной ситуации. Животное всегда реагирует на те или иные предметы, и почти всем его реакциям присуща известная степень правомерности. Метод проб и ошибок состоит не в слепых, рассчитанных на случайную удачу движениях, а в испробовании определенных путей к цели. Насколько мы можем судить по поведению животного, у него всегда имеется некоторое схватывание объективной ситуации. Другое дело, что в любой ситуации, которую можно назвать проблемной, это схватывание никогда не бывает с самого начала полным. Ситуация должна быть исследована, а это редко может быть сделано без передвижений и манипулирования. Но даже при первом взгляде на ситуацию общие очертания проблемы вскрываются в достаточной мере, чтобы до известной степени ограничить область исследования и манипулирования».[11]

Инсайт


Решение задач путём внезапного озарения (инсайта), понимания ситуации, проникновения в её суть описано В. Кёлером. Эксперименты Кёлера демонстрируют следующие примеры того, как это происходит.[12]

  • Курица, видя перед собой цель, отделённую от неё некоторым препятствием (забором), «совсем беспомощна, постоянно налетает, если видит цель перед собою сквозь решётку, на препятствие, беспокойно бегая туда и сюда», и не способна добраться к этой цели иначе как с помощью таких метаний, лишь постепенно приближающих её к цели (что напоминает описания Торндайка). Напротив, собака или ребёнок (например, девочка 1 года 3 мес., едва научившаяся ходить), оценив пространственные характеристики ситуации, могут сразу найти кратчайший обходной путь.

  • Обезьяна способна схватить палку и достать ею еду, находящуюся вне клетки (без всяких проб и ошибок).

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

  • Шимпанзе влезает на ящик или даже ставит ящики друг на друга, чтобы достать высоко висящий плод.
^

Использование орудий


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

Примеры использования орудий животными:

  • Грифы бросают камни на яйца страусов, чтобы разбить их. (Это не новое наблюдение; легенда гласит, что Эсхил погиб, когда орёл сбросил ему на голову не то черепаху, приняв лысину Эсхила за камень, не то камень, приняв его лысину за яйцо.)

  • Дятловый вьюрок достаёт насекомых из щелей коры колючкой кактуса.

  • Шимпанзе пользуются палками, прутьями, стеблями травы для добывания термитов, мёда, выкапывания растений; используют листья как губку для добывания воды из дупла и для чистки тела. Павианы прутьями добывают насекомых, камнями давят скорпионов.
^

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


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

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

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

От языка Planner также произошли логические языки программирования QA-4, Popler, Conniver и QLISP. Языки программирования Mercury, Visual Prolog, Oz и Fril произошли уже от языка Prolog. На базе языка Planner было разработано также несколько альтернативных языков логического программирования, не основанных на методе поиска с возвратами (backtracking), например, Ether .




Скачать 172,23 Kb.
оставить комментарий
Дата21.09.2011
Размер172,23 Kb.
ТипРешение, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх