Математические основы информатики - Реферат

Informatique, в противоположность традиционному англоязычному термину англ. computer science - наука о компьютерах - в США или англ. computing science - вычислительная наука-в Британии есть наука о вычислениях, хранении и обработке информации. Она включает дисциплины, так или иначе относящиеся к вычислительным машинам: как абстрактные, вроде анализа алгоритмов, так и довольно конкретные, например, разработка языков программирования. Тезис иногда преподносят как фундаментальный принцип информатики, обращая особое внимание на машину Тьюринга и машину фон-неймановской архитектуры, поскольку они имеют явное сходство с большинством из ныне действующих компьютеров. Темами исследований в информатике являются вопросы: что можно, а что нельзя реализовать в программах (теория вычислимости и искусственный интеллект), каким образом можно решать специфические задачи с максимальной эффективностью (алгоритмы), в каком виде следует хранить и восстанавливать информацию специфического вида (структуры данных), как программы и люди должны взаимодействовать друг с другом (пользовательский интерфейс и языки программирования) и т. п.Теория графов - раздел дискретной математики, изучающий свойства графов. В наиобщем смысле граф представляется как множество вершин (узлов), соединенных ребрами. В строгом определении графом называется такая пара множеств Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут (см.* Проблема четырех красок - была сформулирована в 1852 году, но доказательство получено лишь в 1976 году (достаточно 4-х красок для карты на сфере (плоскости)). Обозначим через R= r(i,j) - (m 1)(m 1) матрицу расстояний, элемент которой r(i,j) - расстояние между городом с номером i и городом с номером j. Обозначим через X= x(i,j) - (m 1)(m 1) матрицу неизвестных, элемент которой x(i,j) =1, если коммивояжер из города с номером i переедет в город с номером j, x(i,j) = 0, в противном случае; u(i) - специальные переменные, i=1,2,...m. Здесь условия (1) означают, что коммивояжер ровно один раз въедет в каждый город (кроме города с номером 0); условия (2) означают, что коммивояжер ровно один раз выедет из каждого города (кроме города с номером 0), ограничения (3) означают существование лишь одного цикла, начинающегося в городе с номером 0, проходящего через все города и завершающегося в городе с номером 0; ограничения (4) являются естественными условиями на введенные переменные. Граф называется плоским, если вершины являются точками плоскости, а ребра - ломаными линиями (составленными из отрезков) в этой же плоскости, имеющими своими концами вершины, не пересекающимися между собой и не включающими других вершин, кроме своих концов.Основоположником советской школы кибернетики и информатики признан профессор МГУ Алексей Андреевич Ляпунов. Слово «информатика» для обозначения комплекса компьютерных наук было введено в словарь русского языка в 1976 году академиком Андреем Петровичем Ершовым. Существуют три подхода: • сверхширокий, включающий в информатику все, что связано с любыми процессами получения, преобразовании и передачи информации; • широкий, включающий в информатику все, что связано с компьютерами, в том числе вопросы конструирования вычислительной техники; • узкий, определяющий информатику только как науку о применении компьютеров, то есть как науку о компьютерных технологиях.

Содержание

Введение 3

1 Теория графов 5

1.1 Понятие и терминология теории графов 5

1.2 Некоторые задачи теории графов 6

2 Математическая логика и теория типов 25

Заключение 27

Список использованной литературы 30

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

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

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

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

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

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

Прародителем информатики является кибернетика, основанная американским математиком Норбертом Винером, опубликовавшим в 1948 году одноименную книгу. Основоположником советской школы кибернетики и информатики признан профессор МГУ Алексей Андреевич Ляпунов.

Слово «информатика» для обозначения комплекса компьютерных наук было введено в словарь русского языка в 1976 году академиком Андреем Петровичем Ершовым.

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

• широкий, включающий в информатику все, что связано с компьютерами, в том числе вопросы конструирования вычислительной техники;

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

Таким образом, к настоящему времени имеются три толкования термина «информатика».

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

Второе - информатика как полный набор компьютерных наук, точный эквивалент computer science. В данном значении термин объединяет самые разные стороны программирования и использования компьютеров, методов их конструирования и разработки программного обеспечения. Такое толкование чаще всего используется в обычном профессиональном языке и при обратном переводе на английский. Например, «факультет информатики» правильнее всего перевести как «computer science faculty» или «computer science department» в зависимости от того, на какую аудиторию рассчитан перевод (в британском английском более распространено слово «faculty», а в американском - «department»).

Третье - информатика в узком смысле, когда за рамки computer science выносятся детальные вопросы технического устройства компьютеров (hardware), а в составе науки остаются проблемы их применения. В таком значении термин обычно используется в узкопрофессиональной среде программистов, а также в учебных программах. Именно так его следует понимать в общепринятом в образовательной среде словосочетании «информатика и вычислительная техника», иначе получается логическая некорректность.

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

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

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

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

1. Апокин И. А., Майстров Л. Е. История вычислительной техники: От простейших счетных приспособлений до сложных релейных систем. М.: Наука, 2000.

2. Гладких Б. А. От абака до компьютера. Томск: Изд-во НТЛ, 2005.

3. Гутер Р. С., Полунов Ю. Л. От абака до компьютера. М.: Знание, 2001. .

4. Кук Д., Бейз Г. Компьютерная математика. М., Наука, 2000.

5. Марков А.А. Элементы математической логики. М.: Изд-во МГУ, 2004.

6. Пойа Д. Математическое открытие. М.: Наука, 2000.

7. Прилуцкий М.Х. Математические основы информатики. Нижний Новгород: Нижег.гос.ун-т, 2000.

8. Симонович С., Евсеев Г., Алексеев А. Общая информатика. М.: Дело, 1999.

9. Турецкий В.Я. Математика и информатика. Екатеринбург: Пропаганда, 2002.

10. Фор Р., Кофман А., Дени-Папен М. Современная математика. М.: Мир, 2006.

11. Частиков А. Архитекторы компьютерного мира. Спб: БХВ-Петербург, 2002.

12. Шенфилд Дж. Математическая логика. М.: Наука, 2005.