Сделай Сам Свою Работу на 5

Возрастная периодизация детей дошкольного возраста





СОДЕРЖАНИЕ

1. Определение алгоритма 3

2. Теория алгоритмов и ее основатели: 4

2.1. Тьюринг Алан 5

2.2. Клини Стефан Коул 8

2.3. Чёрч Алоиз 10

2.4. Пост Эмиль Леон 13

3. Список литературы 15

 


Определение алгоритма

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

Слово алгоритм содержит в своем составе преобразованное географическое название Хорезм. Термин «алгоритм» обязан своим происхождением великому ученому средневекового Востока–Муххамад ибн Муса ал-Хорезми (Магомет, сын Моисея, из Хорезма ). Он жил приблизительно с 783 по 850 годы, и в 1983 году отмечалось 1200-летие со дня его рождения в городе Ургенче – областном центре современной Хорезмской области Узбекистана. В латинских переводах с арабского арифметического трактата ал-Хорезми его имя транскрибировалось как algorismi. Откуда и пошло слово «алгоритм» – сначала для обозначения алгоритмов цифровых вычислений десятичной позиционной арифметики, а затем для обозначения произвольных процессов, в которых искомые величины решаемых задач находятся последовательно из исходных данных по определенным правилам и инструкциям.



 

Теория алгоритмов и ее основатели

Теория алгоритмов не учит "составлять" алгоритмы. Она занимается более важным вопросом. Основная задача классической теории алгоритмов – это ответ на вопрос: " Можно ли (вообще) для задач данного типа построить алгоритм?". Говоря более наукообразно: "Являются ли задачи данного типа алгоритмически разрешимыми? "Это связано с тем, что, во-первых, не для всех задач возможно создать алгоритмы их решения. А, во-вторых, чтобы сделать математически строгий вывод о невозможности построить алгоритм, надо иметь строгое (формальное) определение самого алгоритма. Но понятие АЛГОРИТМА относится к фундаментальным неопределяемым понятиям. Понятие алгоритма заменили строго формализованными математическими моделями. Среди самых известных рекурсивные функции, машины Тьюринга и нормальные алгорифмы Маркова. Эти математические модели выступают в роли "конкретизаций понятия алгоритма". То есть длительная практика подтверждает так называемый тезис Черча, который можно пересказать так: Для любой алгоритмически разрешимой задачи можно построить рекурсивную функцию (машину Тьюринга, нормальный алгорифм Маркова). И наоборот, для задач, для которых нельзя построить перечисленные конкретизации, не существует алгоритма решения.



 

Тьюринг Алан

 

 

 

Тьюринг Алан Матисон(Turing, Alan Mathison) (1912–1954), английский математик, логик. Тьюринг родился в Лондоне 23 июня 1912. Учился в Шерборнской школе, затем в Кембриджском университете, который окончил в 1935. В том же году был избран членом совета Кингз-колледжа. В 1936–1938 работал над докторской диссертацией в Принстонском университете в США. В 1937 он опубликовал известную работу «О вычислимых числах, с приложением к проблеме разрешимости» (On the Computable Numbers, with an Application to the Entscheidungsproblem), в которой, используя «машины Тьюринга», показал невозможность существования формальной, чисто механической процедуры, которая позволяла бы решать, выводимо ли данное высказывание из некоторого набора математических аксиом. Вместе с К.Гёделем Тьюринг похоронил надежды Д.Гильберта и его последователей, полагавших, что всю математику можно представить в виде набора аксиом и получаемых на их основе теорем. Поскольку машина Тьюринга является абстрактной вычислительной машиной, было доказано, что существует класс логических задач, не разрешимых с помощью любого компьютера.



Во время Второй мировой войны Тьюринг работал в организации, занимавшейся расшифровкой кодов противника. Принимал участие в создании электромеханического устройства для дешифровки текстов, получаемых с помощью немецкой шифровальной машины «Энигма», и в течение некоторого времени возглавлял отдел, осуществлявший радиоперехват. После войны Тьюринг предложил весьма амбициозный проект АСЕ (Automatic Computing Engine – Автоматическая Вычислительная Машина), над которой работал в Национальной физической лаборатории в 1945–1948. Когда работа над проектом замедлилась по бюрократическим причинам, он перешел на преподавательскую работу в Манчестерский университет, где к его услугам был уже действовавший небольшой компьютер «Марк-1». С конца 1940-х годов Тьюринг занимался математическими проблемами биологии. Свои идеи Тьюринг сформулировал в нескольких выступлениях и интервью, а также в статье Вычислительные машины и разум (Computing Machinery and Intellegence), опубликованной в журнале «Майнд» («Mind») (1950). Эта статья стала эпохальной для той отрасли компьютерной науки, за которой впоследствии закрепилось название «искусственный интеллект». В 1951 Тьюринг был избран членом Лондонского королевского общества.

Умер Тьюринг в своем доме в Уилмслоу, близ Манчестера, 7 июня 1954

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

Машина Тьюринга – машина, имитирующая о осуществляющая алгоритмические процессы. Концепция такого рода машины возникла в середине 30-х годов 20 века в результате анализа действий человека, выполняющего в соответствии с заранее разработанным планом те или иные вычисления, то есть последовательные преобразования знаковых комплексов. Анализ этот в свою очередь, был осуществлен Тьюрингом с целью решения назревшей к тому времени проблемы поиска точного математического эквивалента для общего интуитивного представления об алгоритме.

Машина Тьюринга – это математическая модель идеализированного вычислительного устройства. Ее удобно представить в виде автоматически функционирующего устройства, способного находиться в конечном числе внутренних состояний и снабженного бесконечной внешней памятью - лентой. Лента разделена на конечное число ячеек, в каждой ячейке ленты в определенный момент времени записан один из символов а0, а1, а2, ..., аN.

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

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

Кроме ленты, имеется головка чтения/записи, которая, во-первых, умеет двигаться вперед, назад и стоять на месте; во-вторых, умеет читать содержимое, стирать и записывать символы из данного алфавита; в третьих , управляется программой.

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

Машина Тьюринга - это модель компьютера, и решает она следующую проблему: если для решения задачи можно построить машину Тьюринга, то она алгоритмически разрешима.

И машина Тьюринга, и машина Поста эквивалентны по своим возможностям. Разработаны практически в одно и то же время (в 1936 году) независимо друг от друга.

Можно ли любой алгоритм представить в форме машины Тьюринга? Ответ на этот вопрос дается в виде так называемого тезиса Тьюринга: всякий алгоритм представим в форме машины Тьюринга. Это тезис потому, что его невозможно доказать, так как в нем фигурируют, с одной стороны, интуитивное понятие «всякий алгоритм», а с другой стороны – точное понятие «машина Тьюринга».

Класс нормальных алгоритмов Маркова и класс алгоритмов, представленных в форме машин Тьюринга, совпадают.

 


Клини Стефан Коул

5.1.1909 Родился в Хартфорд, штат Коннектикут
член Национальной Академии Наук США
Окончил Принстонский университет
В 1934 получил степень доктора философии в Принстонском университете
С 1935 работает в Висконсинском университете
С 1948 профессор
В книге «Введение в математику» дал очерк состояния оснований математики и возникших в середине 20 века в этой связи основных направлений в математической логике. В ней подробно рассмотрены интуиционские системы.
Введена классификация Клини-Мостовского для теоретико-числовых предикатов, независимо С.Клини и А.Мостовским

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

Чёрч Алоизо

Чёрч Алоизо (Church Alonzo) (родился 14.6.1903, Вашингтон) – крупный американский логик и математик, профессор математики Принстонского и Калифорнийского универститетов. С 1936 года редактор журнала «The Journal of Symbolic Logic». Занимался исследованиями проблемы логической семантики. Внес большой вклад в развитие математической логики и теории автоматов. Он знаменит тем, что в 1935 году построил первый пример неразрешимой массовой проблемы, которая состоит в требовании найти алгоритм для решения некоторой серии «единичных» проблем. Массовая проблема неразрешима, если ее решения, то есть требуемого алгоритма, е существует.

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

Алоизо Чёрч автор книги «Введение в математическую логику» (1956), в которой разъяснил свое понимание метода математической логики, определил ее первичные понятия и изложил исчисление высказываний или пропорциональное исчисление, функциональные исчисления первого порядка, чистое функциональное исчисление первого порядка и функциональные исчисления второго порядка. А.Чёрч дает определения таких категорий, как имя, константы и переменные функции, символы, связки, операторы, кванторы, проблема разрешения, непротиворечивость и полнота системы аксиом.

Математическую логику А.Чёрч называет формальной логикой, предмет которой изучается методом построения формализованных языков. «Обычно (формальная) логика, – пишет он, – занимается анализом предложений и доказательств; при этом основное внимание обращается на форму в отвлечении от содержания…»[1] Поскольку естественные языки на протяжении длительных исторических периодов развивались под влиянием практических потребностей легкости общения, постольку они не отличаются точностью и надежностью, что приводит к ошибкам в рассуждениях. Чтобы избежать возможных ошибок, А.Черч предлагает употреблять для логических целей специально созданный язык – формализованный язык, в который из обычных языков будут перенесены собственные имена. При этом он подчеркивает, что в хорошо построенном языке каждое имя должно иметь точно один смысл, если ставится задача обеспечить однозначность в формализованных языках. Суждение А.Чёрч определяет так: «Всякий концепт истинного значения называется суждением независимо от того, является ли он смыслом какого-либо предложения».[2]

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

 

Пост Эмиль Леон

Первые многозначные логики построили независимо друг от друга польский логик Я. Лукасевич в 1920 г. и американский логик Э.Пост в 1921 г. С тех пор построены и исследованы десятки и сотни таких «логик».

Пост (Post) Эмиль Леон (11.2.1897 – 21.04.1954) – американский математик и логик. Читал лекции по математике и логике в Колумбийском, Нью-йоркском и других университетах США. Им получен ряд фундаментальных результатов в математической логике: одно из наиболее употребительных определений понятий непротиворечивости и полноты формальных систем (исчислений); доказательства функциональной полноты и дедуктивной полноты (в широком и узком смысле) исчисления высказываний; изучение систем многозначной логики с более чем 3 значениями истинности; одно из первых (независимо от Тьюринга) определений понятия алгоритма в терминах «абстрактной вычислительной машины» и формулировка основного тезиса теории алгоритмов о возможности описать любой конкретный алгоритм посредством этого определения; результаты о выразимости общерекурсивных функций и предикатов через примитивно рекурсивные, в частности так называемая теорема о нормальной форме; первые (одновременно с А.А.Марковым) доказательства алгоритмической неразрешимости ряда проблем математической логики и алгебры.

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

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

Машина Поста – математическое построение, предназначенное для уточнения понятия алгоритма.

Машиной называется потому, что при построении используются некоторые понятия реальных машин – память, команда, и пр.

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

Кроме ленты, имеется головка чтения/записи, которая: - умеет двигаться вперед, назад и стоять на месте;

– умеет читать содержимое, стирать и записывать метку;

– управляется программой, в которую могут входить в любой комбинации и любом количестве шесть команд:

1) Вправо

2) Влево

3) Поставить метку

4) Стереть метку

5) Передачи управления на один номер команды в программе, если в текущей ячейке есть метка; если метки нет, то передача управления на другой номер команды

6) Прекращения работы

Состояние машины – это состояние ленты и положение головки чтения/записи.

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

Машина Поста – это модель компьютера.

Машина решает следующую проблему: если для решения задачи можно построить машину Поста, то она алгоритмически разрешима.

Машина Поста и машина Тьюринга эквивалентны по своим возможностям. Разработаны практически в одно и то же время (в 1936 г.) независимо друг от друга.

Можно ли любой алгоритм представить в форме машины Поста? Ответ на этот вопрос дается в виде так называемого тезиса Поста: всякий алгоритм представим в форме машины Поста. Это тезис потому, что его невозможно доказать, так как в нем фигурируют с одной стороны, интуитивное понятие «всякий алгоритм», а с другой стороны – точное понятие «машина Поста».


Список литературы

 

1. Ершов Ю.Л., Палютин Е.А. Математическая логика. М.: Наука, 1987.

2.Клини С. Введение в метаматематику. - М.: Изд-во иностр. лит., 1957.

3. Клини С. Математическая логика. М., 1973.

4. Клини С.К.Машины Тьюринга и рекурсивные функции. М., 1972.

5. Кондаков Н.И. Логический словарь-справочник. – М.: Наука, 1975.

6. Малышев А. Алгоритмы и рекурсивные функции. - М.: Наука, 1986.

7. Математическая энциклопедия. – М.: Изд-во «Советская энциклопедия», 1982.

8. Успенский В.А. Машина Поста. М.: Наука, 1988. - 96 с.

9.Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. - М.: Наука, 1987. - 288с

10. Чёрч А. Введение в математическую логику. Т. 1. – М., 1960.

 


 

Таблица 1

Возрастная периодизация детей дошкольного возраста

Годы жизни Периоды Группы
по биологическим признакам по педагогическим признакам
1-10 дней Новорожденный Дошкольный возраст Ранний Первая
1 год Грудной возраст Вторая
2 года Раннее детство Младший Первая младшая
3 года Вторая младшая
4 года Первое детство Средний Средняя
5 лет Старший Старшая
6 лет Подготовительная
7 лет

 


[1] Чёрч А. Ввведение в математическую логику. Т. 1. – М., 1960. – С. 15.

[2] Там же, с. 32.

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.