Принципы обработки компьютерной информации арифметические и логические основы работы компьютера

Обновлено: 30.06.2024

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

Главное новшество курса в том, что он на сто процентов формализован и проверен машинами: весь текст буквально является скриптом для Coq. Он предназначен для чтения во время интерактивного сеанса с Coq. Все детали в тексте полностью формализованы в Coq, а упражнения рассчитаны на работу с Coq.

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

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

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

Настоящий курс посвящен последнему набору методов. Текст сплетает воедино пять концептуальных нитей:

(3) идея функционального программирования как метода программирования, упрощающего рассуждения о программах, и как связующего звена между программированием и логикой;

(4) формальные методы для рассуждений о свойствах конкретных программ (например, тот факт, что функция сортировки или компилятор подчиняются некоторой формальной спецификации); и

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

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

Логика

Логика — это область исследования, предметом которой являются доказательства — неопровержимые аргументы в пользу истинности конкретных утверждений. Тома были написаны о центральной роли логики в информатике. Манна и Уолдингер назвали это «исчислением компьютерных наук», а в статье Халперна и др. О необычной эффективности логики в компьютерных науках перечислены десятки способов, которыми логика предлагает важные инструменты и идеи. Действительно, они отмечают, что «на самом деле логика оказалась значительно более эффективной в компьютерных науках, чем в математике. сто лет пришли из математики."

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

Помощники по проверке

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

Автоматические доказыватели теорем работают по нажатию кнопки: вы даете им предложение, и они возвращают либо истину, ложь, либо < у меня закончилось время. Хотя их возможности ограничены довольно специфическими рассуждениями, за последние годы они значительно расширились и теперь используются в огромном разнообразии условий. Примеры таких инструментов включают решатели SAT, решатели SMT и средства проверки моделей.

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

Являясь платформой для моделирования языков программирования, он стал стандартным инструментом для исследователей, которым необходимо описывать и анализировать сложные языковые определения. Он использовался, например, для проверки безопасности платформы JavaCard, получения наивысшего уровня сертификации по общим критериям, а также для формальных спецификаций наборов инструкций x₈₆ и LLVM и языков программирования, таких как С.

Кстати, если вас интересует название, вот что говорится на официальном веб-сайте Coq: "Некоторые французские ученые-компьютерщики имеют традицию называть свое программное обеспечение видами животных: Caml, Elan, Foc или Phox примеры этого молчаливого соглашения. По-французски «coq» означает «петух», и это звучит как инициалы исчисления конструкций (CoC), на котором оно основано». Петух также является национальным символом Франции, а C-o-q – это первые три буквы имени Тьерри Коканда, одного из первых разработчиков Coq.

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

Функциональное программирование разрабатывалось в течение многих десятилетий — действительно, его корни восходят к лямбда-исчислению Черча, которое было изобретено в 1930-х годах, когда еще не было компьютеров! Но с начала 1990-х годов он вызывает всплеск интереса со стороны инженеров-технологов и языковых дизайнеров, играя ключевую роль в дорогостоящих системах таких компаний, как Jane St. Capital, Microsoft, Facebook и Ericsson.

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

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

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

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

Проверка программы

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

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

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

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

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

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

Системы шрифтов

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

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

Эта тема замыкает круг: язык, свойства которого мы изучаем в этой части, просто типизированное лямбда-исчисление, по существу является упрощенной моделью ядра самого Coq!

Дополнительная литература

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

Зависимости глав

Схему взаимосвязей между главами и некоторые предлагаемые пути прохождения материала можно найти в файле deps.html .

Системные требования

Текущая версия Coq, доступная на домашней странице Coq. Все должно работать с версией 8.4 (или 8.5).

Proof General — это интегрированная среда разработки на основе Emacs. Его предпочитают пользователи, которые уже знакомы с Emacs. Требуется отдельная установка (погуглите "Proof General").

Упражнения

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

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

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

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

Скачивание файлов Coq

Если вы собираетесь использовать эти материалы в своем собственном курсе, вы, несомненно, найдете то, что хотели бы изменить, улучшить или добавить. Ваш вклад приветствуется!

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

Настоящим я передаю авторские права на мои прошлые и будущие вклады в проект Software Foundations Автору записи каждого тома или компонента для лицензирования на тех же условиях, что и остальные Software Foundations. Я понимаю, что в настоящее время Авторами Записи являются: Для Томов 1 и 2, известных до 2016 года как «Основы программного обеспечения», а с 2016 года как (соответственно) «Логические основы» и «Основы программирования», автор записи это Бенджамин Пирс. Для Тома 3, "Проверенные функциональные алгоритмы", автором записи является Эндрю В. Аппель. Для компонентов, не входящих в указанные тома (например, инструменты для набора текста и оценки и другая программная инфраструктура), автором записи является Бенджамин Пирс.

Для начала отправьте электронное письмо Бенджамину Пирсу, описав себя и то, как вы планируете использовать материалы, включая (1) приведенный выше текст о передаче авторских прав и (2) результат выполнения "htpasswd -s -n ИМЯ". ", где ИМЯ – предпочитаемое вами имя пользователя.

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

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

Наши редакторы рассмотрят то, что вы отправили, и решат, нужно ли пересматривать статью.

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

Далее следует краткое описание цифровых компьютеров. Полное описание см. в см. информатике: основные компьютерные компоненты.

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

Функциональные элементы

Типичная цифровая компьютерная система имеет четыре основных функциональных элемента: (1) оборудование ввода-вывода, (2) основную память, (3) блок управления и (4) арифметико-логическое устройство. Любое из ряда устройств используется для ввода данных и программных инструкций в компьютер и для получения доступа к результатам операции обработки. Общие устройства ввода включают клавиатуры и оптические сканеры; устройства вывода включают принтеры и мониторы. Информация, полученная компьютером от своего блока ввода, сохраняется в основной памяти или, если не для непосредственного использования, во вспомогательном запоминающем устройстве.Блок управления выбирает и вызывает инструкции из памяти в соответствующей последовательности и передает соответствующие команды соответствующему блоку. Он также синхронизирует различные рабочие скорости устройств ввода и вывода со скоростью арифметико-логического устройства (ALU), чтобы обеспечить правильное перемещение данных по всей компьютерной системе. ALU выполняет арифметические и логические алгоритмы, выбранные для обработки входящих данных, с чрезвычайно высокой скоростью — во многих случаях за наносекунды (миллиардные доли секунды). Основная память, блок управления и АЛУ вместе составляют центральный процессор (ЦП) большинства цифровых компьютерных систем, а устройства ввода-вывода и вспомогательные запоминающие устройства составляют периферийное оборудование.

Разработка цифрового компьютера

Блез Паскаль из Франции и Готфрид Вильгельм Лейбниц из Германии изобрели механические цифровые вычислительные машины в 17 веке. Однако обычно считается, что английский изобретатель Чарльз Бэббидж создал первый автоматический цифровой компьютер. В 1830-х годах Бэббидж разработал свою так называемую аналитическую машину, механическое устройство, предназначенное для объединения основных арифметических операций с решениями, основанными на собственных вычислениях. Планы Бэббиджа воплотили в себе большинство фундаментальных элементов современного цифрового компьютера. Например, они призывали к последовательному управлению, т. е. программному управлению, которое включало ветвление, циклирование, а также арифметические и запоминающие устройства с автоматической распечаткой. Однако устройство Бэббиджа так и не было завершено и было забыто до тех пор, пока его труды не были заново открыты более века спустя.

Огромное значение в эволюции цифрового компьютера имели работы английского математика и логика Джорджа Буля. В различных эссе, написанных в середине 1800-х годов, Буль обсуждал аналогию между символами алгебры и символами логики, используемыми для представления логических форм и силлогизмов. Его формализм, работающий только с 0 и 1, стал основой того, что сейчас называется булевой алгеброй, на которой основаны теория и процедуры компьютерного переключения.

Джону В. Атанасову, американскому математику и физику, приписывают создание первого электронного цифрового компьютера, который он построил с 1939 по 1942 год с помощью своего аспиранта Клиффорда Э. Берри. Конрад Цузе, немецкий инженер, фактически изолированный от других разработок, в 1941 году завершил строительство первой действующей вычислительной машины с программным управлением (Z3). В 1944 году Ховард Эйкен и группа инженеров корпорации International Business Machines (IBM) завершили работу над Harvard Mark I – машиной, операции обработки данных которой контролировались главным образом электрическими реле (коммутационными устройствами).

Клиффорд Э. Берри и компьютер Атанасова-Берри, или ABC, c. 1942 г. ABC, возможно, был первым электронным цифровым компьютером.

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

В 1946 году Дж. Преспер Эккерт и Джон У. Мочли из Пенсильванского университета сконструировали ENIAC (аббревиатура от eэлектронный nмерический i интегратор ии cкомпьютер), цифровая машина и первый электронный компьютер общего назначения. Его вычислительные возможности были заимствованы у машины Атанасова; оба компьютера включали электронные лампы вместо реле в качестве активных логических элементов, что привело к значительному увеличению скорости работы. Концепция компьютера с хранимой программой была представлена в середине 1940-х годов, а идея хранения кодов инструкций, а также данных в электрически изменяемой памяти была реализована в EDVAC (electronic, d создать vпеременный аавтоматический cкомпьютер).

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

Транзистор был изобретен в 1947 году в Bell Laboratories Джоном Бардином, Уолтером Х. Браттейном и Уильямом Б. Шокли.

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

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

К началу 1980-х интегральные схемы продвинулись до очень крупномасштабной интеграции (СБИС). Этот дизайн и технология производства значительно увеличили плотность схем микропроцессора, памяти и вспомогательных микросхем, т. Е. Те, которые служат для сопряжения микропроцессоров с устройствами ввода-вывода. К 1990-м годам некоторые схемы СБИС содержали более 3 миллионов транзисторов на кремниевой микросхеме площадью менее 0,3 квадратных дюйма (2 квадратных см).

Цифровые компьютеры 1980-х и 90-х годов, использующие технологии БИС и СБИС, часто называют системами четвертого поколения. Многие микрокомпьютеры, произведенные в 1980-х годах, были оснащены одним чипом, на котором были интегрированы схемы процессора, памяти и функций интерфейса. (См. также суперкомпьютер.)

Использование персональных компьютеров выросло в 1980-х и 90-х годах. Распространение Всемирной паутины в 1990-х годах привело миллионы пользователей к Интернету, всемирной компьютерной сети, и к 2019 году около 4,5 миллиардов человек, более половины населения мира, имели доступ к Интернету. Компьютеры становились меньше и быстрее, и в начале 21 века они были широко распространены в смартфонах, а затем и в планшетных компьютерах.

Редакторы Британской энциклопедии Эта статья была недавно отредактирована и обновлена Эриком Грегерсеном.

Главное новшество курса в том, что он на сто процентов формализован и проверен машинами: весь текст буквально является скриптом для Coq.Он предназначен для чтения во время интерактивного сеанса с Coq. Все детали в тексте полностью формализованы в Coq, а упражнения рассчитаны на работу с Coq.

Настоящий курс посвящен последнему набору методов. Текст сплетает воедино пять концептуальных нитей:

Логика

Помощники по проверке

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

Автоматические доказыватели теорем работают по нажатию кнопки: вы даете им предложение, и они возвращают либо истину, ложь, либо < у меня закончилось время. Хотя их возможности ограничены довольно специфическими рассуждениями, за последние годы они значительно расширились и теперь используются в огромном разнообразии условий. Примеры таких инструментов включают решатели SAT, решатели SMT и средства проверки моделей.

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

Являясь платформой для моделирования языков программирования, он стал стандартным инструментом для исследователей, которым необходимо описывать и анализировать сложные языковые определения. Он использовался, например, для проверки безопасности платформы JavaCard, получения наивысшего уровня сертификации по общим критериям, а также для формальных спецификаций наборов инструкций x₈₆ и LLVM и языков программирования, таких как С.

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

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

Проверка программы

Системы шрифтов

Дополнительная литература

Зависимости глав

Системные требования

Текущая версия Coq, доступная на домашней странице Coq. Все должно работать с версией 8.4 (или 8.5).

Proof General — это интегрированная среда разработки на основе Emacs. Его предпочитают пользователи, которые уже знакомы с Emacs. Требуется отдельная установка (погуглите "Proof General").

Упражнения

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

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

Скачивание файлов Coq

Информатика — это дисциплина, изучающая архитектуру компьютера, проектирование программного обеспечения, алгоритмы, обработку информации, компьютерные приложения и системы, а также математические основы вычислений. Четырехлетняя степень бакалавра наук в области компьютерных наук - это ориентированная на студентов отраслевая программа B.S. степень, которая ведет к трудоустройству или аспирантуре в области компьютерных наук. Содержание и учебная программа по информатике основаны на работе Ассоциации вычислительной техники (ACM) и Компьютерного общества Института инженеров по электротехнике и электронике (IEEE), двух основных профессиональных организаций в области компьютерных наук. Рекомендации по учебным программам ACM/IEEE CS2013, наиболее известный национальный стандарт учебных программ на получение степени в области компьютерных наук, использовались для обеспечения достаточного охвата важных тем. Учебная программа предназначена для того, чтобы учащиеся получили обширную основу в области компьютерных наук, естественных наук, математики и коммуникативных навыков. Учащиеся также смогут расширить свои возможности с помощью расширенных факультативных предложений.

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

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

Типичные возможности трудоустройства

Разработчики программного обеспечения
Инженеры-программисты
Инженеры по контролю качества
Аналитики данных
Веб-разработчики
Специалисты по техническим вопросам
Помощники по исследованиям

Результаты программы по информатике (BS):

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

Зачисление в Государственный колледж Фармингдейл – Государственный университет Нью-Йорка осуществляется на основе квалификации поступающего независимо от возраста, пола, семейного или военного положения, расы, цвета кожи, вероисповедания, религии, национального происхождения, инвалидности или сексуальной ориентации.

Читайте также: