Программирование Бессараб Федор Семенович

Содержание программы Введение. Возникновение вычислительных систем и компьютеров. Понятие об алгоритме. Машина Тьюринга и машина фон Неймана. Структура реального компьютера. Персональный компьютер. Hardware и Software. Характеристика основных устройств персонального компьютера. Понятие операционной системы. Назначение операционной системы. Операционные системы DOS и Windows. Файлы и файловая система. Логическая и физическая структура файловой системы. Файловые оболочки, их назначение и основные функции. Программы - утилиты. Архивы, архивация данных. Математические принципы сжатия данных. Использование компьютера в лаборатории. Редактор Word, особенности набора математического текста. Использование электронной таблицы Excel для вычислений и оформления лабораторных работ. Основы программирования. Алгоритмизация, языки программирования. Методы программирования: структурное программирование, объектно- ориентированное программирование, шаблоны. Язык программирования С++. Структура программы. Основные концепции языка.

План лекции 1 Анкета Историческая справка Алгоритм. Понятие Алгоритма Машина Тьюринга

Анкета школы Была ли информатика в школе Был ли компьютерный класс Тип операционной системы ПК в школе (Windows, DOS, другие) Было ли программирование и на каком языке Есть ли дома компьютер Оценить свою подготовку по 5 шкале

История теория (Декарт, Лейбниц) практика (Бэббидж, Чарльз) Алгоритм

Вычислительные машины Бэббиджа Малая разностная машина (1822, оперировала 18 разрядными числами с точностью до восьмого знака после запятой и обеспечивала скорость вычислений 12 членов последовательности в 1 минуту. Могла считать значения многочленов 7-ой степени.) Большая разностная машина (не была построена) Аналитическая машина (проект)

Аналитическая машина Бэббиджа состояла из: склада (store), фабрики или мельницы (mill), управляющего элемент (control) и устройства ввода/вывода информации.

Алгоритм Интуитивное понятие алгоритма (алгоритм – это инструкция): А. - строгая и четкая система правил, которая определяет последовательность действий над некоторыми объектами, и после конечного числа шагов приводит к достижению поставленной цели. Аль Хорезми (Абу Джаффар Мухаммед Ибн Муса Аль Хорезми персидский математик ~ 820 г н.э.)

Алгоритм Евклида Вычисление наибольшего общего делителя двух натуральных чисел A и В (А>В) 1. Если А < В, поменять местами. 2. Вычислить остаток от деления А/В и сохранить как С. 3. Если С=0, то идти на 5, иначе идти на 4 4. Заменим А на В, В на С, идти на СТОП, В – НОД, Вычисление остатка от деления – «сложная» операция (подпрограмма вычисления остатка).

Вычисление остатка вычитанием 1. Взять А и В. 2. Если А<B, то идти на 4, иначе идти на Заменим А на A-В, идти на СТОП, A – остаток

Уточненное определение Алгоритма Объекты реального мира можно отображать словами в различных алфавитах А. – четкая и конечная система правил для преобразования слов из некоторого алфавита в слова из этого же алфавита Всякая ли задача алгоритмически разрешима?

Машина Тьюринга L921 состояние Буквыалфавита На ленте написано «слово» Работа начинается с крайней правой буквы Результат – записано новое «слово» МТ в левой позиции в состоянии останова реакция состоит из трех возможных действий: написать новую букву перейти в новое состояние передвинуться влево или вправо

Алфавит м. Тьюринга С каждой машиной Тьюринга связаны два конечных алфавита: алфавит входных символов A = {a0, a1,..., am} С разными машинами Тьюринга могут быть связаны разные алфавиты A и Q. Состояние q0 называется пассивным (останов) - если машина попала в это состояние, то она закончила свою работу. В состоянии q1 машина начинает свою работу. и алфавит состояний Q = {q0, q1,..., qp}.

Программа для м. Тьюринга у машины Тьюринга есть три вида операций. Каждый раз для очередной пары (q j, a i ) МТ выполняет команду, состоящую из трех операций с определенными параметрами. Программа для машины Тьюринга представляет собой таблицу, в каждой клетке которой записана команда.

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