Математические основания информатики

Математика

Основные сведения

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

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

--------------------------------------------------------------------

Информатика

Материал из Википедии — свободной энциклопедии

Текущая версия (сравнить)   (+/-)

Данная версия страницы не проверялась участниками с соответствующими правами. Вы можете прочитать последнюю стабильную версию, проверенную 22 марта 2010, однако она может значительно отличаться от текущей версии. Проверки требуют 30 правок.

Перейти к: навигация, поиск

Информа?тика (ср. нем. Informatik, фр. Informatique, англ. computer science — компьютерная наука — в США, англ. computing science — вычислительная наука — в Великобритании) — наука о способах получения, накоплении, хранении, преобразовании, передаче и использовании научной информации. Она включает дисциплины, так или иначе относящиеся к обработке информации в вычислительных машинах и вычислительных сетях: как абстрактные, вроде анализа алгоритмов, так и довольно конкретные, например, разработка языков программирования.

Термин информатика возник в 60-х годах во Франции для названия области, занимающейся автоматизированной переработкой информации, как слияние французских слов information и automatique (F. Dreyfus, 1972).

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

Содержание

1 Введение

2 Определения

3 История информатики

4 См. также

5 Примечания

6 Ссылки

7 Литература

Введение

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

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

Определения

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

История информатики

Основная статья: История информатики

Термин «информатика» был впервые введён в Германии Карлом Штейнбухом в 1957 году. В 1962 году этот термин был введён во французский язык Ф. Дрейфусом, который также предложил и переводы на ряд других европейских языков. В советской научно-технической литературе термин «информатика» был введён А. И. Михайловым, А. И. Черным и Р. С. Гиляревским в 1968 году.

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

Первый факультет информатики был основан в 1962 году в университете Пёрдью (Purdue University). Сегодня факультеты и кафедры информатики имеются в большинстве университетов мира.

В школах СССР учебная дисциплина «Информатика» появилась в 1985 году одновременно с первым учебником А. П. Ершова «Основы информатики и вычислительной техники».

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

4 декабря отмечается День российской информатики, так как в этот день в 1948 году Государственный комитет Совета министров СССР по внедрению передовой техники в народное хозяйство зарегистрировал за номером 10 475 изобретение И. С. Брука и Б. И. Рамеева — цифровую электронную вычислительную машину.

-------------------------------------------------------------------

Вычислительная математика

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

Имеется викиучебник по теме

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

К задачам вычислительной математики относят:

решение систем линейных уравнений

нахождение собственных значений и векторов матрицы

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

решение нелинейных алгебраических уравнений

решение систем нелинейных алгебраических уравнений

решение дифференциальных уравнений (как обыкновенных дифференциальных уравнений, так и уравнений с частными производными)

решение систем дифференциальных уравнений

решение интегральных уравнений

задачи аппроксимации

задачи интерполяции

задачи экстраполяции

задачи численной оптимизации

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

-------------------------------------------------------------------------

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

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

------------------------------------------------------------------------------

Математическая логика

Материал из Википедии — свободной энциклопедии

Текущая версия (сравнить)   (+/-)

Данная версия страницы не проверялась участниками с соответствующими правами. Вы можете прочитать последнюю стабильную версию, проверенную 15 декабря 2009, однако она может значительно отличаться от текущей версии. Проверки требуют 18 правок.

Перейти к: навигация, поиск

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

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

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

Отношение исчислений к семантике выражается понятиями семантической пригодности и семантической полноты исчисления. Исчисление И называется семантически пригодным для языка Я, если любая выводимая в И формула языка Я является верной. Аналогично, исчисление И называется семантически полным в языке Я, если любая верная формула языка Я выводима в И.

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

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

-------------------------------------------------------------------------

Тео?рия вероя?тностей — раздел математики, изучающий закономерности случайных явлений: случайные события, случайные величины, их свойства и операции над ними.

История

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

Важный вклад в теорию вероятностей внёс Якоб Бернулли: он дал доказательство закона больших чисел в простейшем случае независимых испытаний. В первой половине XIX века теория вероятностей начинает применяться к анализу ошибок наблюдений; Лаплас и Пуассон доказали первые предельные теоремы. Во второй половине XIX века основной вклад внесли русские учёные П. Л. Чебышёв, А. А. Марков и А. М. Ляпунов. В это время были доказаны закон больших чисел, центральная предельная теорема, а также разработана теория цепей Маркова. Современный вид теория вероятностей получила благодаря аксиоматизации, предложенной Андреем Николаевичем Колмогоровым. В результате теория вероятностей приобрела строгий математический вид и окончательно стала восприниматься как один из разделов математики.