Решение задач на тему: Теория графов. Понятие и терминология теории графов. Некоторые задачи теории графов

Введение

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

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

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

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

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

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

Оглавление

- Введение 3

- Теория графов

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

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

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

- Заключение 27

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

Заключение

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

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

Несмотря на широкую распространенность термина "информатика", у специалистов до сих пор нет единого мнения о его толковании. Существуют три подхода:

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

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

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

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

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

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

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

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

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

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

Возникновение информатики во второй половине 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.