Описание последовательности действий, которые должен выполнить компьютер для решения задачи
Обновлено: 01.07.2024
Компьютеры и программное обеспечение идут рука об руку. Компьютеры сильны, потому что они могут делать много вещей, а программы — это то, как мы заставляем компьютеры делать все это.
Видео: что такое программирование?
Компьютерное оборудование
- Центральный процессор (ЦП)
- Основная память (оперативная память или ОЗУ)
- Дополнительные устройства хранения
- Устройства ввода
- Устройства вывода
ЦП
ЦП — это сердце компьютера. Программа – это последовательность инструкций, хранящихся в оперативной памяти. Когда программа запускается, ЦП получает инструкции и выполняет или следует инструкциям.
Цикл выборки/декодирования/выполнения
- fetch — получение следующей инструкции из основной памяти.
- декодировать — определить, какую инструкцию выполнять.
- выполнить — выполнить инструкцию.
Каждая программа представляет собой последовательность основных инструкций, состоящую из арифметических и логических операций, а также операций управления потоком.
Арифметические и логические операции включают сложение, вычитание, умножение, деление и сравнение значений (равенство, меньше, больше).
Операции потока управления используются для определения следующей инструкции. Например, в зависимости от инструкции программа может пропустить или перейти к другой части списка инструкций.
Вы узнаете подробности о том, как ЦП обрабатывают инструкции в CS 271, Компьютерная архитектура и язык ассемблера.
Основная память
Основная память или ОЗУ используется для хранения программы во время ее выполнения и для хранения данных, с которыми работает программа.
Сведения об оперативной памяти
- ЦП может быстро получить доступ к любому месту в ОЗУ.
- ОЗУ называется энергозависимой памятью. В отличие от постоянного хранилища, когда компьютер выключается или когда программа завершает выполнение, значения, хранящиеся в ОЗУ, стираются.
- ОЗУ делится на единицы хранения, называемые байтами. Байт — это последовательность из восьми битов.
- Бит — это наименьший элемент ОЗУ, в нем хранится двоичная цифра, 0 или 1. Каждая программа и каждое значение данных на вашем компьютере хранится в виде последовательностей нулей и ls.
Дополнительное хранилище
Вторичное хранилище обеспечивает длительное и постоянное хранение. В отличие от оперативной памяти, данные, хранящиеся во вторичном хранилище, не исчезают при выключении или перезагрузке компьютера. Наиболее распространенной формой вторичного хранилища для больших компьютеров является дисковый накопитель, но компьютеры могут использовать и другие формы вторичного хранилища, например твердотельные накопители, в которых используются микросхемы памяти, сохраняющие значения данных без питания.
Как и в основной памяти, во вторичном хранилище также хранится информация в виде последовательностей нулей и единиц в виде битов и байтов.
Устройства ввода
Обычно мы думаем о клавиатурах и мышах, но устройства ввода могут включать в себя камеры, микрофоны и многие другие типы различных датчиков, когда вы начинаете думать о компьютерах, встроенных в автомобили, электронику и почти любое электрическое устройство.
Устройства вывода
Информация, которую компьютер отправляет во внешний мир, называется выводом. Если задействован человек, выходные данные обычно отправляются на устройство вывода, такое как экран компьютера или принтер. Не все программы будут выводить данные на устройство вывода. Вместо этого выходные данные могут быть отправлены по компьютерной сети или сохранены в базе данных.
Видео: аппаратное и программное обеспечение
Программы и языки программирования
Как сказано выше, программирование включает в себя создание набора инструкций, которым компьютер будет следовать, чтобы решить проблему или выполнить задачу. Давайте уточним нашу терминологию в этом разделе.
Алгоритмы
Алгоритм задает конечную последовательность четко определенных операций для решения конкретной проблемы или класса проблем. Шаги алгоритма можно описать разными способами, включая слова (также известные как естественный язык), блок-схемы, псевдокод (описанный ниже) и код языка программирования.
По мере увеличения сложности задач важно разрабатывать алгоритмы, которые будут эффективными (т. е. быстрыми) и правильными в том смысле, что они будут давать указанный результат для любых допустимых входных данных. На курсе CS 325 "Анализ алгоритмов" вы узнаете о методах анализа сложности и доказательства правильности.
Превращение алгоритмов в программы
Алгоритм может быть реализован на многих различных компьютерных языках, и одна программа может использовать или реализовывать множество различных алгоритмов. Например, вы можете использовать алгоритм сортировки для упорядочивания сообщений и алгоритм расшифровки для понимания сообщений.
Машинный код, язык ассемблера и компиляторы
ЦП компьютера выполняет инструкции вашей программы. Однако пока вы пишете программу на таком языке, как C++, процессор компьютера может следовать только инструкциям, закодированным как последовательность Os и s.Программный компилятор — это специальная программа, которая преобразует операторы, написанные на языке программирования, в двоичную форму (Os и s>, называемую машинным кодом. Поскольку нам трудно распознать последовательности 0 и 1, существует низкоуровневая (близкая к аппаратной ) язык программирования, называемый языком ассемблера, который использует короткие сокращения и шаблоны для описания того, что должен делать ЦП. Например, оператор ассемблера "MOV AL, 61h;" означает копирование следующего значения (61h, шестнадцатеричное представление 97) в ячейку памяти " АЛ".
Вы узнаете гораздо больше о машинном коде и языке ассемблера в CS 271, Архитектура компьютера и язык ассемблера.
Языки высокого уровня
В этом классе вы изучите C++, язык высокого уровня. Языки высокого уровня — это компьютерные языки, которые скрывают многие низкоуровневые детали компьютерной системы и, как правило, используют более естественные слова и символы по сравнению со словами, такими как «MOV», на языке ассемблера, который является языком низкого уровня.
C++ — один из многих языков высокого уровня. Чтобы увидеть текущую популярность всех компьютерных языков, перейдите в индекс TIOBE.
Исходный код, объектный код и исполняемый код
Исходный код
Когда вы начнете создавать программы в этом классе, вы будете создавать исходный код. Исходный код сохраняется в простом текстовом файле, называемом исходным файлом.
Преобразование исходного кода в исполняемый код
Ваш компьютер не понимает исходный код. Вы должны использовать компилятор для преобразования исходного кода в исполняемый код, который вы можете запустить и запустить на своем компьютере.
Во время преобразования исходного кода в исполняемый файл компилятор C++ создаст объектный код.
Исходный код преобразуется компилятором в так называемый объектный код. Объектный код программы на C++ сохраняется в файлах с суффиксом .o или .obj. На последнем этапе, называемом связыванием, объектные файлы объединяются с любыми библиотечными подпрограммами (подпрограммами, предоставленными языком для использования вами) для создания окончательного исполняемого файла с расширением .exe.
В зависимости от того, как вы компилируете свою программу, вы можете увидеть или не увидеть различные этапы преобразования исходных файлов в исполняемый файл. Например, во многих IDE (интегрированных средах разработки, таких как Visual Studio, Code:: Blocks или XCode) промежуточные шаги выполняются автоматически, поэтому вы можете нажать кнопку «сборка», и исполняемый файл будет создан.
Из чего состоит программа?
Языковые элементы
Большинство языков программирования включают следующие элементы.
Ключевые слова
Ключевые слова – это слова, имеющие особое значение в языке. Их можно использовать только по прямому назначению. Также известны как зарезервированные слова.
Определяемые программистом идентификаторы
Идентификаторы, определяемые программистом, — это слова, которые вы выбираете как программист для определения переменных или процедур программирования.
Операторы
Операторы выполняют операции над одним или несколькими операндами. Операнд — это часть данных. Различные арифметические символы, такие как +, * и /, являются примерами операторов.
Пунктуация
Знаки препинания отмечают начало или конец оператора или отдельных элементов в списке.
Синтаксис
Правила, которые необходимо соблюдать при построении программы. Эти правила определяют, как вы можете комбинировать ключевые слова, определенные программистом идентификаторы, операторы и знаки препинания.
Специфика C++. Вы начнете изучать элементы языка, характерные для C++, в главе 2.
Строки и операторы
Мы часто думаем, что программы состоят из строк и операторов. Строка — это всего лишь одна строка в программе. Вы можете отображать номера строк в большинстве редакторов исходного кода IDE. В Visual Studio 2013 их необходимо включить, поскольку по умолчанию они отключены. Вы часто будете видеть ссылки на номера строк при компиляции программы и возникновении ошибки.
На снимке экрана показана программа с ошибкой. Когда программа была скомпилирована, выходные данные (серые окна выше) включали «source.cpp(B)», что указывало на то, что проблема была в строке 8 файла с именем source. цена за тысячу показов
Инструкция — это полная инструкция, которая заставляет компьютер выполнить какое-либо действие. Оператор может занимать более одной строки. Значение оператора станет более понятным, как только вы начнете программировать в главе 2.
Переменные
Инструкция — это полная инструкция, которая заставляет компьютер выполнить какое-либо действие. Оператор может занимать более одной строки. Значение оператора станет более понятным, как только вы начнете программировать в главе 2.
Ввод и вывод
Двумя наиболее важными факторами при программировании являются ввод и вывод.Многие программы, которые вы напишете для классных заданий, будут использовать ввод с клавиатуры. Программа запросит ввод, и вы наберете ответ. По мере прохождения программы обучения вы приобретете опыт работы с файлами, базами данных, веб-ресурсами и другими источниками ввода.
Во многих, если не во всех заданиях CS 161, вы будете направлять вывод программы на консоль. Вы не часто видите вывод консоли, если запускаете приложения в Windows или OS X, потому что эти типы прикладных программ используют графические пользовательские интерфейсы (GUI). Однако программирование с графическим интерфейсом добавляет гораздо больше работы по созданию программы, и наша работа в CS 161 состоит в том, чтобы научить вас основам программирования, поэтому мы будем придерживаться консольного вывода.
Пример вывода в консоль
Активность
Выберите хотя бы одно занятие, которое учащиеся могут активно вовлечь в изучение материала. Чем больше, тем лучше!
Просмотреть
Обобщите содержание раздела. Кроме того, не забудьте связать материал с тем, что будет дальше, чтобы помочь учащимся связать этот материал со следующим материалом.
Программирование включает в себя классификацию частей задачи, которые может выполнять цифровое устройство, точное описание задач, а затем перевод на язык, который может понять ЦП компьютера.
Одним из первых шагов программирования является постановка задачи, которая конкретно включает в себя то, что нужно выполнить.
Стандартные программы включают в себя многие функции, которые могут вам понадобиться, однако наличие базовых знаний в области программирования позволит вам создавать программное обеспечение, которое лучше соответствует вашим личным потребностям.
Большинство программных приложений позволяют выполнять настройку с помощью мини-программ, называемых макросами. Создание макросов позволяет выполнять сложные действия с помощью одной команды.
Вы можете создавать макросы в Microsoft Word и Excel.
Этот план представляет собой набор конкретных последовательных шагов, точно описывающих, что компьютерная программа должна сделать для завершения работы.
Алгоритмы могут звучать как компьютерный термин, но на самом деле вы используете их всякий раз, когда принимаете решение.
Компьютерные программисты пишут алгоритмы, используя блок-схемы и на естественном языке, например на английском, чтобы алгоритм могли увидеть и прочитать столько редакторов, сколько необходимо.
Блок-схема используется для предоставления ориентира при работе с процессом.
Псевдокод подобен плану.
Псевдокод использует разные уровни, показывающие поток действий внутри программы.
После того, как эта последовательность действий завершена, вопрос задается снова, что создает цикл.
Пока ответ на вопрос положительный, цикл будет повторять один и тот же набор действий.
При таком подходе программисты разбивают каждую задачу на подробные подзадачи.
Категории ввода называются классами, а объекты являются примерами элементов ввода, используемых в каждом классе.
Программисты, использующие объектно-ориентированный анализ, тратят много времени на идентификацию классов и установление взаимосвязей между каждым классом. Чтобы заставить алгоритм работать, программистам может потребоваться создать различные объекты, которые будут служить примерами класса.
Операционная система Unix была написана на C, и большинство современных операционных систем, таких как Microsoft Windows и Mac OS X, были основаны на Unix.
Java использует архитектурную нейтральность, что означает, что код нужно скомпилировать только один раз, что позволяет ему быть совместимым со многими различными процессорами.
Java чаще всего используется для написания приложений для смартфонов и планшетов на базе Android, а также для написания веб-приложений.
Swift – это язык программирования, представленный Apple, который позволяет программистам разрабатывать программное обеспечение для iOS и OS X, более простое в освоении и использовании, чем Objective C.
Контент, написанный для показа в Интернете, должен включать специальные символы, называемые тегами.
Теги управляют тем, как веб-браузеры отображают контент, включая изображения, текст и другой мультимедийный контент, помеченный тегами HTML.
Adobe Dreamweaver и Microsoft Visual Studio Express — популярные программы, помогающие создавать HTML-контент.
HTML5 — это пятая версия HTML, позволяющая интегрировать анимацию JavaScript и другие типы мультимедиа.
JavaScript был создан для работы с различными компонентами веб-страницы. JavaScript использует синтаксис и операторы, используемые в Java. JavaScript включает различные классы, представляющие популярные объекты, используемые на веб-страницах, включая кнопки, флажки и раскрывающиеся списки.
Другим популярным языком сценариев является VBScript.
Сотни форматов программирования используют XML для создания документов для использования в Интернете.
XML упаковывает данные в теги, которые можно отображать в Интернете.XML не использует предопределенные теги. Теги создаются автором документа XML. XML был разработан, чтобы упростить изменение данных, совместное использование, транспортировку и доступность.
Ajax позволяет обмениваться информацией и данными с сервером, который автоматически обновляет части веб-страницы без необходимости обновления.
Ajax обменивается данными без необходимости изменения данных, отображаемых на веб-странице. Это обеспечивает более отзывчивый пользовательский интерфейс.
JSON поддерживает асинхронную связь между браузером и сервером.
Компилятор может читать исходный код, который включает в себя инструкции по программированию, написанные на компьютерном языке высокого уровня, и переводит исходный код на определенный машинный язык.
Большинство языков программирования имеют собственный встроенный компилятор. Если язык программирования не имеет компилятора, скорее всего, используется интерпретатор.
Когда программист скомпилировал программу и ему нужно внести небольшое изменение, он часто использует интерпретатор для "тестирования" новой строки кода, а не для компиляции всей программы.
Отладка означает удаление любых ошибок в программе.
Существует несколько методов, которые программисты используют для отладки кода.
В большинстве случаев используется система проб и ошибок, когда программист пытается изолировать проблемную область, а затем проверяет строки кода, чтобы определить ошибку.
Результаты всего проекта документируются для пользователей и команды разработчиков.
Например, ваш автомобиль представляет собой систему компьютеров, деталей и механизмов, предназначенных для совместной работы, чтобы вы могли управлять автомобилем.
Информационная система включает в себя людей, методы, данные, информацию, программное и аппаратное обеспечение, которые работают вместе для выполнения общей задачи или цели.
При разработке программного обеспечения обычно используется жизненный цикл разработки системы (SDLC).
Определение проблемы включает анализ текущей ситуации и используемой информационной системы.
Распространенные вопросы включают: Какая информация необходима? Кому нужна информация? Когда им это нужно? Сколько это будет стоить? и Зачем им эта информация?
Следующий этап – предложение альтернатив.
Это означает изучение альтернативных решений существующей договоренности или проблемы.
Эта задача включает в себя предложение возможных планов, которые отличаются от текущей ситуации.
Алгоритмы — это спецификации последовательности действий, аналогичные рецептам приготовления пищи. Описание должно быть достаточно конкретным, чтобы приготовить вкусную еду. С другой стороны, необходима некоторая абстракция, чтобы презентация оставалась удобочитаемой; никто не учит повара резать лук кубиками. При представлении алгоритмов в информатике ситуация похожая. Презентация должна быть достаточно конкретной, чтобы ее можно было анализировать и повторно реализовать, но достаточно абстрактной, чтобы ее можно было перенести на другие языки программирования и машины. Процесс решения проблемы часто можно смоделировать как поиск в пространстве состояний, начиная с некоторого заданного начального состояния с правилами, описывающими, как преобразовать одно состояние в другое. Их нужно применять снова и снова, чтобы в конечном итоге удовлетворить некое целевое условие. Во многих областях компьютерных наук эвристика рассматривается как практическое правило. Однако в поиске искусственного интеллекта эвристика — это четко определенное отображение состояний в числа. Существуют различные типы эвристик поиска. Эта глава знакомит с системой обозначений, конкретными головоломками и формализмом общих задач. Он напоминает историю успеха эвристического поиска и изучает эвристики как эффективно вычисляемые нижние границы.
Иерархическое распознавание целей
Нейт Блейлок , Джеймс Аллен , План, деятельность и распознавание намерений , 2014 г.
1.3.1.3 Данные, помеченные планом
Конечно, наиболее полезный тип свода планов должен включать не только цель верхнего уровня, но также план и состояние мира.
Bauer [4] записывает последовательности действий пользователя (и соответствующее состояние системы) в программу электронной почты и использует распознаватель планов постфактум, чтобы пометить их соответствующей целью и планом. Это апостериорное распознавание потенциально может быть намного более точным, чем онлайн-прогнозирование, потому что оно позволяет просматривать всю последовательность выполнения. Потенциальная проблема, которую мы видим с этим подходом, заключается в том, что если первоначальный распознаватель планов постоянно делает ошибки в прогнозировании планов, эти ошибки будут распространяться в корпусе. Сюда входят случаи, когда библиотека планов не покрывает дополнительные или ошибочные действия пользователя.
Путь психолога
Роберт Чарльз Мецгер, «Отладка путем мышления», 2004 г.
12.5.4 Сбои памяти
Сильверман документирует ряд ошибок, возникающих при рассуждениях, основанных на навыках.
Забывание цели. Вы выполняете последовательность действий, но забываете, зачем это делаете.
Ошибка памяти порядка: вы временно забыли порядок, в котором должны выполняться действия в последовательности.
Ошибка интервала памяти: вы временно забываете физический или хронологический интервал между действиями в последовательности.
Ошибка координации памяти: вы временно забываете о движениях физических объектов, необходимых в последовательности действий.
Неправильное запоминание: вы забываете, насколько хорошо вы на самом деле умеете выполнять определенную последовательность действий.
Не помнить. Вы забыли фактические шаги последовательности, и вам нужно заново освоить навык.
Все эти ошибки, связанные с навыками, могут возникать, когда программист выполняет последовательность действий, являющихся частью изученного навыка.
Модели тактильных вычислений, вдохновленные человеком
Кристель Байер , . Стефан Дж. Кибель, Tactile Internet, 2021 г.
8.2.6 Изучение априорных последовательностей действий
Как человеческий мозг усваивает эти априорные вероятности по сравнению с ASQ? Что касается привычек, некоторые ответы дают такие модели, как Q-обучение [540, 559] и обучение с разницей во времени [540, 562]. Если действие приводило к вознаграждению несколько раз в прошлом, может быть создана сильная ассоциация стимул-реакция в форме априорных значений, которая будет использоваться в будущих испытаниях. В то время как в классических экспериментах по обучению эти ассоциации SR были между стимулом и атомарным действием, это не обязательно должно быть так. Вместо этого можно создать ассоциации между контекстом и любым действием (или последовательностью действий), которое в прошлом приводило к вознаграждению. Это означает, что ассоциации SR не обязательно связаны с атомарными действиями и не обязательно должны быть уникальными.
Формальное описание возможного механизма, посредством которого повторение приводит к выученным априорным данным, было представлено [563] . Авторы представили отчет о формировании и использовании привычки на механистическом уровне. В своей работе они демонстрируют модель принятия решений, основанную на байесовском выводе, в которой перспективное планирование рассматривается как вероятность модели, которая затем изучается с помощью повторения задачи, чтобы стать более приоритетной, чем действия, которые будут использоваться в будущих испытаниях. Другими словами, привычки хранятся в виде априорного распределения по действиям, что смещает решения человека в сторону определенного набора действий. Эти предварительные распределения создаются с повторением стратегии перспективного планирования. Обратите внимание, что в этом случае привычки не обязательно должны быть едиными ассоциациями стимул-реакция, а вместо этого могут состоять из подмножества доступных действий (или последовательностей действий), которые учитываются при принятии решения в данном контексте.
В учетной записи, представленной [563], может быть реализована система предварительного выбора ASQ для оценки. Например, только те ASQ, априорная вероятность которых превышает пороговое значение, могут подвергаться дальнейшей оценке. Определение используемого механизма сокращения пространства ASQ должно стать предметом дальнейших исследований.
Чтобы дополнить картину, в следующем разделе мы обсудим, как мозг может сделать вывод о текущем контексте и как он использует эту информацию для выбора наилучших априорных значений для текущей задачи, тем самым значительно упрощая принятие решений для наиболее повторяющихся действий. -опытные контексты.
Сокращение пространства состояний
Стефан Эделькамп , Стефан Шрёдль , эвристический поиск , 2012 г.
10.3 Резюме
В этой главе мы изучили сокращение, чтобы сделать поиск более эффективным. Сокращение означает игнорирование частей дерева поиска (и, таким образом, уменьшение коэффициента ветвления) для экономии времени выполнения и памяти. Это может быть сложно, так как мы хотели бы, чтобы поиск находил кратчайший путь из начального состояния в любое целевое состояние (допустимое сокращение) или, по крайней мере, какой-то путь из начального состояния в целевое состояние (сокращение, сохраняющее решение), если он существует. Кроме того, само сокращение требует времени выполнения и памяти, и поэтому нам необходимо убедиться, что эти затраты перевешиваются соответствующей экономией. Отсечение часто использует закономерности в пространстве состояний, знание которых может быть предоставлено экспертом или получено автоматически. Обучение может происходить либо перед поиском (статическая обрезка), часто в аналогичных, но меньших пространствах состояний, чем те, в которых выполняется поиск, либо во время поиска (динамическая обрезка). Если это делается во время поиска, это может быть сделано как часть поиска пути от начального состояния к целевому состоянию или как часть двухуровневой архитектуры, где поиск верхнего уровня находит путь от начального состояния к целевому состоянию. целевое состояние и поиск более низкого уровня получают дополнительные сведения об отсечении.
Мы обсудили следующие допустимые стратегии обрезки:
Сокращение подстроки удаляет последовательности действий (называемые дубликатами), которые приводят к тому же состоянию, что и по крайней мере одна более недорогая несокращенная последовательность действий (называемая ярлыком). Таким образом, эта стратегия сокращения является альтернативой отказу от повторной генерации уже сгенерированных состояний для алгоритмов поиска, которые не хранят в памяти все ранее сгенерированные состояния, такие как IDA*, и, таким образом, не могут легко обнаруживать повторяющиеся состояния.Мы обсудили два статических способа поиска повторяющихся последовательностей действий, а именно поиск в ширину, который находит последовательности действий, которые приводят к одному и тому же состоянию при выполнении в том же состоянии, и обнаружение последовательностей действий, которые приводят к тому же состоянию, в котором они выполняются. (циклы). Например, URDL — это цикл в пустом мире Gridworld, подразумевая, что UR — это повторяющаяся последовательность действий RU (обратная DL), а ULD — повторяющаяся последовательность действий R (обратная L). Мы также обсудили динамический способ поиска повторяющихся последовательностей действий, а именно во время поиска A*. Чтобы иметь возможность эффективно обнаруживать повторяющиеся последовательности действий, мы можем закодировать их как автоматы с конечным числом состояний, например, используя алгоритм Ахо-Корасика. Мы использовали Eight - Puzzle, чтобы проиллюстрировать сокращение подстроки.
Отсечение тупика удаляет состояния, из которых невозможно достичь целевого состояния. Состояние можно назвать тупиковым, если все его последующие состояния являются тупиковыми, или если показать, что одно его упрощение (называемое декомпозицией) является тупиковым. Мы обсудили статический способ поиска тупиковых ситуаций (называемый самозагрузкой), а именно использование таблиц штрафов. Таблицы штрафов — это способ изучения и хранения более обоснованных эвристик, а бесконечная эвристика указывает на тупик. Мы также обсудили динамический способ поиска повторяющихся последовательностей действий, а именно во время поиска A* (что приводит к декомпозиции абстракции A*). Мы использовали Sokoban для иллюстрации тупиковой обрезки.
Сокращение симметрии сокращает последовательности действий, которые похожи (симметрично) на последовательность действий без сокращения той же стоимости. Мы обсудили динамический способ уменьшения симметрии, который использует перестановки переменных состояния и некоторые предварительно скомпилированные знания о симметрии между переменными в целевом состоянии.
Мы обсудили следующие недопустимые стратегии обрезки:
Решение проблем с помощью макросов сокращает количество действий в пользу нескольких последовательностей действий (называемых макросами), что не только снижает коэффициент ветвления, но и глубину поиска. Мы обсудили статический способ изучения макросов для головоломки «Восьмерка», когда макросы ставят одну плитку за другой на место, не нарушая уже установленных плиток.
Сокращение релевантности удаляет действия в состоянии, которые считаются неважными, поскольку они не способствуют достижению преследуемой в настоящее время подцели. Действия, которые не влияют друг на друга, называются отдаленными действиями. Сокращение релевантности может, например, сократить действие, если за последнее время было выполнено более определенного количества удаленных действий (поскольку в этом случае действие не способствует достижению подцели, преследуемой недавно выполненными действиями) или если действие удалено до последнего. действие, но не определенное количество действий, которые были выполнены недавно (поскольку действие тогда не способствует подцели, преследуемой последним действием, которое уже переключило подцель, преследуемую действиями, выполненными ранее). Мы использовали Sokoban, чтобы проиллюстрировать сокращение релевантности.
Наконец, частичное уменьшение порядка удаляет последовательности действий, которые приводят к тому же состоянию, что и по крайней мере одна несокращенная последовательность действий. В отличие от сокращения подстроки, несокращенная последовательность действий может быть дороже, чем сокращенная последовательность действий. Действия без сокращений называются достаточными действиями. Мы обсудили способ определения обширных действий, используя свойства действий, такие как их независимость и невидимость, чтобы последовательности действий от начала до цели не искались только в том случае, если они заикаясь эквивалентны последовательности действий от начала до цели. цель, которую ищут. Мы обсудили способы постобработки найденной последовательности действий, чтобы сделать ее короче, несмотря на то, что нельзя гарантировать, что ни последовательность с уменьшенным порядком, ни постобработка будут кратчайшими.
В таблице 10.4 сравниваются подходы к сокращению пространства состояний. Стратегии классифицируются по критериям, являются ли они допустимыми (т. е. сохраняют оптимальные решения в оптимальных решателях) или инкрементальными (т. е. позволяют обнаруживать и обрабатывать информацию об отсечении во время Поиск). Правила сокращения являются жесткими критериями и могут рассматриваться как присвоение поиску эвристической оценки ∞. Некоторые правила распространяются на уточнения допустимой эвристики поиска, нижней границы. Классификация не фиксирована; обратитесь к презентации в тексте. В зависимости от ослабления (усиления) допущений для сценария обрезки допустимые приемы обрезки могут стать недопустимыми (и наоборот). Мы также обеспечиваем некоторую экономию времени для хранения и применения обрезки, которая, конечно же, зависит от реализации соответствующей структуры данных и игнорирует некоторые тонкости, указанные в тексте. Для сокращения подстрок мы предполагаем автомат Ахо-Корасика (IDA*) или суффиксные деревья (IDLA*). Для тупиковой обрезки и поиска шаблонов необходима структура хранения, основанная на частичных состояниях.Симметрии могут быть предоставлены экспертами в предметной области или выведены системой (планирование действий). Для краткости при планировании действий и сокобане мы предполагали унарное логическое кодирование набора атомов (квадратов) для формирования вектора состояния.
Таблица 10.4. Обзор сокращения пространства состояний; l(n) — длина дубликата (пути решения), S — вектор состояния размером k, P – набор паттернов, M – набор симметрий (*амортизированная сложность).
поиск меню
Урок 5. Последовательности, выделения и циклы
Последовательности, выборки и циклы
За всем программным обеспечением, которое мы используем ежедневно, стоит код, работающий со всевозможными терминами и символами. Удивительно, но его часто можно разбить на три простые программные структуры, называемые последовательностями, выборками и циклами. Все вместе они образуют самые основные инструкции и алгоритмы для всех типов программного обеспечения.
Посмотрите видео ниже, чтобы узнать больше о последовательностях, выделении и циклах.
Последовательность – это последовательность действий, выполняемых в определенном порядке. Выполняется действие 1, затем действие 2, затем действие 3 и т. д., пока не будут выполнены все действия в последовательности.
Последовательность, которую мы выполняем каждый день, — это утренняя рутина. Вы можете проснуться, выпить немного воды, принять душ, позавтракать и так далее. Распорядок дня у всех разный, но все они состоят из последовательности различных действий.
Выбор немного отличается. Вместо того, чтобы следовать определенному порядку событий, они задают вопрос, чтобы выяснить, какой путь выбрать дальше.
Допустим, вы идете чистить зубы и обнаруживаете, что у вас закончилась зубная паста. Затем вы спросите: «Есть ли у меня еще зубная паста?» Если ответ отрицательный, то вы должны добавить его в свой список покупок. Но если ответ да, вы бы просто использовать зубную пасту. На самом деле это все, что делает выбор: отвечает на вопрос на основе того, что он находит.
Третья структура программирования — это цикл. Подобно выборкам, циклы задают вопросы. Однако разница в том, что они задают один и тот же вопрос снова и снова, пока определенная задача не будет выполнена.
Например, возьмем процесс забивания гвоздя. Даже если вы этого не осознаете, вы постоянно спрашиваете себя: «Гвоздь полностью вошел?» Когда ответ отрицательный, вы снова забиваете гвоздь. Вы продолжаете повторять этот вопрос до тех пор, пока не ответите «да», а затем останавливаетесь. Циклы позволяют программистам эффективно кодировать повторяющиеся задачи вместо повторного написания одних и тех же действий.
Эти три программные структуры могут показаться довольно простыми сами по себе, но в сочетании они могут создавать довольно сложное программное обеспечение.
Изучите базовый процесс разработки решения проблемы. Ничто в этой главе не является уникальным для использования компьютера для решения проблемы. Этот процесс можно использовать для решения самых разных проблем, в том числе и не связанных с компьютерами.
Проблемы, решения и инструменты
У меня проблема! Мне нужно поблагодарить тетю Кей за подарок на день рождения, который она прислала мне. Я мог бы отправить благодарственное письмо по почте. Я мог бы позвонить ей по телефону. Я мог бы отправить ей сообщение по электронной почте. Я мог бы подъехать к ней домой и поблагодарить ее лично. На самом деле, я мог бы отблагодарить ее многими способами, но суть не в этом. Дело в том, что я должен решить, как я хочу решить проблему, и использовать соответствующий инструмент для реализации (выполнения) моего плана. Почта, телефон, Интернет и мой автомобиль — это инструменты, которые я могу использовать, но ни один из них на самом деле не решает мою проблему.Точно так же компьютер не решает проблемы, это всего лишь инструмент, который я могу использовать для реализации своего плана решения проблемы.
Зная, что тетя Кей ценит творческие и необычные вещи, я решил нанять поющего посыльного, чтобы передать мою благодарность. В этом контексте мессенджер — это инструмент, но он нуждается в моих инструкциях. Я должен сказать курьеру, где живет тетя Кей, в какое время я хочу, чтобы сообщение было доставлено, и какие слова я хочу спеть. Компьютерная программа аналогична моей инструкции к мессенджеру.
История тети Кей использует знакомый контекст, чтобы подготовить почву для полезной точки зрения на компьютеры и компьютерные программы. В следующем списке приведены основные аспекты этой точки зрения.
Компьютер — это инструмент, который можно использовать для реализации плана решения проблемы.
Компьютерная программа — это набор инструкций для компьютера. Эти инструкции описывают шаги, которые должен выполнить компьютер для реализации плана.
Алгоритм – это план решения проблемы.
Человек должен разработать алгоритм.
Человек должен перевести алгоритм в компьютерную программу.
Эта точка зрения закладывает основу для процесса, который мы будем использовать для разработки решений проблем Jeroo. Базовый процесс важен, потому что его можно использовать для решения самых разных задач, в том числе тех, решение которых будет написано на каком-то другом языке программирования.
Процесс разработки алгоритма
Каждое решение проблемы начинается с плана. Этот план называется алгоритмом.
Есть много способов написать алгоритм. Некоторые из них очень неформальные, некоторые довольно формальные и математические по своей природе, а некоторые довольно графические. Инструкция по подключению DVD-проигрывателя к телевизору представляет собой алгоритм. Математическая формула, такая как πR 2, является частным случаем алгоритма. Форма не имеет особого значения, если она обеспечивает хороший способ описания и проверки логики плана.
Разработка алгоритма (плана) — ключевой этап решения проблемы. Когда у нас есть алгоритм, мы можем перевести его в компьютерную программу на каком-нибудь языке программирования. Процесс разработки нашего алгоритма состоит из пяти основных этапов.
Шаг 1. Получите описание проблемы.
Шаг 2. Проанализируйте проблему.
Шаг 3. Разработайте высокоуровневый алгоритм.
Шаг 4. Усовершенствуйте алгоритм, добавив больше деталей.
Шаг 5. Просмотрите алгоритм.
Шаг 1. Получите описание проблемы.
Этот шаг намного сложнее, чем кажется. В следующем обсуждении слово клиент относится к тому, кто хочет найти решение проблемы, а слово разработчик относится к тому, кто находит способ решить проблему. . Разработчик должен создать алгоритм, который решит проблему клиента.
Клиент отвечает за создание описания проблемы, но зачастую это самая слабая часть процесса. Довольно часто описание проблемы страдает от одного или нескольких из следующих типов дефектов: (1) описание основано на невысказанных предположениях, (2) описание неоднозначно, (3) описание неполно или (4) описание имеет внутренние противоречия. Эти дефекты редко возникают из-за невнимательности со стороны клиента. Вместо этого они связаны с тем, что естественные языки (английский, французский, корейский и т. д.) довольно неточны. Частью ответственности разработчика является выявление дефектов в описании проблемы и работа с клиентом над устранением этих дефектов.
Шаг 2. Проанализируйте проблему.
Целью этого шага является определение начальной и конечной точек решения проблемы. Этот процесс аналогичен математику, определяющему, что дано и что должно быть доказано. Хорошее описание проблемы облегчает выполнение этого шага.
Определяя отправную точку, мы должны начать с поиска ответов на следующие вопросы:
Какие данные доступны?
Где эти данные?
Какие формулы относятся к задаче?
Какие существуют правила работы с данными?
Какие отношения существуют между значениями данных?
При определении конечной точки нам необходимо описать характеристики решения. Другими словами, как мы узнаем, когда закончим? Задавание следующих вопросов часто помогает определить конечную точку.
Какие новые факты мы получим?
Какие элементы будут изменены?
Какие изменения будут внесены в эти элементы?
Каких вещей больше не будет?
Шаг 3. Разработайте высокоуровневый алгоритм.
Алгоритм – это план решения проблемы, но планы имеют несколько уровней детализации. Обычно лучше начинать с высокоуровневого алгоритма, который включает основную часть решения, но оставляет детали на потом.Мы можем использовать повседневный пример для демонстрации алгоритма высокого уровня.
Проблема: мне нужно отправить поздравительную открытку моему брату Марку.
Анализ: у меня нет карты. Я предпочитаю купить открытку, а не делать ее самостоятельно.
Этот алгоритм подходит для повседневного использования, но в нем отсутствуют детали, которые пришлось бы добавлять, если бы решение выполнял компьютер. Эти сведения включают ответы на следующие вопросы.
"Какой магазин я посещу?"
"Какие карты нравятся Марку: юмористические, сентиментальные, рискованные?"
Такие детали рассматриваются на следующем этапе нашего процесса.
Шаг 4. Усовершенствуйте алгоритм, добавив больше деталей.
Алгоритм высокого уровня показывает основные шаги, которые необходимо выполнить для решения проблемы. Теперь нам нужно добавить детали к этим шагам, но сколько деталей мы должны добавить? К сожалению, ответ на этот вопрос зависит от ситуации. Мы должны учитывать, кто (или что) будет реализовывать алгоритм и насколько этот человек (или вещь) уже умеет это делать. Если кто-то собирается купить поздравительную открытку Марка от моего имени, мои инструкции должны быть адаптированы к тому, знаком ли этот человек с местными магазинами и насколько хорошо покупатель знает вкус моего брата в поздравительных открытках.
Когда нашей целью является разработка алгоритмов, которые приведут к компьютерным программам, нам необходимо учитывать возможности компьютера и предоставлять достаточно подробностей, чтобы кто-то другой мог использовать наш алгоритм для написания компьютерной программы, которая следует шагам нашего алгоритма. . Как и в случае с поздравительной открыткой, нам нужно настроить уровень детализации в соответствии со способностями программиста. Если вы сомневаетесь или учитесь, лучше иметь слишком много деталей, чем слишком мало.
Большинство наших примеров переходят от высокоуровневого к подробному алгоритму за один шаг, но это не всегда разумно. Для более крупных и сложных задач этот процесс обычно повторяется несколько раз, при этом разрабатываются алгоритмы промежуточного уровня. Каждый раз мы добавляем больше деталей к предыдущему алгоритму, останавливаясь, когда не видим пользы от дальнейшего уточнения. Этот метод постепенного перехода от алгоритма высокого уровня к детализированному алгоритму часто называют пошаговым уточнением .
Поэтапное уточнение – это процесс разработки подробного алгоритма путем постепенного добавления деталей к алгоритму высокого уровня.
Шаг 5. Просмотрите алгоритм.
Последний шаг – просмотр алгоритма. Что мы ищем? Во-первых, нам нужно шаг за шагом проработать алгоритм, чтобы определить, решит ли он исходную проблему. Как только мы убедимся, что алгоритм действительно обеспечивает решение проблемы, мы начинаем искать другие вещи. Следующие вопросы являются типичными из тех, которые следует задавать всякий раз, когда мы рассматриваем алгоритм. Задавать эти вопросы и искать на них ответы — хороший способ развить навыки, которые можно применить к следующей проблеме.
Решает ли этот алгоритм очень конкретную проблему или более общую проблему? Если он решает очень конкретную проблему, следует ли его обобщать?
Например, алгоритм, вычисляющий площадь круга радиусом 5,2 метра (формула π*5,2 2 ), решает очень конкретную задачу, а алгоритм, вычисляющий площадь любого круга (формула π*R 2 ), решает более общая проблема.
Можно ли упростить этот алгоритм?
Одна из формул для вычисления периметра прямоугольника:
Более простой формулой будет:
Похоже ли это решение на решение другой проблемы? Чем они похожи? Чем они отличаются?
Например, рассмотрим следующие две формулы:
Сходство: каждый вычисляет площадь. Каждый умножает два измерения.
Различия: используются разные измерения. Формула треугольника содержит 0,5.
Гипотеза. Возможно, каждая формула площади предполагает умножение двух измерений.
Пример 4.1. Собрать и посадить
Этот раздел содержит расширенный пример, демонстрирующий процесс разработки алгоритма. Чтобы завершить алгоритм, нам нужно знать, что каждый Джеру может прыгать вперед, поворачиваться влево и вправо, срывать цветок с его текущего местоположения и сажать цветок в его текущем местоположении.
Постановка задачи (шаг 1)
Иеру начинается с точки (0, 0) лицом на восток, и в его сумке нет цветов. В локации (3, 0) есть цветок. Напишите программу, которая предписывает Джеру сорвать цветок и посадить его в точке (3, 2). После посадки цветка Джеру должен прыгнуть на одну клетку на восток и остановиться. На острове нет других сетей, цветов или джеруа.
| Начало | Завершение |
|---|---|
 |  |
Анализ проблемы (шаг 2)
Цветок ровно на три клетки впереди джеру.
Цветок нужно посадить ровно на две клетки южнее его текущего местоположения.
Иеру должен стоять лицом на восток на одну клетку к востоку от посаженного цветка.
Нет сетей, о которых нужно беспокоиться.
Алгоритм высокого уровня (шаг 3)
Давайте назовем Джеру Бобби. Бобби должен сделать следующее:
Подробный алгоритм (шаг 4)
Давайте назовем Джеру Бобби. Бобби должен сделать следующее:
Просмотрите алгоритм (шаг 5)
Алгоритм высокого уровня разделил проблему на три довольно простых подзадачи. Это кажется хорошей техникой.
Этот алгоритм решает очень специфическую проблему, поскольку Джеру и цветок находятся в очень определенных местах.
На самом деле этот алгоритм является решением немного более общей проблемы, в которой Джеру начинается где угодно, а цветок находится на 3 клетки прямо перед Джеру.
Код Java для "Выбери и посади"
Хороший программист не пишет программу сразу. Вместо этого программист будет писать и тестировать программу в серии сборок. Каждая сборка дополняет предыдущую. Алгоритм высокого уровня поможет нам в этом процессе.
Хороший программист работает постепенно, добавляя маленькие кусочки по одному и постоянно перепроверяя работу до сих пор.
ПЕРВАЯ СТРОКА
Чтобы увидеть это решение в действии, создайте новый сценарий Greenfoot4Sofia и используйте команду меню Edit Palettes Jeroo, чтобы сделать классы Jeroo видимыми. Щелкните правой кнопкой мыши класс Island и создайте новый подкласс с именем по вашему выбору. Этот подкласс будет содержать ваш новый код.
Рекомендуемая первая сборка содержит три вещи:
Основной метод (здесь myProgram() в подклассе вашего острова).
Объявление и создание экземпляра каждого Jeroo, который будет использоваться.
Алгоритм высокого уровня в виде комментариев.
Экземпляр в начале myProgram() помещает Бобби в (0, 0), лицом на восток, без цветов.
После того, как первая сборка заработает правильно, мы можем перейти к остальным. В этом случае каждая сборка будет соответствовать одному шагу высокоуровневого алгоритма. Использование четырех сборок для такой простой программы может показаться слишком трудоемким, но это помогает выработать привычки, которые станут бесценными по мере усложнения программ.
ВТОРАЯ СТРОКА
Эта сборка добавляет логику для получения цветка, которая в подробном алгоритме (шаг 4 выше) состоит из прыжков 3 раз, а затем сбора цветка. Новый код обозначен комментариями, которых не было в оригинале (они здесь только для того, чтобы привлечь внимание к дополнениям). Пустые строки помогают показать организацию логики.
Выполнив работу на данный момент, вы можете проверить, работает ли этот шаг в запланированном алгоритме должным образом.
ТРЕТЬЯ СТРОКА
В этой сборке добавлена логика "положить цветок". Новый код обозначается комментариями, представленными здесь для обозначения дополнений.
ЧЕТВЕРТАЯ СТРОКА (последняя)
Эта сборка добавляет логику "прыжка на восток".
Пример 4.2. Замена сети на цветок
Этот раздел содержит второй пример, демонстрирующий процесс разработки алгоритма.
Постановка задачи (шаг 1)
Есть два Джеру. Один Джеру начинается в (0, 0) лицом на север с одним цветком в мешочке. Второй начинается в (0, 2) лицом на восток с одним цветком в мешочке. В локации (3, 2) есть сеть. Напишите программу, которая предписывает первому Джеру отдать свой цветок второму. Получив цветок, второй Джеру должен отключить сеть и посадить на ее место цветок. Посадив цветок, Джеру должен повернуться лицом на юг. На острове нет других сетей, цветов или джеруа.
| Начало | Завершение |
|---|---|
 |  |