Marketing y la Gestión de la Cadena de Suministros

Imagina la última publicidad que hayas visto en algun medio de comunicación a tal punto que no paras de pensar en ese producto y no pararás hasta comprarlo pues está a un precio que tu consideras "el justo" pero cuando llegas al punto de venta te llevas la sorpresa que no lo tienen, en tu afán por tener en tus manos ese producto vas a otro lado y tienes la misma suerte... pasan de lugar en lugar y en todos te indican que no tienen el producto. ¿Qué pasó? ¿Qué salió mal?

Las empresas deben decidir cuál es la mejor forma de almacenar, manejar y trasladar sus productos y servicios de modo que estén disponibles para los clientes en los surtidos correctos, en el momento oportuno y en el lugar apropiado.

La distribución física y la eficacia logística tienen un impacto importante en la satisfacción del cliente como en los costos de la empresa. Aquí la importancia y naturaleza de la administración de la logística en la cadena de abasto.



Logística del Marketing

Llamada también distribución física; que implican las tareas necesarias para planear, implementar   y   controlar el  flujo físico de materiales, productos terminados e información relacionada desde los puntos de origen hasta los puntos de consumo para satisfacer las necesidades de los clientes manera rentable. 
Es decir se trata de hacer llegar el producto correcto al  cliente  correcto en el lugar correcto y el momento correcto.

El objetivo de la logística de marketing debe ser proporcionar servicio máximo al cliente al menor costo para lo cual la empresa investiga primero la importancia de los diversos servicios de distribución que tiene para sus clientes y luego establecer los niveles de servicio deseado para cada segmento. El objetivo es maximizar las utilidades no las ventas.
Algunas empresas ofrecen menos servicio que sus competidores y cobran un precio más bajo, otras ofrecen mayor servicio y cobran un precio más alto para cubrir los costos elevados.

Las funciones principales de logística incluyen:
Procesamiento de pedidos
Almacenamiento
Control de inventarios y transportación.

Administración de la cadena de Abasto.

Consiste en manejar flujos de valor agregado de materiales, de productos finales y de información relacionada, entre los proveedores, las empresas, los revendedores y los usuarios finales.
Hoy en día las empresas están adoptando el concepto de Administración integrada de la cadena de Abasto que reconoce que la prestación de mejores servicios al cliente y la reducción de los costos de distribución requieren un trabajo en equipo, tanto dentro de la empresa como entre las organizaciones del canal de marketing, a fin de aumentar al máximo el desempeño de todo el sistema de distribución.

Funciones de los Canales de Distribución

Los miembros de un canal de marketing realizan las siguientes funciones:

Reúnen información acerca de los clientes, competidores potenciales reales, y otros actores y fuerzas del entorno de marketing, necesarias para planificar y apoyar el intercambio.
Desarrollan y diseminan comunicaciones convincentes para estimular la compra.
Llegan a acuerdos en cuanto a precios y otros términos para que se traslade la propiedad o posesión.
Hacen pedidos a los fabricantes.
Adquieren los fondos para financiar inventarios en diferentes niveles del canal.
Se encargan del almacenamiento y movimientos sucesivos del producto físico.
Supervisan la transferencia real de propiedad de una organización o persona a otra.
Tramitan el pago de las facturas de los compradores a través de los bancos y otras entidades financieras.
Asumen riesgos relacionados con el canal.
Contacto, encontrar prospectos de compradores y comunicarse con ellos.
Moldean y ajustan la oferta a las necesidades del comprador, incluyendo actividades como fabricación, clasificación, ensamblado y empaque.


Administración de Canal

La empresa debe determinar si distribuirá su producto en forma exclusiva, de manera selectiva o intensamente y deberá definir las obligaciones de cada miembro del canal.
La administración eficaz de canal requiere seleccionar intermediarios, capacitarlos y motivarlos.
La meta es forjar una sociedad a largo plazo que sea rentable para todos los miembros del canal.
Los miembros del canal se deben evaluar periódicamente con estándares preestablecidos.
Modificar  los  sistemas  del  canal  cuando  las  condiciones  del mercado cambian.


Encuentra más de 390 casos de estudio de marketing, administración y gestión empresarial en http://www.facebook.com/EBlogDeRaffo
Recuerda que también puedes seguirnos en twitter como @rtrucios




Te invitamos a compartir nuestros contenidos con tus colegas y así hacer crecer nuestra comunidad





Relación de la Gestión Comercial las demás áreas de la empresa y su ubicación dentro de una estructura organizacional

Con la finalidad de poder desarrollar estrategias comerciales adecuadas para el cumplimiento de los objetivos de la organización, cada departamento ha de coordinar necesariamente con el departamento comercial siguiendo las políticas marcadas por la dirección. En ese sentido, podemos destacara lo siguiente:

Con el departamento de producción:
Volumen de producción, calidad, tiempo para disponer de los productos y servicios, etc.
Con el departamento administrativo financiero:
Ingresos previstos por ventas, presupuestación de nuevos productos servicios o modificaciones es los existentes, determinación de precios, discriminación de los precios, modos de cobro etc.
Con el departamento de recursos humanos:
Selección, formación, ubicación o distribución y retribución de la fuerza de ventas.
Con el departamento de informática:
Elaboración y gestión de bases de datos de clientes para su tratamiento y segmentación, formato y descripciones en factura etc.


Ubicación de la Gestión Comercial en la estructura orgánica de la Empresa.

El organigrama supone la representación gráfica de las funciones principales de la empresa y de sus interrelaciones funcionales y jerárquicas. Depende mucho del giro de la empresa y de la envergadura o tamaño de la misma.
A continuación presento dos tipos de organigramas donde ubicamos al departamento comercial.




Recuerda:

La función comercial en la mayoría de las empresas está encargada al área de ventas  que es la que  conecta el mercado con la organización, siendo el Marketing el nexo de unión entre las  demandas de los consumidores reflejadas en el mercado y la oferta que realizan las empresas, entre las que se produce una relación de intercambio.

La planificación estratégica de los negocios implica las actividades como definir la misión, analizar las oportunidades y los riesgos externos, analizar las fuerzas y debilidades internas, formular metas, formular estrategias, formular programas de apoyo, implementar los programas y obtener feedback y ejercer control.

La propuesta de valor constituye una serie de ventajas o diferenciadores que una empresa ofrece a los clientes para solución de un problema o satifacer una necesidad de manera innovadora.

La gestión Comercial es la función encargada de hacer conocer y abrir la organización al mundo exterior, se ocupa de dos problemas fundamentales, la satisfacción del cliente y la participación o el aumento de su mercado.

La gestión Comercial de una empresa es de vital importancia para alcanzar los objetivos estratégicos. Es uno de los componentes clave para el seguimiento y Reporte de las ventas realizadas dentro de la entidad.

El departamento Comercial se relaciona con los departamentos de Producción, Recursos Humanos, Informática, Administración para lograr una efectiva gestión Comercial.

La ubicación del departamento comercial dentro de la estructura orgánica depende del giro y tamaño de la empresa comercial.


Encuentra más de 390 casos de estudio de marketing, administración y gestión empresarial en http://www.facebook.com/EBlogDeRaffo
Recuerda que también puedes seguirnos en twitter como @rtrucios




Te invitamos a compartir nuestros contenidos con tus colegas y así hacer crecer nuestra comunidad




SAP: COMO COMENZÓ Y EVOLUCIONÓ A LO LARGO DEL TIEMPO



Encuentra más de 390 casos de estudio de marketing, administración y gestión empresarial en http://www.facebook.com/EBlogDeRaffo
Recuerda que también puedes seguirnos en twitter como @rtrucios




Te invitamos a compartir nuestros contenidos con tus colegas y así hacer crecer nuestra comunidad



Cultura Empresarial de SAP - Filiales, subsidiarias y centros de desarrollo de SAP AG alrededor del mundo

SAP cuenta con toda una red de centros de desarrollo, centros de formación y subsidiarias de servicio. Por ejemplo, hay centros de desarrollo (los SAP Labs) en Palo Alto (EE. UU.), Sophia Antipolis (Francia), Bangalore (India) y Tokyo (Japón), y también en otros países. SAP tiene subsidiarias locales en más de 50 países que se encargan de ventas, consultoría, formación y servicios.
Existen diversos centros de formación en Estados Unidos: Newton Square (Philadelphia), Atlanta, San Francisco y Dallas, por citar algunos. En Alemania, hay centros de formación y de consultoría en Walldorf (Baden), Berlín, Hamburgo y Ratingen (Düsseldorf).

SAP Hosting AG & Co. KG, una subsidiaria propiedad absoluta de SAP AG, trabaja a escala internacional y tiene su sede en St. Leon-Rot (Alemania). También tiene filiales en Walldorf, Philadelphia, Palo Alto, Tokyo, Sydney, Singapur y Bangalore. SAP Hosting ofrece extensos servicios de hosting que permiten a las empresas acceder a las soluciones más actuales de SAP de forma rápida y eficaz. Los servicios se adaptan a medida de las necesidades de los clientes de mySAP Business Suite, e incluyen hosting de evaluación, hosting de implementación, hosting de aplicación, operaciones remotas de aplicación, gestión de aplicaciones y formación en host.
SAP Manage ofrece SAP Business One, un producto desarrollado para pequeñas y medianas empresas (PYMES). Además, SAP Manage comercializa y da soporte al producto en Israel.
Steeb es el principal proveedor alemán de sistemas SAP para empresas medianas. Ofrece soluciones sectoriales, de negocios electrónicos y de ERP de gran rendimiento para preparar a las empresas de caras a futuros retos. Steeb lleva desde 1974 trabajando con empresas medianas y ofrece soluciones integrales para sistemas SAP y para su propio producto: SC/400. El programa integral que ofrece incluye ambos productos de software y los servicios correspondientes (consultoría, implementación y soporte), además de hardware y redes. Steeb se centra en el sector de la producción, el comercio al por mayor y el sector servicios. La serie de soluciones avanzadas de Steeb (as//) ofrece soluciones de SAP preconfiguradas para proveedores automovilísticos, fabricantes de maquinaria y equipamiento, y fabricantes de configuración por orden en los sectores de la metalurgia, la madera y los plásticos.



Los empleados de SAP
El buen ambiente característico en SAP llama la atención nada más llegar. Los candidatos que visitan SAP por primera vez pronto se dan cuenta de por qué la empresa tiene tan buena fama. Aquí la gente está relajada y es amable, y la energía en los pasillos te hace sentirte como si hubieras entrado en el campus de una universidad.

Cultura empresarial 
Los nuevos empleados se integran en el mundo de SAP por medio de actos de orientación especiales, programas de empleados en formación y un concepto de mentor que garantiza que cada empleado disfrute de una guía práctica durante este tiempo. Dado que la mentalidad de equipo se valora enormemente en SAP, todos los empleados pueden confiar por
completo en sus compañeros. Sobre todo los empleados nuevos, que pueden beneficiarse de los consejos y la información que aportan compañeros con más experiencia.

Orientación al logro, creatividad e innovación
La cultura de SAP deja mucho espacio para la libertad personal. Esta libertad motiva e inspira a los empleados a desarrollar y hacer realidad sus ideas. Los conceptos creativos e innovadores son siempre bienvenidos en el equipo, y se da apoyo a las nuevas ideas. Este apoyo anima a los empleados e incrementa la productividad tanto del equipo como más allá de los límites de cada departamento. La falta de límites burocráticos y restricciones jerárquicas permite que la información llegue rápidamente a donde debe estar.

Formación a través del desarrollo personal
Los empleados de SAP saben que deben poder reaccionar con flexibilidad ante los cambios y que sus conocimientos deben estar siempre al día. Por ello, la iniciativa personal se da por sentado, al igual que comportarse de forma responsable como representante de la empresa. Esta mentalidad es característica de los empleados de SAP. La cultura de SAP implica también horarios de trabajo flexibles que son aprovechados al máximo, y el aceptar responsabilidades desde el principio está considerado un incentivo para rendir más.

Clientes de referencia e interlocutores
Los clientes de referencia son los que han implementado las soluciones de SAP con éxito y están listos para transmitir su experiencia del proyecto de implementación y del funcionamiento en productivo. Este intercambio de información tiene lugar en visitas a clientes de referencia, mediante llamadas telefónicas, presentaciones y entrevistas.

La colaboración entre SAP y sus proveedores de software asociados garantiza que las soluciones empresariales de SAP y otros sistemas de aplicación se pueden comunicar sin problemas.
El programa de interlocutores de software de SAP proporciona interfases definidas estándar a los proveedores de software. Estas interfases se pueden utilizar para integrar productos adicionales a la perfección en las soluciones de SAP.

Los interlocutores de SAP dan soporte a nuestros clientes durante la selección, la implementación y la utilización productiva de los productos de SAP. Estos interlocutores suelen tener años de experiencia en SAP y pertenecer a SAP Alliance Partner Service y SAP Partner Service. Las empresas asociadas pueden participar en un proceso de cualificación para demostrar su experiencia con algunos productos o soluciones de SAP y obtener así el status de Special Expertise Partner (SEP).

SAP NetWeaver
La plataforma de aplicación e integración de SAP es la base técnica para mySAP Business Suite, SAP Industry Packages y SAP xApps. Proporciona una infraestructura integral, abierta y flexible que permite integrar componentes de SAP o de otros proveedores con facilidad.

SAP NetWeaver se divide en cuatro áreas:

- People Integration
People Integration garantiza que sus empleados contarán con la información y las funciones que necesitan para realizar su trabajo lo más rápida y eficientemente posible. Las funciones de SAP NetWeaver Portal desempeñan un rol primordial para ello.

- Information Integration
Information Integration se utiliza para gestionar todos los datos relevantes para las empresas. Esto incluye datos de la propia empresa y también relativos a terceros.

- Process Integration
Process Integration garantiza que los procesos empresariales se ejecuten más allá de los límites del sistema, en una infraestructura de sistemas heterogénea. Para ello se utilizan paquetes de datos XML y escenarios de workflow, por ejemplo. La SAP NetWeaver Exchange Infrastructure (SAP NetWeaver XI) desempeña un papel principal en este caso.

- Application Platform
Application Platform es compatible con Java 2 Enterprise Edition (J2EE) y ABAP (lenguaje de programación de SAP) en un mismo entorno.
Garantiza la independencia de las bases de datos y los sistemas operativos, una compatibilidad absoluta con aplicaciones empresariales y servicios Web independientes de la plataforma, y un entorno abierto basado en estándares conocidos. El componente central de Application Platform es SAP NetWeaver Application Server.


mySAP ERP
Hoy más que nunca es imperativo garantizar que los procesos empresariales de una organización estén integrados, intercomunicados, y sean transparentes. mySAP ERP permite a las empresas tener un mejor control del entorno administrativo y operativo, e incrementar su eficacia y su rentabilidad. Además, esta aplicación reduce los costes de integración e implementación, ya que se reduce el tiempo antes de beneficios y se compensan las inversiones existentes en TI.
mySAP ERP se ha diseñado de modo que las empresas puedan implementar sólo las funciones empresariales que necesitan mientras las necesiten, lo que simplifica las actualizaciones y reduce el coste total de titularidad.
Con mySAP ERP, SAP ha fijado un nuevo estándar para sistemas ERP. Esta aplicación incorpora las soluciones mySAP ERP Financials, mySAP ERP Human Capital Management, mySAP ERP Operations y mySAP ERP Corporate Services.

mySAP ERP Financials
El objetivo de esta solución es utilizar los fondos de una empresa eficazmente y, en consecuencia, incrementar la rentabilidad a largo plazo.

mySAP ERP Human Capital Management
Todas las empresas tienen empleados. Son recursos importantes, y mySAP ERP HCM permite utilizarlos eficazmente para que la empresa triunfe.
Esta solución abarca todos los aspectos de los recursos humanos, desde la contratación de personal a la formación, pasando por el cálculo de la nómina.

mySAP ERP Operations
mySAP ERP Operations proporciona una amplia solución operativa para automatizar y perfeccionar el aprovisionamiento y la ejecución de la logística, el desarrollo de productos y la fabricación, las ventas y el servicio.

mySAP ERP Corporate Services
Corporate Services presenta soluciones de servicio para ciclos de vida end-to-end para Medio ambiente, Salud y Seguridad, Gestión de viajes y
Gestión de bienes inmuebles. La sección también se dirige al desarrollo de eficientes programas de incentivos.

Los procesos están totalmente integrados. Antes, un sistema ERP se conectaba sólo a una base de datos. Con SAP, un sistema ERP es ahora una combinación de componentes que integran a personas, información y procesos de forma flexible y genérica.
mySAP ERP es además la aplicación principal de mySAP Business Suite.

Evolución de ERP
Con el sistema SAP R/3, SAP creó un estándar de ERP internacional. SAP R/3 cuenta con una amplia gama de funciones estándar integradas. Por ejemplo, los datos de los procesos de ventas, expedición o gestión de stocks se transfieren automáticamente a las funciones de finanzas.
SAP R/3 ha pasado por varios ciclos de release. En cada nuevo release, las funciones se han ampliado, las aplicaciones de han optimizado y las interfases con otros componentes de software se han ampliado. SAP R/3 se desarrolla con ABAP, el lenguaje de programación de SAP.

Desde el lanzamiento de SAP R/3 Enterprise, las modificaciones y las ampliaciones se integran en el sistema como extensiones. Esto acelera y simplifica el proceso de actualización y la adaptación a cada ramo.
SAP ERP Central Component (SAP ECC) es el sucesor natural de SAP R/3 y también uno de los componentes principales de la aplicación mySAP ERP.

mySAP Business Suite
Si desea seguir siendo competitivo en la situación económica actual, debe ser flexible y capaz de cambiar para adaptarse a las nuevas demandas que los clientes crean constantemente. mySAP Business Suite proporciona esta flexibilidad en un paquete integral de soluciones integradas abiertas para toda la cadena de creación de valor. Los clientes, empleados, proveedores e interlocutores se agrupan en una unidad dentro de un proceso prácticamente instantáneo.

Las características y soluciones principales de mySAP ERP se ven reforzadas y ampliadas con las siguientes aplicaciones de mySAP Business Suite:

mySAP Customer Relationship Management
mySAP CRM es una aplicación que da prioridad al cliente. El cliente puede ponerse en contacto con las empresas a través de una serie de canales de comunicación.

mySAP Product Lifecycle Management
Esta aplicación ofrece funciones para el desarrollo y la seguridad del producto, calidad y mantenimiento.

mySAP Supply Chain Management
Las cadenas logísticas no acaban a las puertas de los almacenes. Puede utilizar mySAP SCM para planificar y optimizar cadenas logísticas más allá de los límites de la empresa.

mySAP Supplier Relationship Management
El aprovisionamiento a través de Internet y los mercados son sólo dos modos de optimizar las compras. Los empleados pueden utilizar esta aplicación para el aprovisionamiento con información acerca de la demanda directamente desde sus centros de trabajo de una forma rápida, sencilla y eficaz.


Encuentra más de 390 casos de estudio de marketing, administración y gestión empresarial en http://www.facebook.com/EBlogDeRaffo
Recuerda que también puedes seguirnos en twitter como @rtrucios




Te invitamos a compartir nuestros contenidos con tus colegas y así hacer crecer nuestra comunidad


¿QUÉ ES EL MARKETING DE CONTENIDOS?

MARKETING DE CONTENIDOS







Encuentra más de 390 casos de estudio de marketing, administración y gestión empresarial en http://www.facebook.com/EBlogDeRaffo
Recuerda que también puedes seguirnos en twitter como @rtrucios




Te invitamos a compartir nuestros contenidos con tus colegas y así hacer crecer nuestra comunidad

Una Introducción a la Teoría y Complejidad de la Computabilidad

Te has preguntado alguna vez: ¿Cuál es exactamente el dispositivo en el que estás leyendo este artículo? ¿Qué es una computadora? La ciencia de la computación se remonta a un tiempo mucho antes de que se pensara en estos modernos dispositivos informáticos. En una industria donde las preguntas más frecuentes giran en torno a los lenguajes de programación, marcos y bibliotecas, a menudo damos por sentado los conceptos fundamentales que hacen funcionar una computadora.
Pero estas computadoras, que parecen poseer un potencial infinito— ¿tienen alguna limitación? ¿Hay problemas que las computadoras no pueden resolver?
Teoría de la computabilidad y complejidad
En este artículo, abordaremos estas preguntas alejándonos de los detalles de los lenguajes de programación y las arquitecturas de la computadora. Al comprender el poder y las limitaciones de las computadoras y los algoritmos, podemos mejorar la forma en que pensamos y razonar mejor sobre las diferentes estrategias.
La visión abstracta de la informática produce resultados que han resistido la prueba del tiempo, siendo tan valiosos para nosotros hoy como lo fueron cuando se desarrollaron inicialmente en la década de 1970.

Computabilidad

¿Qué es una computadora? ¿Qué es un problema?

En la escuela, a menudo se nos enseña un modelo mental de problemas y funciones que dice algo como esto:
_ Una función es un procedimiento que aplica a una entrada x para encontrar una salida f(x)._
Resulta que la definición matemática es diferente:
Una función es un conjunto de pares ordenados de modo que el primer elemento de cada par proviene de un conjunto X (llamado el dominio), el segundo elemento de cada par proviene de un conjunto Y (llamado co-dominio o rango) y cada elemento del dominio está emparejado con exactamente un elemento del rango.
Eso fue bastante. Pero, ¿qué significa eso exactamente?
Función
Esta definición nos dice que una computadora es una máquina para funciones informáticas.
¿Por qué?
Porque las computadoras transforman la entrada arbitraria a alguna salida. En otras palabras, resuelven problemas. Las dos definiciones de funciones, la que conocemos muy bien y la formal, coinciden para muchos propósitos prácticos.
Sin embargo, la definición matemática nos permite llegar a conclusiones interesantes tales como la existencia de funciones no procesables (es decir, problemas sin solución):
Por qué no todas las funciones se pueden describir como un algoritmo.

Reglas del Juego

Para ayudar con nuestros argumentos, imaginemos a las computadoras como máquinas que tienen una entrada, desarrollan una secuencia de operaciones y después de un tiempo, dan una salida.
Vamos a llamar a la entrada alfabeto de la máquina, que es un set de secuencia de caracteres de algún conjunto finito. Por ejemplo, el alfabeto de la máquina puede ser binario (0s y 1s) o podría ser el juego de caracteres ASCII. Cualquier secuencia finita de caracteres es una cadena—por ejemplo “0110.”
Además, representaremos el resultado de una máquina como una decisión binaria de aceptación y rechazo que se entrega una vez que la máquina (con suerte) finaliza su cálculo. Esta abstracción se ajusta bien a la definición matemática de funciones anteriores.
Computadora aceptar-rechazar
Dados estos parámetros, es importante caracterizar un tipo más: una colección de cadenas de caracteres. Tal vez nos preocupamos por el conjunto de cadenas de caracteres que acepta una máquina, o tal vez estamos construyendo una máquina que acepta cadenas de caracteres en un determinado conjunto y no en otros, o tal vez estamos preguntando si es posible diseñar una máquina que acepte todo en algún conjunto particular y no en otros.
En todos estos casos, un conjunto de cadenas de caracteres se denomina lenguaje—por ejemplo, el conjunto de todas las cadenas binarias que representan números pares o el conjunto de cadenas que tienen un número par de caracteres. Resulta que los idiomas, como los números, pueden ser operados con los operadores como concatenación, unión, intersección y otros similares.
Un operador importante es el operador estrella Kleene que también se usa con expresiones regulares. Esto se puede considerar como la unión de todos los poderes posibles del lenguaje. Por ejemplo, si nuestro idioma A es el conjunto de cadenas de caracteres { ‘01’, ‘1’ }, entonces un miembro de A* es la cadena de caracteres ‘0101111’.

Contabilidad

La última pieza del rompecabezas antes de demostrar nuestra afirmación de que no todas las funciones son computables es el concepto de contabilización. Intuitivamente, nuestra prueba mostrará que hay más idiomas; es decir, más problemas que posibles programas para resolverlos. Esto funciona porque el tema de si una cadena de caracteres pertenece a un idioma (Sí/No) es en sí misma un problema.
Más precisamente, nuestra prueba afirma que el conjunto de posibles programas es infinitamente contable, mientras que el conjunto de idiomas sobre un alfabeto es infinitamente incontable.
En este punto, puedes estar pensando “La infinidad es una idea bastante extraña en sí misma, ¡ahora tengo que lidiar con dos de ellos!”
Bueno, no es tan malo. Un conjunto contablemente infinito es uno que se puede enumerar. Es posible decir: este es el primer elemento, este es el segundo elemento y así sucesivamente, eventualmente asignando un número a cada elemento del conjunto. Toma el conjunto de números pares, por ejemplo. Podemos decir que 2 es el primero, 4 el segundo, 6 el tercero y así sucesivamente. Tales conjuntos son contablemente infinitos o contables.
Sin embargo, con algunos conjuntos como los números reales, no importa cuán inteligente seas; simplemente no hay enumeración. Estos conjuntos son incontablemente infinitos o incontables.

Muchos Programas de Manera Contable

Primero queremos mostrar que el conjunto de programas de computadora es contable. Para nuestros propósitos, hacemos esto al observar que el conjunto de todas las cadenas de caracteres sobre un alfabeto finito es contable. Esto funciona porque los programas de computadora son cadenas de caracteres finitas.
La prueba es sencilla y no cubrimos los detalles aquí. El punto clave es que hay tantos programas de computadora como, por ejemplo, números naturales.
Para reiterar:
El conjunto de todas las cadenas de caracteres sobre cualquier alfabeto (Ej., Conjunto de todos los programas informáticos) es contable.

Incontablemente, Muchos Idiomas

Dada esta conclusión, ¿qué pasa con los subconjuntos de estas cadenas de caracteres? Preguntado de otra manera, ¿qué pasa con el conjunto de todos los idiomas? Resulta que este conjunto es incontable.
_El conjunto de todos los idiomas sobre cualquier alfabeto es incontable. _
Una vez más, no cubrimos la prueba aquí.

Consecuencias

Aunque pueden no ser inmediatamente aparentes, las consecuencias de la incontabilidad de los idiomas y la contabilización del conjunto de todos los programas informáticos son profundas.
¿Por qué?
Supongamos que A es el conjunto de caracteres ASCII; los caracteres ASCII son solo los necesarios para componer un programa de computadora. Podemos ver que el conjunto de cadenas de caracteres que representan, por ejemplo, los programas de JavaScript son un subconjunto de A* (aquí, * es el operador estrella de Kleene). La elección de JavaScript es arbitraria. Dado que este conjunto de programas es un subconjunto de un conjunto contable, tenemos que el conjunto de programas de JavaScript es contable.
Además, consideremos que para cualquier idioma L podemos definir alguna función f que evalúe a 1 si alguna cadena x está en L y 0 en caso contrario. Todas esas funciones son distintas. Debido a que existe una correspondencia 1:1 con el conjunto de todos los idiomas y porque el conjunto de todos los idiomas es incontable, tenemos que el conjunto de todas esas funciones es incontable.
Aquí está el punto en profundidad:
Como el conjunto de todos los programas válidos es contable pero el conjunto de funciones no lo es, entonces debe haber algunas funciones para las cuales simplemente no podemos escribir programas.
Todavía no sabemos cómo son estas funciones o problemas pero sabemos que existen. Ésta es una realización humillante porque hay algunos problemas por los cuales no hay solución. Consideramos que las computadoras son extremadamente poderosas y capaces sin embargo, algunas cosas están fuera de su alcance.
Ahora la pregunta es: “¿Cómo son estos problemas?” Antes de continuar describiendo estos problemas, primero debemos modelar la computación de forma generalizada.

Máquinas de Turing

Uno de los primeros modelos matemáticos de una computadora fue desarrollado por Alan Turing. Este modelo, llamado máquina de Turing, es un dispositivo extremadamente simple que captura por completo nuestra noción de computabilidad.
Máquina de Turing
La entrada a la máquina es una cinta sobre la cual se ha escrito la entrada. Usando un cabezal de lectura/escritura, la máquina convierte la entrada en salida a través de una serie de pasos. En cada paso, se toma una decisión sobre si y qué escribir en la cinta y si se debe mover hacia la derecha o hacia la izquierda. Esta decisión se basa exactamente en dos cosas:
  • El símbolo actual debajo del cabezal y
  • El estado interno de la máquina, que también se actualiza cuando se escribe el símbolo
Eso es todo.

Universalidad

En 1926, Alan Turing no solo desarrolló la máquina de Turing sino que también tuvo varias ideas importantes sobre la naturaleza de la computación cuando escribió su famoso artículo, “Sobre números computables”. Se dio cuenta de que un programa de computadora en sí podría considerarse como entrada a una computadora. Con este punto de vista, tuvo la hermosa idea de que una máquina de Turing podría simular o ejecutar esa entrada.
Si bien damos por sentadas estas ideas hoy, en la época de Turing la idea de una máquina tan universal fue el gran avance que permitió a Turing desarrollar problemas sin solución.

Tesis de Church-Turing

Antes de continuar, examinemos un punto importante: sabemos que la máquina de Turing es un modelo de computación, pero ¿es lo suficientemente general? Para responder a esta pregunta, pasamos a la Tesis de Church-Turing, lo que da credibilidad a la siguiente declaración:
Todo lo computable es computable por una máquina de Turing.
Mientras Turing desarrolló la máquina de Turing como un modelo de computación, Alonzo Church también desarrolló un modelo de cálculo conocido como lambda-cálculo. Estos modelos son potentes ya que ambos describen la computación y lo hacen de una manera igual a cualquiera de las computadoras de hoy o para cualquier computadora. Esto significa que podemos usar una máquina de Turing para describir los problemas irresolubles que buscamos, sabiendo que nuestros hallazgos se aplicarán a todas las computadoras posibles.

Reconocimiento y Decidibilidad

Tenemos que cubrir un poco más de fondo antes de describir concretamente un problema sin solución, a saber, los conceptos de reconocedores de lenguaje y factores decisivos de lenguaje.
Un idioma es reconocible si hay una máquina de Turing que lo reconoce.
y
Un lenguaje es decidible si hay una máquina de Turing que lo decide.
Para ser un reconocedor de un idioma, una máquina de Turing debe aceptar cada cadena de caracteres en el idioma y no debe aceptar nada que no esté en el idioma. Puede rechazar o repetir esas cadenas. Para ser un factor de decisión, una máquina de Turing siempre debe detener su entrada aceptando o rechazando.
Aquí, la idea de detener la entrada es crítica. De hecho, vemos que los factores de decisión son más poderosos que los reconocedores. Además, un problema se puede resolver, o dicho de otra manera, una función es decidible solo si existe una máquina de Turing que decide el lenguaje descrito por la función.

Indecibilidad

Si alguna vez has escrito un programa de computadora, seguramente debes saber la sensación de estar sentado allí, solo mirando la computadora girar las ruedas cuando se ejecuta el programa. No se sabe si el programa tarda mucho o si hay algún error en el código que causa un ciclo infinito. Es posible que incluso te hayas preguntado por qué el compilador no verifica el código para ver si se detendría o se repetirá para siempre cuando se ejecute.
El compilador no tiene dicho control porque simplemente no se puede hacer. No es que los ingenieros de compilación no sean lo suficientemente inteligentes o carezcan de los recursos, es simplemente imposible verificar un programa de computadora arbitrario para determinar si se detiene.
Podemos probar esto usando la máquina de Turing. Las máquinas de Turing se pueden describir como cadenas de caracteres, por lo que hay un número contable de ellas. Supongamos que M1, M2, y así sucesivamente conforman el conjunto de todas las máquinas de Turing. Vamos a definir la siguiente función:
f(i, j) = 1 si Mi acepta <Mj>, 0 al contrario
Aquí, <M> es la sintaxis para la “codificación de cadena de M” y esta función representa el problema de producir 1 si Mi se detiene al aceptar Mj como entrada y salida 0 al contrario. Ten en cuenta que Mi debe detener (es decir, ser un factor decisivo). Esto es necesario ya que deseamos describir una función indecidible (es decir, problema sin solución).
Ahora, definamos también un lenguaje L que consiste en codificaciones de cadenas de máquinas de Turing que NO aceptan sus propias descripciones:
L = { <M> | M no acepta <M> }
Por ejemplo, alguna máquina M1 puede dar en la salida 0 para la entrada <M1&gt, mientras que otra máquina M2puede dar en la salida 1 para la entrada <M2>. Para probar que este lenguaje es indecidible, preguntamos qué hace ML, la máquina que decide el lenguaje L, cuando se le da su propia descripción <ML> como entrada. Hay dos oportunidades:
ML acepta <ML>
o
ML rechaza <ML>
Si ML acepta su propia codificación, entonces eso significa que <ML> no está en el idioma L. Sin embargo, si ese fuera el caso, entonces ML no debería haber aceptado su codificación en primer lugar. Por otro lado, si ML no acepta su propia codificación, entonces <ML> está en el lenguaje L, entonces ML debería haber aceptado su codificación de cadena de caracteres.
En ambos casos, tenemos una paradoja o, en términos matemáticos, una contradicción, que demuestra que el lenguaje L es indecidible; por lo tanto, hemos descrito nuestro primer problema sin solución.

Deteniendo el Problema

Si bien el problema que acabamos de describir puede no parecer relevante, puede reducirse a problemas adicionales irresolubles de importancia práctica, sobre todo el problema de detención:
El lenguaje de las codificaciones de las máquinas de Turing que se detienen en la cadena vacía.
El problema de detención se aplica a la pregunta de por qué los compiladores no pueden detectar nudos infinitos desde antes. Si no podemos determinar si un programa termina en la cadena vacía, entonces ¿cómo podríamos determinar si su ejecución daría como resultado un nudo infinito? En este punto podría parecer que agitamos nuestras manos para llegar a una conclusión simple sin embargo, nos dimos cuenta de que ninguna máquina de Turing puede decir si un programa de computadora se detendrá o permanecerá en un nudo para siempre. Este es un problema importante con aplicaciones prácticas y no se puede resolver en una máquina de Turing o cualquier otro tipo de computadora. Un iPhone no puede resolver este problema. Un escritorio con muchos núcleos no puede resolver este problema. La nube no puede resolver este problema. Incluso si alguien quisiera inventar una computadora cuántica, aún no sería capaz de resolver el problema de detención.

Resumen

En nuestro examen de la teoría de computabilidad hemos visto cómo hay muchas funciones que no son computables en ningún sentido ordinario de la palabra mediante un argumento de conteo. Definimos con precisión lo que queremos decir con computación, remontándonos a la inspiración de Turing a partir de su propia experiencia con lápiz y papel para formalizar la máquina de Turing. Hemos visto cómo este modelo puede calcular cualquier cosa que cualquier computadora actual o prevista para mañana pueda y nos dimos cuenta de una clase de problemas que no son computables en absoluto.
Aun así, la computabilidad tiene una desventaja. El hecho de que podamos resolver un problema no significa que podamos resolverlo rápidamente. Después de todo, ¿de qué sirve una computadora si su cálculo no va a terminar antes de que el sol se vuelva nova sobre nosotros decenas de millones de años en el futuro?
Dejando las funciones computables y los lenguajes atrás, ahora discutimos la complejidad de cómputo, examinando el cálculo eficiente y el famoso problema P vs. NP.

Complejidad

Lento vs. Rápido

Los científicos informáticos reconocen una variedad de clases de problemas y dos clases que nos importan incluyen problemas que las computadoras pueden resolver rápida o eficientemente, conocidos como P y problemas cuyas soluciones se pueden verificar rápidamente pero no se pueden obtener rápidamente, conocidas como NP.
Por ejemplo, supongamos que eres responsable de desarrollar algoritmos para un servicio de citas en línea y alguien plantea la pregunta: “¿Todos pueden obtener una cita?” La respuesta se reduce a emparejar individuos compatibles para que todos estén emparejados. Resulta que hay algoritmos eficientes para resolver este problema. Este problema está en el conjunto P.
Bueno, ¿y si quisiéramos identificar la hermandad más grande entre nuestros usuarios? Por hermandad, nos referimos a la red más grande de individuos que son compatibles entre sí. Cuando el recuento de usuarios es bajo, este problema se puede resolver rápidamente. Podemos identificar fácilmente, por ejemplo, una hermandad con 3 usuarios. Sin embargo, a medida que empezamos a buscar hermandades más grandes, el problema se vuelve cada vez más difícil de resolver. Este problema está en el conjunto NP.

Definiciones Formales

P es el conjunto de problemas que se pueden resolver en tiempo polinomial. Es decir, el número de pasos computacionales está limitado por una función polinómica con respecto al tamaño del problema. Sabemos que la pregunta “¿Todos pueden tener una cita?”, también conocida como problema de coincidencia bipartita, está en P.
NP es el conjunto de problemas que son verificables en tiempo polinomial. Esto incluye todos los problemas en P, por supuesto; sin embargo, no sabemos si esta contención es estricta. Conocemos problemas que son verificables de manera eficiente pero que no se pueden resolver de manera eficiente, pero no sabemos si el problema es verdaderamente insoluble. El problema de la hermandad es uno de esos problemas. Sabemos que podemos verificar la solución de manera eficiente pero no sabemos con certeza si podemos resolver el problema de manera eficiente.
Por último, NP-complete es el conjunto de problemas que son los problemas más difíciles en NP. Se les conoce como los más difíciles porque cualquier problema en NP se puede transformar eficientemente en NPC. Como resultado, si alguien identificara una solución eficiente a un problema en NPC, toda la clase de NP sería absorbida por P. El problema de la hermandad también está en NPC
P vs. NP
Por lo tanto, llegamos al problema de P contra NP. Muchos científicos informáticos y matemáticos creen firmemente que P y NP no son iguales. Si lo fueran, las implicaciones serían más allá de lo profundo. Gran parte de la infraestructura digital actual se basa en el hecho de que hay problemas en NP que no están en P. Si ese no fuera el caso, los métodos criptográficos por ejemplo, colapsarían de la noche a la mañana, permitiendo que una persona que posee una solución eficiente a un problema de NPC pueda subvertir incluso los protocolos de seguridad más estrictos.

Sutilezas de Trazabilidad

Para los principiantes en informática, la diferencia entre los problemas de emparejamiento y hermandad no parece ser un gran problema. De hecho, la diferencia entre un problema en P y un problema en NP puede ser muy sutil. Ser capaz de notar la diferencia es importante para cualquiera que diseñe algoritmos en el mundo real.
Considera el problema de la ruta más corta. Dadas dos ubicaciones, el objetivo es identificar el camino más corto entre ellas. Un iPhone calcula esto en cuestión de milisegundos. Este es un problema computacionalmente tratable.
Por otro lado, considera el problema del vendedor ambulante, donde el objetivo es visitar un subconjunto de posibles destinos que terminan en el origen mientras viajan la distancia más corta posible. Este problema es similar al problema de ruta más corta pero es NP-completo; también explica por qué la logística de la cadena de suministro es una industria de mil millones de dólares.
De hecho, podemos ser aún más sutiles. En lugar de pedir el camino más corto (P), podemos pedir el camino más largo sin nudos. Resulta que el problema de la ruta más larga también es NP-completo.
Hay muchos más ejemplos de esta sutil distinción, incluida la identificación de las coberturas de los vértices en los gráficos bipartitos vs. generales o la satisfacción de las fórmulas booleanas con dos y tres literales por cláusula. El punto es que no es inmediatamente obvio si un problema está en P o NP, por ello la razón del análisis del tiempo de ejecución es una habilidad crítica. Si el algoritmo que uno debe diseñar es para un problema en P, entonces sabemos que hay una solución eficiente. Si, por otro lado, el problema está en NP, entonces tenemos un caso fuerte para argumentar en contra de buscar una solución, porque el algoritmo en general, simplemente tomaría demasiado tiempo para resolver el problema.

Resumen

En este examen de complejidad, definimos las clases de problemas P y NP. P informalmente representa problemas que pueden ser resueltos eficientemente por una computadora, mientras que NP representa aquellos que son verificables de manera eficiente.
Nadie ha podido demostrar que P no es igual a NP. Si estas dos clases de problemas son equivalentes, es lo que se conoce como el problema P vs. NP y es el problema abierto más importante en la informática teórica actual, si no en todas las matemáticas. De hecho, en el año 2000, el Clay Math Institute denominó al problema P vs. NP como una de las siete preguntas abiertas más importantes en matemáticas y ha ofrecido una recompensa de un millón de dólares por una prueba que determina la solución a este problema.

Conclusión

En este artículo nos adentramos en los ámbitos de la computabilidad y la complejidad, respondiendo grandes preguntas como “¿Qué es una computadora?”. Si bien los detalles pueden ser abrumadores, hay una serie de aprendizajes profundos que vale la pena recordar:
  • Hay algunas cosas que simplemente no se pueden calcular, como el problema de detención.
  • Hay algunas cosas que no se pueden calcular de manera eficiente, como los problemas en NPC.
Más importantes que los detalles son las formas de pensar sobre computación y problemas computacionales. En nuestra vida profesional e incluso en nuestro día a día, podemos encontrarnos con problemas nunca antes vistos y podemos usar herramientas y técnicas probadas para determinar el mejor curso de acción.
Fuente:

Síguenos en Google +

El Blog de Raffo recomienda